Bulletin of the American Physical Society
APS March Meeting 2023
Volume 68, Number 3
Las Vegas, Nevada (March 5-10)
Virtual (March 20-22); Time Zone: Pacific Time
Session B64: Quantum Algorithms for Optimization |
Hide Abstracts |
Sponsoring Units: DQI Chair: Matthew DeCross, Quantinuum Room: Room 415 |
Monday, March 6, 2023 11:30AM - 11:42AM |
B64.00001: Iterative approaches to quantum optimization via problem reductions Stuart Hadfield, Sohaib Alam, Lucas Brady, Zhihui Wang Existing approaches to tackling combinatorial optimization problems on quantum computers typically operate by constructing a quantum algorithm from which global candidate solutions are directly sampled. However, this often leads to onerous requirements on the quantum device if one expects to find optimal or high-quality approximate solutions with this approach. An alternative paradigm is to instead use the quantum computer in an iterative fashion to obtain partial information about the given problem instance at each step (such as expectation values of local operators or other instance properties), which is then used to classically simplify the instance, and after enough iterations a global solution is obtained. In this direction we propose and study a general hybrid quantum-classical framework for quantum optimization via iterative problem reductions. Our framework encapsulates and extends a number of related existing quantum approaches such as RQAOA as well as various classical greedy algorithms. In particular, we propose how to extend these approaches to the important setting of problems with hard feasibility constraints, through either feasibility-preserving or penalty-based approaches. We further show how our framework naturally extends to a variant of branch-and-bound tree search, which as a heuristic can be run for some number of iterations and the best solution found returned, or the tree exhaustively searched (up to branch pruning) when a complete (exact) solver is required. Our results help pave the way towards novel deployment of quantum computers for optimization and new paths to potential advantage in the hybrid quantum-classical setting. |
Monday, March 6, 2023 11:42AM - 11:54AM |
B64.00002: How Much Entanglement Do Quantum Optimization Algorithms Require? Yanzhu Chen, Linghua Zhu, Chenxu Liu, Nicholas Mayhall, Edwin Barnes, Sophia Economou Many classical optimization problems can be mapped to finding the ground states of Ising Hamiltonians, for which quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) provide heuristic methods. It is unclear how entanglement affects their performance. An Adaptive Derivative-Assembled Problem-Tailored (ADAPT) variation of QAOA improves the convergence rate by allowing entangling operations in the mixer layers whereas it requires fewer CNOT gates in the entire circuit. In this talk, I will examine the entanglement generated during the execution of ADAPT-QAOA and show that its behavior is quite different from standard QAOA. |
Monday, March 6, 2023 11:54AM - 12:06PM |
B64.00003: How hard is it to outperform a classical simulator at running a quantum optimization algorithm? Maxime Dupont, Nicolas Didier, Mark J Hodson, Joel E Moore, Matthew Reagor Platforms for studying variational quantum-classical algorithms (VQAs) with superconducting qubit processors reaching beyond the limits of exascale emulation limits are on the horizon. In this talk, we review recent work on one pattern of VQA, the QAOA ansatz. First, we refine expected boundaries for scaling up noisy simulation with QAOA with tensor networks, limited by entanglement [1]. Still, initial states and final solutions with QAOA typically have low entanglement. We thus clarify the evolution of entanglement during the execution of the algorithm [2]. Next, we report QAOA runs on the recent Aspen-M 80Q platform at Rigetti [1]. |
Monday, March 6, 2023 12:06PM - 12:18PM |
B64.00004: Spectral analysis for Variational Quantum Algorithms: noise diagnostics, error mitigation, and efficient cost function recovery Enrico Fontana, Cristina Cîrstoiu, Ivan Rungger, Ross Duncan We study the cost function of variational quantum algorithms (VQAs) from a spectral analysis perspective. This enables the use of signal processing tools for noisy and noiseless analysis. For different noise models, we quantify the additional, higher frequency modes in the output signal caused by device errors. We show that filtering these noise-induced modes effectively mitigates errors. We then employ spectral analysis and compressed sensing to identify settings where a noiseless VQA cost function can be recovered classically, and present theoretical and numerical evidence supporting the viability of similar sparse recovery techniques. As demonstration, we efficiently recover simulated Quantum Approximate Optimization Algorithm (QAOA) instances of large system size from a few samples, indicating that sparse recovery can enable a more efficient use of quantum resources in the optimisation of variational algorithms. Overall, we make the case that spectral analysis constitutes an exciting new tool for studying VQAs, and as such may be of interest to the broader community striving to bring near-term quantum computers up to their full potential. |
Monday, March 6, 2023 12:18PM - 12:30PM |
B64.00005: Performances and limitations of variational quantum algorithms under realistic noise models Marco Schumann, Frank Wilhelm-Mauch, Alessandro Ciani Variational quantum algorithms (VQAs) are promising candidates to perform useful tasks with the currently available noisy quantum computers. However, these algorithms may suffer from the problem of barren plateaus that hinder their trainability. Recently, it was also shown that general Pauli noise can worsen the barren plateau problem [1]. |
Monday, March 6, 2023 12:30PM - 12:42PM |
B64.00006: Measurement-based Approaches to Quantum Approximate Optimization Tobias Stollenwerk, Stuart Hadfield Parameterized quantum circuits are attractive candidates for potential quantum advantage in the near future. |
Monday, March 6, 2023 12:42PM - 12:54PM |
B64.00007: Testing symmetry on quantum computers Soorya Rethinasamy, Margarite LaBorde, Mark Wilde Symmetry is a unifying concept in physics. In quantum information and beyond, it is known that quantum states possessing symmetry are not useful for certain information-processing tasks. For example, states that commute with a Hamiltonian realizing a time evolution are not useful for timekeeping during that evolution, and bipartite states that are highly-extendible are not strongly entangled and thus not useful for basic tasks like teleportation. Motivated by this perspective, this paper details several quantum algorithms that test the symmetry of quantum states and channels. For the case of testing Bose symmetry of a state, we show that there is a simple and efficient quantum algorithm, while the tests for other kinds of symmetry rely on the aid of a quantum prover. We prove that the acceptance probability of each algorithm is equal to the maximum symmetric fidelity of the state being tested, thus giving a firm operational meaning to these latter resource quantifiers. We evaluate the performance of these algorithms on a variety of inputs by using the variational approach to quantum algorithms, replacing the quantum prover with a quantum variational algorithm. We also show that the maximum symmetric fidelities can be calculated by semi-definite programs, which is useful for benchmarking the performance of these algorithms for sufficiently small examples. Finally, we establish various generalizations of the resource theory of asymmetry, with the upshot being that the acceptance probabilities of the algorithms are resource monotones and thus well motivated from the resource-theoretic perspective. |
Monday, March 6, 2023 12:54PM - 1:06PM |
B64.00008: Error mitigated parity quantum optimization Glen Bigan Mbeng, Anita Weidinger, Wolfgang Lechner The LHZ/parity architecture can encode industrial-relevant optimization problems on near-term quantum devices with fully programmable planar chips. However, running quantum optimization algorithms on the LHZ/parity architecture still requires developing error mitigation techniques to cope with hardware decoherence and dephasing processes. We propose a novel approach that exploits the architecture's intrinsic structure to mitigate bit-flip errors. We present numerical simulations of the quantum approximate optimization algorithm (QAOA), suggesting that our error mitigation scheme will significantly enhance the algorithm's performance on noisy quantum hardware. |
Monday, March 6, 2023 1:06PM - 1:18PM |
B64.00009: Variational algorithms for quantum dynamics with short depth quantum circuits Md Faisal Alam, Bryan K Clark Quantum dynamics is the quintessential application of quantum computers. The naive approach to quantum dynamics requires quantum circuits of depth that scales linearly with the duration of time evolution. However, near-term quantum computers suffer from short coherence time and gate infidelities, which limit the depth of the circuits they can reliably run. Under the assumption of a fixed depth budget, it is interesting to ask what quantum algorithm is best suited to maximizing fidelity with the exactly evolved state. In this work we develop algorithmic approaches to this problem and explore the various trade-offs between the quantum resources involved. We further benchmark these approaches on various model systems. |
Monday, March 6, 2023 1:18PM - 1:30PM |
B64.00010: Variational Quantum Algorithms for Semidefinite Programming Dhrumil J Patel, Patrick J Coles, Mark M Wilde A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N >> M, where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings. |
Monday, March 6, 2023 1:30PM - 1:42PM |
B64.00011: Exploring the role of parameters in variational quantum algorithms Abhinav Anand, Sumner Alperin-Lea, Alexandre Choquette, Alán Aspuru-Guzik The prospect of achieving quantum advantage by running variational algorithms on near-term devices is very exciting. However many challenges remain before these near-term devices can be used reliably to solve different problems in different areas of science. In this talk, I will explain a way to analyze the impact of the parametrization in variational quantum algorithms (VQAs) on the size of the solution space spanned by their parameters. Focusing on quantum circuits whose structure is patterned on alternating unitaries, I will present a connection between VQAs and the theory of quantum control that has been recently established. I will show how our proposed analysis gives insight into the most efficient way to parametrize a quantum circuit in order to span a sector of interest in the Hilbert space. Finally, I will present some numerical results to show the improvements that can be made using the proposed analysis. |
Monday, March 6, 2023 1:42PM - 1:54PM |
B64.00012: Accurately Solving Linear Systems with Quantum Oracles Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi, Brandon Augustino, Tamás Terlaky, Giacomo Nannicini Quantum linear system algorithms (QLSA), w.r.t dimension, have the potential to solve linear systems (LSs) faster than classical methods. However, to extract the classical solution, a quantum tomography algorithm (QTA) is needed which increases both error and time complexity. To accurately and efficiently solve LSs using QLSA and QTA algorithms, we propose an Iterative Refinement method (IRM) which uses limited-precision quantum oracles iteratively to improve dependence on precision to logarithmic. The IRM is broadly applicable. We discuss its application in Quantum Interior Point Methods (QIPM) and discuss how the proposed IRM accelerates QIPMs. |
Follow Us |
Engage
Become an APS Member |
My APS
Renew Membership |
Information for |
About APSThe American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics. |
© 2024 American Physical Society
| All rights reserved | Terms of Use
| Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 20740-3844
(301) 209-3200
Editorial Office
100 Motor Pkwy, Suite 110, Hauppauge, NY 11788
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700