Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs

被引:88
作者
Farhi, Edward [1 ]
Gosset, David [2 ,3 ]
Hen, Itay [4 ]
Sandvik, A. W. [5 ]
Shor, Peter [6 ,7 ]
Young, A. P. [4 ]
Zamponi, Francesco [8 ,9 ]
机构
[1] MIT, Ctr Theoret Phys, Cambridge, MA 02139 USA
[2] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada
[3] Univ Waterloo, Inst Quantum Comp, Waterloo, ON N2L 3G1, Canada
[4] Univ Calif Santa Cruz, Dept Phys, Santa Cruz, CA 95064 USA
[5] Boston Univ, Dept Phys, Boston, MA 02215 USA
[6] MIT, CSAIL, Cambridge, MA 02139 USA
[7] MIT, Dept Math, Ctr Theoret Phys, Cambridge, MA 02139 USA
[8] CNRS, UMR 8549, Phys Theor Lab, FR-75231 Paris 05, France
[9] Ecole Normale Super, FR-75231 Paris 05, France
来源
PHYSICAL REVIEW A | 2012年 / 86卷 / 05期
基金
美国国家科学基金会;
关键词
COMPLEXITY; GAPS;
D O I
10.1103/PhysRevA.86.052334
中图分类号
O43 [光学];
学科分类号
070207 ; 0803 ;
摘要
In this paper we study the performance of the quantum adiabatic algorithm on random instances of two combinatorial optimization problems, 3-regular 3-XORSAT and 3-regular max-cut. The cost functions associated with these two clause-based optimization problems are similar as they are both defined on 3-regular hypergraphs. For 3-regular 3-XORSAT the clauses contain three variables and for 3-regular max-cut the clauses contain two variables. The quantum adiabatic algorithms we study for these two problems use interpolating Hamiltonians which are amenable to sign-problem free quantum Monte Carlo and quantum cavity methods. Using these techniques we find that the quantum adiabatic algorithm fails to solve either of these problems efficiently, although for different reasons.
引用
收藏
页数:17
相关论文
共 51 条
[1]  
Altshuler B., ARXIV09082782V2
[2]   Anderson localization makes adiabatic quantum optimization fail [J].
Altshuler, Boris ;
Krovi, Hari ;
Roland, Jeremie .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2010, 107 (28) :12446-12450
[3]   First-order quantum phase transition in adiabatic quantum computation [J].
Amin, M. H. S. ;
Choi, V. .
PHYSICAL REVIEW A, 2009, 80 (06)
[4]   Consistency of the Adiabatic Theorem [J].
Amin, M. H. S. .
PHYSICAL REVIEW LETTERS, 2009, 102 (22)
[5]  
[Anonymous], ARXIV10084844
[6]  
Bapst V., ARXIV12108011
[7]  
Berman P., 1999, Automata, Languages and Programming. 26th International Colloquium, ICALP'99. Proceedings (Lecture Notes in Computer Science Vol.1644), P200
[8]  
Bravyi S, 2008, QUANTUM INF COMPUT, V8, P361
[9]   COMPLEXITY OF STOQUASTIC FRUSTRATION-FREE HAMILTONIANS [J].
Bravyi, Sergey ;
Terhal, Barbara .
SIAM JOURNAL ON COMPUTING, 2009, 39 (04) :1462-1485
[10]   Rigorous decimation-based construction of ground pure states for spin-glass models on random lattices [J].
Cocco, S ;
Dubois, O ;
Mandler, J ;
Monasson, R .
PHYSICAL REVIEW LETTERS, 2003, 90 (04) :4-472054