From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. (English) Zbl 1461.68085
Summary: The next few years will be exciting as prototype universal quantum processors emerge, enabling the implementation of a wider variety of algorithms. Of particular interest are quantum heuristics, which require experimentation on quantum hardware for their evaluation and which have the potential to significantly expand the breadth of applications for which quantum computers have an established advantage. A leading candidate is E. Farhi et al.’s [“A quantum approximate optimization algorithm”, Preprint, arXiv:1411.4028], which alternates between applying a cost function based Hamiltonian and a mixing Hamiltonian. Here, we extend this framework to allow alternation between more general families of operators. The essence of this extension, the quantum alternating operator ansatz, is the consideration of general parameterized families of unitaries rather than only those corresponding to the time evolution under a fixed local Hamiltonian for a time specified by the parameter. This ansatz supports the representation of a larger, and potentially more useful, set of states than the original formulation, with potential long-term impact on a broad array of application areas. For cases that call for mixing only within a desired subspace, refocusing on unitaries rather than Hamiltonians enables more efficiently implementable mixers than was possible in the original framework. Such mixers are particularly useful for optimization problems with hard constraints that must always be satisfied, defining a feasible subspace, and soft constraints whose violation we wish to minimize. More efficient implementation enables earlier experimental exploration of an alternating operator approach, in the spirit of the quantum approximate optimization algorithm, to a wide variety of approximate optimization, exact optimization, and sampling problems. In addition to introducing the quantum alternating operator ansatz, we lay out design criteria for mixing operators, detail mappings for eight problems, and provide a compendium with brief descriptions of mappings for a diverse array of problems.
MSC:
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
| 81P65 | Quantum gates |
| 81P68 | Quantum computation |
| 90C27 | Combinatorial optimization |
Keywords:
quantum computing; quantum gate model; quantum algorithms; quantum circuit ansatz; optimization; approximate optimization; constrained optimization; constraint satisfaction problemsReferences:
| [1] | Farhi, E.; Goldstone, J.; Gutmann, S.; A quantum approximate optimization algorithm; arXiv: 2014; . · Zbl 1213.68284 |
| [2] | Biswas, R.; Jiang, Z.; Kechezhi, K.; Knysh, S.; Mandrà, S.; O’Gorman, B.; Perdomo-Ortiz, A.; Petukhov, A.; Realpe-Gómez, J.; Rieffel, E.; A NASA perspective on quantum computing: Opportunities and challenges; Parallel Comput.: 2017; Volume 64 ,81-98. |
| [3] | Rieffel, E.G.; Venturelli, D.; O’Gorman, B.; Do, M.B.; Prystay, E.M.; Smelyanskiy, V.N.; A case study in programming a quantum annealer for hard operational planning problems; Quant. Inform. Process.: 2015; Volume 14 ,1-36. · Zbl 1311.81084 |
| [4] | Lucas, A.; Ising formulations of many NP problems; Front. Phys.: 2014; Volume 2 ,5. |
| [5] | Hadfield, S.; On the representation of Boolean and real functions as Hamiltonians for quantum computing; arXiv: 2018; . |
| [6] | Hen, I.; Spedalieri, F.M.; Quantum annealing for constrained optimization; Phys. Rev. Appl.: 2016; Volume 5 ,034007. |
| [7] | Hen, I.; Sarandy, M.S.; Driver Hamiltonians for constrained optimization in quantum annealing; Phys. Rev.: 2016; Volume 93 ,062312. |
| [8] | Rieffel, E.G.; Polak, W.; ; Quantum Computing: A Gentle Introduction: Cambridge, MA, USA 2011; . · Zbl 1221.81003 |
| [9] | IBM Q and Quantum Computing; ; . |
| [10] | Boixo, S.; Smelyanskiy, V.N.; Shabani, A.; Isakov, S.V.; Dykman, M.; Denchev, V.S.; Amin, M.H.; Smirnov, A.Y.; Mohseni, M.; Neven, H.; Computational multiqubit tunnelling in programmable quantum annealers; Nat. Commun.: 2016; Volume 7 ,10327. |
| [11] | Sete, E.A.; Zeng, W.J.; Rigetti, C.T.; A functional architecture for scalable quantum computing; Proceedings of the 2016 IEEE International Conference on Rebooting Computing (ICRC): ; ,1-6. |
| [12] | Mohseni, M.; Read, P.; Neven, H.; Boixo, S.; Denchev, V.; Babbush, R.; Fowler, A.; Smelyanskiy, V.; Martinis, J.; Commercialize quantum technologies in five years; Nature: 2017; Volume 543 ,171-174. |
| [13] | Debnath, S.; Linke, N.; Figgatt, C.; Landsman, K.; Wright, K.; Monroe, C.; Demonstration of a small programmable quantum computer with atomic qubits; Nature: 2016; Volume 536 ,63-66. |
| [14] | Saffman, M.; Quantum computing with atomic qubits and Rydberg interactions: progress and challenges; J. Phys. B Atom. Mol. Opt. Phys.: 2016; Volume 49 ,202001. |
| [15] | Zahedinejad, E.; Zaribafiyan, A.; Combinatorial optimization on gate model quantum computers: A survey; arXiv: 2017; . |
| [16] | Farhi, E.; Goldstone, J.; Gutmann, S.; A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem; arXiv: 2014; . · Zbl 1213.68284 |
| [17] | Farhi, E.; Harrow, A.W.; Quantum supremacy through the quantum approximate optimization algorithm; arXiv: 2016; . |
| [18] | Yang, Z.C.; Rahmani, A.; Shabani, A.; Neven, H.; Chamon, C.; Optimizing variational quantum algorithms using Pontryagin’s minimum principle; Phys. Rev. X: 2017; Volume 7 ,021027. |
| [19] | Jiang, Z.; Rieffel, E.G.; Wang, Z.; Near-optimal quantum circuit for Grover’s unstructured search using a transverse field; Phys. Rev. A: 2017; Volume 95 ,062317. |
| [20] | Wecker, D.; Hastings, M.B.; Troyer, M.; Training a quantum optimizer; Phys. Rev. A: 2016; Volume 94 ,022309. |
| [21] | Wang, Z.; Hadfield, S.; Jiang, Z.; Rieffel, E.G.; Quantum approximate optimization algorithm for MaxCut: A fermionic view; Phys. Rev. A: 2018; Volume 97 ,022304. |
| [22] | Venturelli, D.; Do, M.; Rieffel, E.; Frank, J.; Compiling quantum circuits to realistic hardware architectures using temporal planners; Quantum Sci. Tech.: 2018; Volume 3 ,025004. |
| [23] | Barak, B.; Moitra, A.; O’Donnell, R.; Raghavendra, P.; Regev, O.; Steurer, D.; Trevisan, L.; Vijayaraghavan, A.; Witmer, D.; Wright, J.; Beating the random assignment on constraint satisfaction problems of bounded degree; arXiv: 2015; . · Zbl 1375.68102 |
| [24] | Hadfield, S.; Wang, Z.; Rieffel, E.G.; O’Gorman, B.; Venturelli, D.; Biswas, R.; Quantum Approximate Optimization with Hard and Soft Constraints; Proceedings of the Second International Workshop on Post Moores Era Supercomputing: New York, NY, USA 2017; ,15-21. |
| [25] | Fingerhuth, M.; Babej, T.; Ing, C.; A quantum alternating operator ansatz with hard and soft constraints for lattice protein folding; arXiv: 2018; . |
| [26] | Farhi, E.; Goldstone, J.; Gutmann, S.; Neven, H.; Quantum algorithms for fixed qubit architectures; arXiv: 2017; . |
| [27] | Lechner, W.; Quantum approximate optimization with parallelizable gates; arXiv: 2018; . |
| [28] | Ho, W.W.; Hsieh, T.H.; Efficient preparation of non-trivial quantum states using the quantum approximate optimization algorithm; arXiv: 2019; . |
| [29] | Verdon, G.; Broughton, M.; Biamonte, J.; A quantum algorithm to train neural networks using low-depth circuits; arXiv: 2017; . |
| [30] | Otterbach, J.; Manenti, R.; Alidoust, N.; Bestwick, A.; Block, M.; Bloom, B.; Caldwell, S.; Didier, N.; Fried, E.S.; Hong, S.; Unsupervised machine learning on a hybrid quantum computer; arXiv: 2017; . |
| [31] | Marsh, S.; Wang, J.; A quantum walk-assisted approximate algorithm for bounded NP optimisation problems; Quant. Inform. Process.: 2019; Volume 18 ,61. · Zbl 1417.81095 |
| [32] | Lloyd, S.; Quantum approximate optimization is computationally universal; arXiv: 2018; . |
| [33] | Guerreschi, G.G.; Smelyanskiy, M.; Practical optimization for hybrid quantum-classical algorithms; arXiv: 2017; . |
| [34] | McClean, J.R.; Boixo, S.; Smelyanskiy, V.N.; Babbush, R.; Neven, H.; Barren plateaus in quantum neural network training landscapes; arXiv: 2018; . |
| [35] | Booth, K.E.C.; Do, M.; Beck, J.C.; Rieffel, E.; Venturelli, D.; Frank, J.; Comparing and integrating constraint programming and temporal planning for quantum circuit compilation; arXiv: 2018; . |
| [36] | Gottesman, D.; Kitaev, A.; Preskill, J.; Encoding a qubit in an oscillator; Phys. Rev. A: 2001; Volume 64 ,012310. |
| [37] | Bartlett, S.D.; de Guise, H.; Sanders, B.C.; Quantum encodings in spin systems and harmonic oscillators; Phys. Rev. A: 2002; Volume 65 ,052316. |
| [38] | Verstraete, F.; Cirac, J.I.; Latorre, J.I.; Quantum circuits for strongly correlated quantum systems; Phys. Rev. A: 2009; Volume 79 ,032316. |
| [39] | Chow, J.M.; Quantum Information Processing with Superconducting Qubits; Ph.D. Thesis: London, UK 2010; . |
| [40] | Soifer, A.; ; The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators: Berlin, Germany 2008; . · Zbl 1221.05001 |
| [41] | Zuckerman, D.; On unapproximable versions of NP-complete problems; SIAM J. Comput.: 1996; Volume 25 ,1293-1304. · Zbl 0864.68039 |
| [42] | Papadimitriou, C.H.; ; Computational Complexity: Hoboken, NJ, USA 1994; . · Zbl 0833.68049 |
| [43] | Yato, T.; Seta, T.; Complexity and completeness of finding another solution and its application to puzzles; IEICE Trans. Fund. Electron. Commun. Comput. Sci.: 2003; Volume 86 ,1052-1060. |
| [44] | Ueda, N.; Nagao, T.; NP-Completeness Results for NONOGRAM via Parsimonious Reductions; ; . |
| [45] | Bremner, M.J.; Jozsa, R.; Shepherd, D.J.; Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy; Proc. R. Soc. Lond. Math. Phys. Sci.: 2010; Volume 467 . · Zbl 1219.81071 |
| [46] | Li, G.; Ding, Y.; Xie, Y.; Tackling the qubit mapping problem for NISQ-Era quantum devices; arXiv: 2018; . |
| [47] | Bremner, M.J.; Montanaro, A.; Shepherd, D.J.; Average-case complexity versus approximate simulation of commuting quantum computations; Phys. Rev. Lett.: 2016; Volume 117 ,080501. |
| [48] | Bremner, M.J.; Montanaro, A.; Shepherd, D.J.; Achieving quantum supremacy with sparse and noisy commuting quantum computations; Quantum: 2017; Volume 1 ,8. |
| [49] | Trevisan, L.; Inapproximability of combinatorial optimization problems; Paradigms of Combinatorial Optimization: Hoboken, NJ, USA 2014; ,381-434. · Zbl 1204.90088 |
| [50] | Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti-Spaccamela, A.; Protasi, M.; ; Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties: Berlin, Germany 2012; . · Zbl 0937.68002 |
| [51] | Papadimitriou, C.; Yannakakis, M.; Optimization, approximation, and complexity classes; J. Comput. Syst. Sci.: 1991; Volume 43 ,425-440. · Zbl 0765.68036 |
| [52] | Khanna, S.; Motwani, R.; Sudan, M.; Vazirani, U.; On syntactic versus computational views of approximability; SIAM J. Comput.: 1998; Volume 28 ,164-191. · Zbl 0915.68068 |
| [53] | Håstad, J.; Some optimal inapproximability results; J. ACM: 2001; Volume 48 ,798-859. · Zbl 1127.68405 |
| [54] | Goemans, M.X.; Williamson, D.P.; Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming; J. ACM: 1995; Volume 42 ,1115-1145. · Zbl 0885.68088 |
| [55] | Khot, S.; Kindler, G.; Mossel, E.; O’Donnell, R.; Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?; SIAM J. Comput.: 2007; Volume 37 ,319-357. · Zbl 1135.68019 |
| [56] | Feige, U.; Karpinski, M.; Langberg, M.; Improved approximation of Max-Cut on graphs of bounded degree; J. Algorithms: 2002; Volume 43 ,201-219. · Zbl 1050.68110 |
| [57] | Lewin, M.; Livnat, D.; Zwick, U.; Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems; Proceedings of the International Conference on Integer Programming and Combinatorial Optimization: Berlin, Germany 2002; ,67-82. · Zbl 1049.90535 |
| [58] | Karloff, H.; Zwick, U.; A 7/8-approximation algorithm for MAX 3SAT?; Proceedings of the 38th Annual Symposium on Foundations of Computer Science: ; ,406-415. |
| [59] | Kohli, R.; Krishnamurti, R.; Mirchandani, P.; The minimum satisfiability problem; SIAM J. Discrete Math.: 1994; Volume 7 ,275-283. · Zbl 0806.68060 |
| [60] | Dinur, I.; Safra, S.; The importance of being biased; Proceedings of the 34th Annual ACM Symposium on the Theory of Computing: ; ,33-42. · Zbl 1192.68318 |
| [61] | Avidor, A.; Zwick, U.; Approximating MIN 2-SAT and MIN 3-SAT; Theor. Comput. Syst.: 2005; Volume 38 ,329-345. · Zbl 1101.68603 |
| [62] | Bertsimas, D.; Teo, C.; Vohra, R.; On dependent randomized rounding algorithms; Oper. Res. Lett.: 1999; Volume 24 ,105-114. · Zbl 0954.90025 |
| [63] | Andersson, G.; Engebretsen, L.; Better approximation algorithms for set splitting and Not-All-Equal SAT; Inform. Process. Lett.: 1998; Volume 65 ,305-311. · Zbl 1338.68286 |
| [64] | Zwick, U.; Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint; Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms: ; ,201-210. · Zbl 0930.68142 |
| [65] | Petrank, E.; The hardness of approximation: Gap location; Comput. Complex.: 1994; Volume 4 ,133-157. · Zbl 0822.68052 |
| [66] | Zhang, J.; Ye, Y.; Han, Q.; Improved approximations for max set splitting and max NAE SAT; Discrete Appl. Math.: 2004; Volume 142 ,133-149. · Zbl 1122.68154 |
| [67] | Lovász, L.; Coverings and colorings of hypergraphs; Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing: Winnipeg, MB, Canada 1973; ,3-12. · Zbl 0322.05114 |
| [68] | Guruswami, V.; Inapproximability results for set splitting and satisfiability problems with no mixed clauses; Algorithmica: 2004; Volume 38 ,451-469. · Zbl 1095.68036 |
| [69] | Bazgan, C.; Escoffier, B.; Paschos, V.T.; Completeness in standard and differential approximation classes: Poly-(D) APX-and (D) PTAS-completeness; Theor. Comput. Sci.: 2005; Volume 339 ,272-292. · Zbl 1068.68063 |
| [70] | Boppana, R.; Halldórsson, M.M.; Approximating maximum independent sets by excluding subgraphs; BIT Numer. Math.: 1992; Volume 32 ,180-196. · Zbl 0761.68044 |
| [71] | Zuckerman, D.; Linear degree extractors and the inapproximability of max clique and chromatic number; Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing: ; ,681-690. · Zbl 1301.68152 |
| [72] | Karakostas, G.; A better approximation ratio for the vertex cover problem; ACM Trans. Algorithms: 2009; Volume 5 ,41. · Zbl 1298.68295 |
| [73] | Dinur, I.; Safra, S.; On the hardness of approximating minimum vertex cover; Ann. Math.: 2005; Volume 162 ,439-485. · Zbl 1084.68051 |
| [74] | Marathe, M.V.; Ravi, S.; On approximation algorithms for the minimum satisfiability problem; Inform. Process. Lett.: 1996; Volume 58 ,23-29. · Zbl 0875.68544 |
| [75] | Hazan, E.; Safra, S.; Schwartz, O.; On the complexity of approximating k-set packing; Comput. Complex.: 2006; Volume 15 ,20-39. · Zbl 1103.90105 |
| [76] | Halldórsson, M.M.; Kratochvıl, J.; Telle, J.A.; Independent sets with domination constraints; Discrete Appl. Math.: 2000; Volume 99 ,39-54. · Zbl 0939.05063 |
| [77] | Johnson, D.S.; Approximation algorithms for combinatorial problems; Proceedings of the Fifth Annual ACM Symposium on Theory of Computing: ; ,38-49. · Zbl 0316.68024 |
| [78] | Dinur, I.; Steurer, D.; Analytical approach to parallel repetition; Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing: New York, NY, USA 2014; ,624-633. · Zbl 1315.91001 |
| [79] | Frieze, A.; Jerrum, M.; Improved approximation algorithms for MAXk-CUT and MAX BISECTION; Algorithmica: 1997; Volume 18 ,67-81. · Zbl 0873.68078 |
| [80] | Krauthgamer, R.; Feige, U.; A polylogarithmic approximation of the minimum bisection; SIAM Rev.: 2006; Volume 48 ,99-130. · Zbl 1088.05068 |
| [81] | Panconesi, A.; Ranjan, D.; Quantifiers and approximation; Proceedings of the 22nd Annual ACM Symposium on Theory of Computing: ; ,446-456. · Zbl 0783.68045 |
| [82] | Halldórsson, M.M.; Approximating Discrete Collections via Local Improvements; Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms: ; ,160-169. · Zbl 0847.90136 |
| [83] | Halldórsson, M.M.; A still better performance guarantee for approximate graph coloring; Inform. Process. Lett.: 1993; Volume 45 ,19-23. · Zbl 0768.68043 |
| [84] | Nishizeki, T.; Kashiwagi, K.; On the 1.1 edge-coloring of multigraphs; SIAM J. Discrete Math.: 1990; Volume 3 ,391-410. · Zbl 0702.05036 |
| [85] | Lund, C.; Yannakakis, M.; On the hardness of approximating minimization problems; J. ACM: 1994; Volume 41 ,960-981. · Zbl 0814.68064 |
| [86] | Orponen, P.; Mannila, H.; On Approximation Preserving Reductions: Complete Problems and Robust Measures (Revised Version); ; . |
| [87] | Papadimitriou, C.H.; Yannakakis, M.; The traveling salesman problem with distances one and two; Math. Oper. Res.: 1993; Volume 18 ,1-11. · Zbl 0778.90057 |
| [88] | Christofides, N.; ; Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem: Pittsburgh, PA, USA 1976; . · Zbl 1489.90150 |
| [89] | Schaller, J.; Valente, J.M.; Minimizing the weighted sum of squared tardiness on a single machine; Comput. Oper. Res.: 2012; Volume 39 ,919-928. · Zbl 1251.90185 |
| [90] | Cheng, T.E.; Ng, C.; Yuan, J.; Liu, Z.; Single machine scheduling to minimize total weighted tardiness; Eur. J. Oper. Res.: 2005; Volume 165 ,423-443. · Zbl 1066.90025 |
| [91] | Lenstra, J.K.; Kan, A.R.; Brucker, P.; Complexity of machine scheduling problems; Ann. Discrete Math.: 1977; Volume 1 ,343-362. · Zbl 0353.68067 |
| [92] | Goemans, M.X.; Queyranne, M.; Schulz, A.S.; Skutella, M.; Wang, Y.; Single machine scheduling with release dates; SIAM J. Discrete Math.: 2002; Volume 15 ,165-192. · Zbl 1009.90096 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
