mixers: Analytical and numerical results for the quantum alternating operator ansatz
- 14 January 2020
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 101 (1) , 012320
Abstract
The quantum alternating operator ansatz (QAOA) is a promising gate-model metaheuristic for combinatorial optimization. Applying the algorithm to problems with constraints presents an implementation challenge for near-term quantum resources. This paper explores strategies for enforcing hard constraints by using Hamiltonians as mixing operators (mixers). Despite the complexity of simulating the model, we demonstrate that, for an integer variable admitting discrete values represented through one-hot encoding, certain classes of the mixer Hamiltonian can be implemented without Trotter error in depth . We also specify general strategies for implementing QAOA circuits on all-to-all connected hardware graphs and linearly connected hardware graphs inspired by fermionic simulation techniques. Performance is validated on graph-coloring problems that are known to be challenging for a given classical algorithm. The general strategy of using mixers is borne out numerically, demonstrating a significant improvement over the general mixer, and moreover the generalized state yields better performance than easier-to-generate classical initial states when mixers are used.
Keywords
All Related Versions
Funding Information
- Ames Research Center
- Air Force Research Laboratory (F4HBKC4162G00)
This publication has 25 references indexed in Scilit:
- Fourier Transform for Fermionic Systems and the Spectral Tensor NetworkPhysical Review Letters, 2014
- Efficient quantum algorithm for preparing molecular-system-like states on a quantum computerPhysical Review A, 2009
- Quantum circuits for strongly correlated quantum systemsPhysical Review A, 2009
- Sequential generation of matrix-product states in cavity QEDPhysical Review A, 2007
- Perfect State Transfer in Quantum Spin NetworksPhysical Review Letters, 2004
- Reversible arithmetic coding for quantum data compressionIEEE Transactions on Information Theory, 2000
- Schumacher’s quantum data compression as a quantum computationPhysical Review A, 1996
- Statistical Mechanics of theModel. IPhysical Review A, 1970
- Two soluble models of an antiferromagnetic chainAnnals of Physics, 1961
- ber das Paulische quivalenzverbotThe European Physical Journal A, 1928