2006/02/10 by Sergey Knysh, S. Knysh, Vadim Smelyanskiy +3
Computer Science · Physics and Astronomy · #Algorithms and Data Compression #Constraint Satisfaction and Optimization #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.dis-nn #cond-mat.stat-mech #quant-ph
paper · pdf · doi:10.48550/arxiv.cond-mat/0602257
30 pages, 7 figures
arxiv created 2006/02/10 · openalex publication_date 2006/02/10 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
In this paper we show that the performance of the quantum adiabatic algorithm is determined by phase transitions in underlying problem in the presence of transverse magnetic field Γ. We show that the quantum version of random Satisfiability problem with 3 bits in a clause (3-SAT) has a first-order quantum phase transition. We analyze the phase diagram γ=γ(Γ) where γ is an average number of clauses per binary variable in 3-SAT. The results are obtained in a closed form assuming replica symmetry and neglecting time correlations at small values of the transverse field Γ. In the limit of Γ=0 the value of γ(0)≈ 5.18 corresponds to that given by the replica symmetric treatment of a classical random 3-SAT problem. We demonstrate the qualitative similarity between classical and quantum versions of this problem.