2013/01/01 by Akira SaiToh, Akira Saitoh
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum many-body systems #acm:68Q10 #acm:68Q17 #cs.CC #msc:68Q10 #msc:68Q17 #quant-ph
paper · pdf · doi:10.4230/lipics.tqc.2013.244
published as in Proc. TQC 2013 (LIPIcs vol.22), pp.244-253 (2013) · 10 pages, 1 figure, v2: proof of Proposition 1 modified, v3: major revision, more detailed explanation in the proof
openalex publication_date 2013/01/01 · arxiv created 2013/07/01 · arxiv updated 2013/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For the model of so-called coherent computing recently proposed by Yamamoto et al. [Y. Yamamoto et al., New Gen. Comput. 30 (2012) 327-355], a theoretical analysis of the success probability is given. Although it was claimed as their prospect that the Ising spin configuration problem would be efficiently solvable in the model, here it is shown that the probability of finding a desired spin configuration decreases exponentially in the number of spins for certain hard instances. The model is thus physically unfeasible for solving the problem within a polynomial cost.