Realistic cost for the model of coherent computing
arXiv:1305.4440 · doi:10.4230/LIPIcs.TQC.2013.244
Abstract
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.
arXiv comment10 pages, 1 figure, v2: proof of Proposition 1 modified, v3: major revision, more detailed explanation in the proof
References in corpus (7)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Experimental implementation of an adiabatic quantum optimization algorithm
- A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
- Error correcting codes for adiabatic quantum computation
- Combining dynamical decoupling with fault-tolerant quantum computation
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Scaling of running time of quantum adiabatic algorithm for propositional satisfiability