Journal
QUANTUM SCIENCE AND TECHNOLOGY
Volume 7, Issue 1, Pages -Publisher
IOP Publishing Ltd
DOI: 10.1088/2058-9565/ac16b8
Keywords
quantum computation; adiabatic quantum computing; complexity theory; quantum algorithms; optimization theory
Funding
- Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA)
- Defense Advanced Research Projects Agency (DARPA), via the US Army Research Office [W911NF-17-C-0050]
Ask authors/readers for more resources
Recent advances in adiabatic quantum computing and quantum annealing have focused on using advanced and novel Hamiltonian representations to solve optimization problems. A significant advancement has been the development of driver Hamiltonians that can commute with the constraints of an optimization problem, providing an alternative method for satisfying those constraints. However, the design of successful driver Hamiltonians for multiple constraints currently relies on specific problem intuition and there is no simple general algorithm for generating them.
Recent advances in the field of adiabatic quantum computing and the closely related field of quantum annealing have centered around using more advanced and novel Hamiltonian representations to solve optimization problems. One of these advances has centered around the development of driver Hamiltonians that commute with the constraints of an optimization problem-allowing for another avenue to satisfying those constraints instead of imposing penalty terms for each of them. In particular, the approach is able to use sparser connectivity to embed several practical problems on quantum devices in comparison to the standard approach of using penalty terms. However, designing the driver Hamiltonians that successfully commute with several constraints has largely been based on strong intuition for specific problems and with no simple general algorithm for generating them for arbitrary constraints. In this work, we develop a simple and intuitive algebraic framework for reasoning about the commutation of Hamiltonians with linear constraints-one that allows us to classify the complexity of finding a driver Hamiltonian for an arbitrary set of linear constraints as NP-complete. Because unitary operators are exponentials of Hermitian operators, these results can also be applied to the construction of mixers in the quantum alternating operator ansatz framework.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available