Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer

被引：100

作者：

Zhu, Linghua ^{[1
]}

Tang, Ho Lun ^{[1
]}

Barron, George S. ^{[1
]}

Calderon-Vargas, F. A. ^{[1
]}

Mayhall, Nicholas J. ^{[2
]}

Barnes, Edwin ^{[1
]}

Economou, Sophia E. ^{[1
]}

机构：

[1] Virginia Tech, Dept Phys, Blacksburg, VA 24061 USA

[2] Virginia Tech, Dept Chem, Blacksburg, VA 24061 USA

来源：

PHYSICAL REVIEW RESEARCH | 2022年 / 4卷 / 03期

关键词：

Iterative methods;

D O I：

10.1103/PhysRevResearch.4.033029

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves combinatorial optimization problems. While there is evidence suggesting that the fixed form of the standard QAOA Ansatz is not optimal, there is no systematic approach for finding better Ansatze. We address this problem by developing an iterative version of QAOA that is problem tailored, and which can also be adapted to specific hardware constraints. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters. We provide evidence that this speedup is connected to the concept of shortcuts to adiabaticity.

引用

页数：9

共 40 条

[11]

Farhi E, 2014, Arxiv, DOI arXiv:1411.4028

[12] An adaptive variational algorithm for exact molecular simulations on a quantum computer [J].

Grimsley, Harper R. ;

Economou, Sophia E. ;

Barnes, Edwin ;

Mayhall, Nicholas J. .

NATURE COMMUNICATIONS, 2019, 10 (1)

[13] QAOA for Max-Cut requires hundreds of qubits for quantum speed-up [J].

Guerreschi, G. G. ;

Matsuura, A. Y. .

SCIENTIFIC REPORTS, 2019, 9 (1)

[14] Shortcuts to adiabaticity: Concepts, methods, and applications [J].

Guery-Odelin, D. ;

Ruschhaupt, A. ;

Kiely, A. ;

Torrontegui, E. ;

Martinez-Garaot, S. ;

Muga, J. G. .

REVIEWS OF MODERN PHYSICS, 2019, 91 (04)

[15] From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz [J].

Hadfield, Stuart ;

Wang, Zhihui ;

O'Gorman, Bryan ;

Rieffel, Eleanor G. ;

Venturelli, Davide ;

Biswas, Rupak .

ALGORITHMS, 2019, 12 (02)

[16] Quantum approximate optimization of non-planar graph problems on a planar superconducting processor [J].

Harrigan, Matthew P. ;

Sung, Kevin J. ;

Neeley, Matthew ;

Satzinger, Kevin J. ;

Arute, Frank ;

Arya, Kunal ;

Atalaya, Juan ;

Bardin, Joseph C. ;

Barends, Rami ;

Boixo, Sergio ;

Broughton, Michael ;

Buckley, Bob B. ;

Buell, David A. ;

Burkett, Brian ;

Bushnell, Nicholas ;

Chen, Yu ;

Chen, Zijun ;

Chiaro, Ben ;

Collins, Roberto ;

Courtney, William ;

Demura, Sean ;

Dunsworth, Andrew ;

Eppens, Daniel ;

Fowler, Austin ;

Foxen, Brooks ;

Gidney, Craig ;

Giustina, Marissa ;

Graff, Rob ;

Habegger, Steve ;

Ho, Alan ;

Hong, Sabrina ;

Huang, Trent ;

Ioffe, L. B. ;

Isakov, Sergei, V ;

Jeffrey, Evan ;

Jiang, Zhang ;

Jones, Cody ;

Kafri, Dvir ;

Kechedzhi, Kostyantyn ;

Kelly, Julian ;

Kim, Seon ;

Klimov, Paul, V ;

Korotkov, Alexander N. ;

Kostritsa, Fedor ;

Landhuis, David ;

Laptev, Pavel ;

Lindmark, Mike ;

Leib, Martin ;

Martin, Orion ;

Martinis, John M. .

NATURE PHYSICS, 2021, 17 (03) :332-+

[17] Shortcuts to Adiabaticity in Digitized Adiabatic Quantum Computing [J].

Hegade, Narendra N. ;

Paul, Koushik ;

Ding, Yongcheng ;

Sanz, Mikel ;

Albarran-Arriagada, F. ;

Solano, Enrique ;

Chen, Xi .

PHYSICAL REVIEW APPLIED, 2021, 15 (02)

[18] Qubit-ADAPT-VQE: An Adaptive Algorithm for Constructing Hardware-Efficient Ansatze on a Quantum Processor [J].

Ho Lun Tang ;

Shkolnikov, V. O. ;

Barron, George S. ;

Grimsley, Harper R. ;

Mayhall, Nicholas J. ;

Barnes, Edwin ;

Economou, Sophia E. .

PRX QUANTUM, 2021, 2 (02)

[19] Efficient and noise resilient measurements for quantum chemistry on near-term quantum computers [J].

Huggins, William J. ;

McClean, Jarrod R. ;

Rubin, Nicholas C. ;

Jiang, Zhang ;

Wiebe, Nathan ;

Whaley, K. Birgitta ;

Babbush, Ryan .

NPJ QUANTUM INFORMATION, 2021, 7 (01)

[20] Controlling the speed and trajectory of evolution with counterdiabatic driving [J].

Iram, Shamreen ;

Dolson, Emily ;

Chiel, Joshua ;

Pelesko, Julia ;

Krishnan, Nikhil ;

Gungor, Ozenc ;

Kuznets-Speck, Benjamin ;

Deffner, Sebastian ;

Ilker, Efe ;

Scott, Jacob G. ;

Hinczewski, Michael .

NATURE PHYSICS, 2021, 17 (01) :135-142

← 1 2 3 4 →