Fetching the paper…

Reading the bibliography…

2019

The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover

Cook, Jeremy, Eidenbenz, Stephan, Bärtschi, Andreas

Original
PDF
Post on X

Understand

The Quantum Alternating Operator Ansatz is a generalization of the Quantum Approximate Optimization Algorithm (QAOA) designed for finding approximate solutions to combinatorial optimization problems with hard constraints.

In this paper, we study Maximum $k$-Vertex Cover under this ansatz due to its modest complexity, while still being more complex than the well studied problems of Max-Cut and Max E3-LIN2.
Our approach includes (i) a performance comparison between easy-to-prepare classical states and Dicke states as starting states, (ii) a performance comparison between two $XY$-Hamiltonian mixing operators: the ring mixer and the complete graph mixer, (iii) an analysis of the distribution of solutions via Monte Carlo sampling, and (iv) the exploration of efficient angle selection strategies.
Our results are: (i) Dicke states improve performance compared to easy-to-prepare classical states, (ii) an upper bound on the simulation of the complete graph mixer, (iii) the complete graph mixer improves performance relative to the ring mixer, (iv) numerical results indicating the standard deviation of the distribution of solutions decreases exponentially in $p$ (the number of rounds in the algorithm), requiring an exponential number of random samples to find a better solution in the next round, and (v) a correlation of angle parameters which exhibit high quality solutions that behave similarly to a discretized version of the Quantum Adiabatic Algorithm.

The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover · Around

Built on

G. B. Mbeng, R. Fazio, and G. Santoro, “Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes,” arXiv e-prints , 2019, arXiv:1906.08948
Original
1906
Earlier work this paper cites.
M. Hodson, B. Ruck, H. Ong, D. Garvin, and S. Dulman, “Portfolio rebalancing experiments using the Quantum Alternating Operator Ansatz,” arXiv e-prints , 2019, arXiv:1911.05296
Original
1911
Earlier work this paper cites.
E. Petrank, “The hardness of approximation: Gap location,” Computational Complexity , vol. 4, no. 2, pp. 133–157, 1994, doi:10.1007/BF01202286
1994
Earlier work this paper cites.
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, “A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem,” Science , vol. 292, no. 5516, pp. 472–475, 2001, doi:10.1126/science.1057726
2001
Earlier work this paper cites.
M. Mosca and P. Kaye, “Quantum Networks for Generating Arbitrary Quantum States,” in Optical Fiber Communication Conference and International Conference on Quantum Information ICQI , Jun 2001, p. PB28, doi:10.1364/ICQI.2001.PB28
2001
Earlier work this paper cites.
S. Khot, “On the Power of Unique 2-Prover 1-Round Games,” in 34th Annual ACM Symposium on Theory of Computing, STOC’02 , 2002, pp. 767–775, doi:10.1145/509907.510017
2002
Earlier work this paper cites.
A. M. Childs, E. Farhi, J. Goldstone, and S. Gutmann, “Finding cliques by quantum adiabatic evolution,” Quantum Information & Computation , vol. 2, no. 3, pp. 181–191, Apr 2002, doi:10.26421/QIC2.3
2002
Earlier work this paper cites.
L. T. Brady, C. L. Baldwin, A. Bapat, Y. Kharkov, and A. V. Gorshkov, “Optimal Protocols in Quantum Annealing and QAOA Problems,” arXiv e-prints , 2020, arXiv:2003.08952
Original
2003
Earlier work this paper cites.
A. Arrasmith, L. Cincio, R. D. Somma, and P. J. Coles, “Operator Sampling for Shot-frugal Optimization in Variational Algorithms,” arXiv e-prints , 2020, arXiv:2004.06252
Original
2004
Earlier work this paper cites.
L. K. Grover, “Fixed-Point Quantum Search,” Physical Review Letters , vol. 95, no. 15, p. 150501, 2005, doi:10.1103/PhysRevLett.95.150501
2005
Earlier work this paper cites.
Y. Zhang, R. Zhang, and A. C. Potter, “QED driven QAOA for network-flow optimization,” arXiv e-prints , 2020, arXiv:2006.09418
Original
2006
Earlier work this paper cites.

Similar

A. Bärtschi and S. Eidenbenz, “Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation,” in IEEE International Conference on Quantum Computing & Engineering, QCE’20 , 2020, arXiv:2006.00354
Original
2006
Cited alongside, same era.
H. Wang, S. Ashhab, and F. Nori, “Efficient quantum algorithm for preparing molecular-system-like states on a quantum computer,” Physical Review A , vol. 79, no. 4, p. 042335, 2009, doi:10.1103/PhysRevA.79.042335
2009
Cited alongside, same era.
D. W. Berry and A. M. Childs, “Black-Box Hamiltonian Simulation and Unitary Implementation,” Quantum Information & Computation , vol. 12, no. 1–2, pp. 29–62, 2012, doi:10.26421/QIC12.1-2
2012
Cited alongside, same era.
B. Olson, I. Hashmi, K. Molloy, and A. Shehu, “Basin Hopping as a General and Versatile Optimization Framework for the Characterization of Biological Macromolecules,” Advances in Artificial Intelligence , vol. 2012, p. 674832, 2012, doi:10.1155/2012/674832
2012

Then

Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, “Quantum approximate optimization algorithm for MaxCut: A fermionic view,” Physical Review A , vol. 97, p. 022304, 2018, doi:10.1103/PhysRevA.97.022304
2018
Later among the works it cites.
G. E. Crooks, “Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem,” arXiv e-prints , 2018, arXiv:1811.08419
Original
2018
Later among the works it cites.
S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, “From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz,” Algorithms , vol. 12, no. 2, p. 34, 2019, doi:10.3390/a12020034
2019
Closest in time.
P. Manurangsi, “A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation,” in 2nd Symposium on Simplicity in Algorithms, SOSA’19 , ser. OASICS, vol. 69, 2019, pp. 15:1–15:21, doi:10.4230/OASIcs.SOSA.2019.15
2019

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Cited alongside, same era.

E. Farhi, J. Goldstone, and S. Gutmann, “A Quantum Approximate Optimization Algorithm,” arXiv e-prints , 2014, arXiv:1411.4028

2014

Cited alongside, same era.

——, “A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem,” arXiv e-prints , 2014, arXiv:1412.6062

2014

Cited alongside, same era.

T. J. Yoder, G. H. Low, and I. L. Chuang, “Fixed-Point Quantum Search with an Optimal Number of Queries,” Physical Review Letters , vol. 113, no. 21, p. 210501, 2014, doi:10.1103/PhysRevLett.113.210501

2014

Cited alongside, same era.

B. Barak, A. Moitra, R. O’Donnell, P. Raghavendra, O. Regev, D. Steurer, L. Trevisan, A. Vijayaraghavan, D. Witmer, and J. Wright, “Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree,” in International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX’15 , ser. LIPICS, vol. 40, 2015, pp. 110–123, doi:10.4230/LIPIcs.APPROX-RANDOM.2015.110

2015

Cited alongside, same era.

Z.-C. Yang, A. Rahmani, A. Shabani, H. Neven, and C. Chamon, “Optimizing Variational Quantum Algorithms Using Pontryagin’s Minimum Principle,” Physical Review X , vol. 7, no. 2, p. 021027, 2017, doi:10.1103/physrevx.7.021027

2017

Cited alongside, same era.

M. Fingerhuth, T. Babej et al. , “A quantum alternating operator ansatz with hard and soft constraints for lattice protein folding,” arXiv e-prints , 2018, arXiv:1810.13411

2018

Cited alongside, same era.

A. E. Brouwer, S. M. Cioabă, F. Ihringer, and M. McGinnis, “The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters,” Journal of Combinatorial Theory, Series B , vol. 133, pp. 88–121, 2018, doi:10.1016/j.jctb.2018.04.005

2018

Cited alongside, same era.

Closest in time.

A. Bärtschi and S. Eidenbenz, “Deterministic Preparation of Dicke States,” in 22nd International Symposium on Fundamentals of Computation Theory, FCT’19 , 2019, pp. 126–139, doi:10.1007/978-3-030-25027-0_9

2019

Closest in time.

D. Cruz, R. Fournier, F. Gremion, A. Jeannerot, K. Komagata, T. Tosic, J. Thiesbrummel, C. L. Chan, N. Macris, M.-A. Dupertuis, and C. Javerzac-Galy, “Efficient Quantum Algorithms for GHZ and W States, and Implementation on the IBM Quantum Computer,” Advanced Quantum Technologies , vol. 2, no. 5–6, p. 1900015, 2019, doi:10.1002/qute.201900015

2019

Closest in time.

Z. Wang, N. C. Rubin, J. M. Dominy, and E. G. Rieffel, “ X Y XY mixers: Analytical and numerical results for the quantum alternating operator ansatz,” Physical Review A , vol. 101, no. 1, p. 012320, 2020, doi:10.1103/PhysRevA.101.012320

2020

Closest in time.

Z. H. Saleem, “Max-independent set and the quantum alternating operator ansatz,” International Journal of Quantum Information , p. 2050011, 2020, doi:10.1142/S0219749920500112

2020

Closest in time.

L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, “Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices,” Physical Review X , vol. 10, no. 2, p. 021067, 2020, doi:10.1103/PhysRevX.10.021067

2020

Closest in time.

V. Akshay, H. Philathong, M. E. S. Morales, and J. D. Biamonte, “Reachability Deficits in Quantum Approximate Optimization,” Physical Review Letters , vol. 124, no. 9, p. 090504, 2020, doi:10.1103/PhysRevLett.124.090504

2020

Closest in time.