Quantum procedures for approximate optimization by quenching
In this disclosure, example quantum algorithms for approximate optimization based on a sudden quench of a Hamiltonian. While the algorithm is general, it is analyzed in this disclosure in the specific context of MAX-EK-LIN2, for both even and odd K. It is to be understood, however, that the algorithm can be generalized to other contexts. A duality can be found: roughly, either the algorithm provides some nontrivial improvement over random or there exist many solutions which are significantly worse than random. A classical approximation algorithm is then analyzed and a similar duality is found, though the quantum algorithm provides additional guarantees in certain cases.
1. A method, comprising:
configuring a quantum computing device to perform an approximate optimization technique to approximate a solution to a combinatorial optimization problem; and
performing the approximate optimization technique on the quantum computing device,
wherein the approximate optimization technique includes using a quantum quench algorithm.
2. The method of claim 1 , wherein the quench algorithm includes averaging state values over a plurality of times.
3. The method of claim 1 , wherein the approximate optimization technique comprises:
changing coupling constants without using a jump or slow change in the coupling constants.
4. The method of claim 3 , wherein the changing coupling constants is performed non-adiabatically.
5. The method of claim 3 , wherein the changing of the coupling constants is followed by an equilibration time.
6. The method of claim 1 , further comprising:
reading out results of the approximate optimization technique from the quantum computing device; and
storing the results in a classical computing device.
7. A system, comprising:
a classical computer; and
a quantum computer,
wherein the quantum computing device is configured to perform an approximate optimization technique on the quantum computing device to approximate a solution to a combinatorial optimization problem,
wherein the approximate optimization technique includes using a quantum quench algorithm.
8. The system of claim 7 , wherein the quench algorithm includes averaging state values over a plurality of times.
9. The system of claim 7 , wherein the approximate optimization technique comprises changing coupling constants without using a jump or slow change in the coupling constants.
10. The system of claim 9 , wherein the changing coupling constants is performed non-adiabatically.
11. The system of claim 9 , wherein the changing of the coupling constants is followed by an equilibration time.
12. The system of claim 9 , wherein the classical computer is further configured to:
read out results of the approximate optimization technique from the quantum computing device; and
store the results in a classical computing device.
13. One or more computer-readable media storing computer-executable instructions, which when executed by a classical computing device, cause the classical computing device to perform a method, the method comprising:
configuring a quantum computing device to perform an approximate optimization technique to approximate a solution to a combinatorial optimization problem; and
performing the approximate optimization technique on the quantum computing device,
wherein the approximate optimization technique includes using a quantum quench algorithm.
14. The one or more computer-readable media of claim 13 , wherein the quench algorithm includes averaging state values over a plurality of times.
15. The one or more computer-readable media of claim 13 , wherein the approximate optimization technique comprises:
changing coupling constants without using a jump or slow change in the coupling constants.
16. The one or more computer-readable media of claim 15 , wherein the changing coupling constants is performed non-adiabatically.
17. The one or more computer-readable media of claim 15 , wherein the changing of the coupling constants is followed by an equilibration time.
18. The one or more computer-readable media of claim 13 , further comprising:
reading out results of the approximate optimization technique from the quantum computing device; and
storing the results.
19. A method, comprising
performing, on a classical computing device, a quantum quench algorithm using simulation of a quantum Hamiltonian to perform approximate optimization, wherein the quench algorithm includes averaging state values over a plurality of times.