Behavior of Analog Quantum Algorithms

Published on Jul 2, 2021in arXiv: Quantum Physics
Lucas T. Brady11
Estimated H-index: 11
Lucas Kocia7
Estimated H-index: 7
+ 3 AuthorsAlexey V. Gorshkov55
Estimated H-index: 55
Analog quantum algorithms are formulated in terms of Hamiltonians rather than unitary gates and include quantum adiabatic computing, quantum annealing, and the quantum approximate optimization algorithm (QAOA). These algorithms are promising candidates for near-term quantum applications, but they often require fine tuning via the annealing schedule or variational parameters. In this work, we explore connections between these analog algorithms, as well as limits in which they become approximations of the optimal procedure.Notably, we explore how the optimal procedure approaches a smooth adiabatic procedure but with a superposed oscillatory pattern that can be explained in terms of the interactions between the ground state and first excited state that effect the coherent error cancellation of diabatic transitions. Furthermore, we provide numeric and analytic evidence that QAOA emulates this optimal procedure with the length of each QAOA layer equal to the period of the oscillatory pattern. Additionally, the ratios of the QAOA bangs are determined by the smooth, non-oscillatory part of the optimal procedure. We provide arguments for these phenomena in terms of the product formula expansion of the optimal procedure. With these arguments, we conclude that different analog algorithms can emulate the optimal protocol under different limits and approximations. Finally, we present a new algorithm for better approximating the optimal protocol using the analytic and numeric insights from the rest of the paper. In practice, numerically, we find that this algorithm outperforms standard QAOA and naive quantum annealing procedures.
馃摉 Papers frequently viewed together
#1Matthew P. Harrigan (Google)H-Index: 14
#2Kevin J. Sung (UM: University of Michigan)H-Index: 4
Last. Sergio Boixo (Google)H-Index: 45
view all 86 authors...
Faster algorithms for combinatorial optimization could prove transformative for diverse areas such as logistics, finance and machine learning. Accordingly, the possibility of quantum enhanced optimization has driven much interest in quantum technologies. Here we demonstrate the application of the Google Sycamore superconducting qubit quantum processor to combinatorial optimization problems with the quantum approximate optimization algorithm (QAOA). Like past QAOA experiments, we study performanc...
#1Itay Hen (SC: University of Southern California)H-Index: 23
In classical computing, analog approaches have sometimes appeared to be more powerful than they really are. This occurs when resources, particularly precision, are not appropriately taken into account. While the same should also hold for analog quantum computing, precision issues are often neglected from the analysis. In this work, we present a classical analog algorithm for unstructured search that can be viewed as analogous to the quantum adiabatic unstructured search algorithm devised by Rola...
#1John Preskill (Caltech: California Institute of Technology)H-Index: 68
Noisy Intermediate-Scale Quantum (NISQ) technology will be available in the near future. Quantum computers with 50-100 qubits may be able to perform tasks which surpass the capabilities of today's classical digital computers, but noise in quantum gates will limit the size of quantum circuits that can be executed reliably. NISQ devices will be useful tools for exploring many-body quantum physics, and may have other useful applications, but the 100-qubit quantum computer will not change the world ...
I describe how real quantum annealers may be used to perform local (in state space) searches around specified states, rather than the global searches traditionally implemented in the quantum annealing algorithm (QAA). Such protocols will have numerous advantages over simple quantum annealing. By using such searches the effect of problem mis-specification can be reduced, as only energy differences between the searched states will be relevant. The QAA is an analogue of simulated annealing, a class...
For a general quantum system driven by a slowly time-dependent Hamiltonian, transitions between instantaneous eigenstates are exponentially weak. But a nearby Hamiltonian exists for which the transition amplitudes between any eigenstates of the original Hamiltonian are exactly zero for all values of slowness. The general theory is illustrated by spins driven by changing magnetic fields, and implies that any spin expectation history, including those where the spin never precesses, can be generate...
The adiabatic theorem provides the basis for the adiabatic model of quantum computation. Recently the conditions required for the adiabatic theorem to hold have become a subject of some controversy. Here we show that the reported violations of the adiabatic theorem all arise from resonant transitions between energy levels. In the absence of fast driven oscillations the traditional adiabatic theorem holds. Implications for adiabatic quantum computation are discussed.
#1Richard BellmanH-Index: 85
#2L. S. PontryaginH-Index: 8
Last. Lucien W. NeustadtH-Index: 9
view all 7 authors...
Cited By2
#1Ryan LaRoseH-Index: 9
#2Eleanor RieffelH-Index: 29
Last. Davide VenturelliH-Index: 21
view all 3 authors...
We introduce multiple parametrized circuit ansatze and present the results of a numerical study comparing their performance with a standard Quantum Alternating Operator Ansatz approach. The ansatze are inspired by mixing and phase separation in the QAOA, and also motivated by compilation considerations with the aim of running on near-term superconducting quantum processors. The methods are tested on random instances of a weighted quadratic binary constrained optimization problem that is fully co...
#1Changhao Yi (UNM: University of New Mexico)H-Index: 1
The simulation of adiabatic evolution has deep connections with Adiabatic Quantum Computation, the Quantum Approximate Optimization Algorithm and adiabatic state preparation. Here we address the error analysis problem in quantum simulation of adiabatic process using Trotter formulas. We show that with additional conditions, the circuit depth can be linear in simulation time T The improvement comes from the observation that the fidelity error here can't be estimated by the norm distance betwee...
This website uses cookies.
We use cookies to improve your online experience. By continuing to use our website we assume you agree to the placement of these cookies.
To learn more, you can find in our Privacy Policy.