The power of quantum systems on a line. (English) Zbl 1180.68162
Summary: We study the computational strength of quantum particles (each of finite dimensionality) arranged on a line. First, we prove that it is possible to perform universal adiabatic quantum computation using a one-dimensional quantum system (with 9 states per particle). This might have practical implications for experimentalists interested in constructing an adiabatic quantum computer. Building on the same construction, but with some additional technical effort and 12 states per particle, we show that the problem of approximating the ground state energy of a system composed of a line of quantum particles is QMA-complete; QMA is a quantum analogue of NP. This is in striking contrast to the fact that the analogous classical problem, namely, one-dimensional MAX-2-SAT with nearest neighbor constraints, is in P. The proof of the QMA-completeness result requires an additional idea beyond the usual techniques in the area: Not all illegal configurations can be ruled out by local checks, so instead we rule out such illegal configurations because they would, in the future, evolve into a state which can be seen locally to be illegal. Our construction implies (assuming the quantum Church-Turing thesis and that quantum computers cannot efficiently solve QMA-complete problems) that there are one-dimensional systems which take an exponential time to relax to their ground states at any temperature, making them candidates for being one-dimensional spin glasses.
MSC:
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 81P68 | Quantum computation |
Keywords:
quantum computationSoftware:
MAX-2-SATReferences:
| [1] | Apolloni B., Carvalho C., de Falco D.: Quantum stochastic optimization. Stochastic Processes and their Applications 33(5), 233–244 (1988) · Zbl 0683.90067 · doi:10.1016/0304-4149(89)90040-9 |
| [2] | Apolloni, B., Cesa-Bianchi, N., de Falco, D.: A numerical implementation of ”quantum annealing”. In: Stochastic Processes, Physics and Geometry: Proceedings of the Ascona-Locarno Conference. River Edge, NJ: World Scientific. 1990, pp. 97–111 |
| [3] | Aharonov, D., Gottesman, D., Irani, S., Kempe, J.: The power of quantum systems on a line. In: FOCS. Proc. 48 th Ann. IEEE, Symp on Foundations of Computer Science, Los Alamitos, CA: IEEE Comp. Soc., 2007, pp. 373–383 · Zbl 1180.68162 |
| [4] | Aharonov, D., Gottesman, D., Kempe, J.: The power of quantum systems on a line. http://arXiv.org/abs/0705.4077v2 [quant-ph], 2007 · Zbl 1180.68162 |
| [5] | Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., Regev, O.: Adiabatic quantum computation is equivalent to standard quantum computation. In: Proc. 45th FOCS, Los Alamitos, CA: IEEE Comp. Soc., 2004, pp. 42–51 · Zbl 1134.81009 |
| [6] | Barahona F.: On the computational complexity of Ising spin glass models. J. Phys. A: Math. Gen. 15, 3241–3253 (1982) · doi:10.1088/0305-4470/15/10/028 |
| [7] | Binder K., Young A.P.: Spin glasses: Experimental facts, theoretical concepts, and open questions. Rev. Mod. Phys. 58, 801–976 (1986) · doi:10.1103/RevModPhys.58.801 |
| [8] | Childs A., Farhi E., Preskill J.: Robustness of adiabatic quantum computation. Phys. Rev. A 65, 012322 (2002) · doi:10.1103/PhysRevA.65.012322 |
| [9] | Deift P., Ruskai M.B., Spitzer W.: Improved gap estimates for simulating quantum circuits by adiabatic evolution. Quant Infor. Proc. 6(2), 121–125 (2007) · Zbl 1119.81024 · doi:10.1007/s11128-006-0045-y |
| [10] | Feynman R.: Quantum mechanical computers. Optics News 11, 11–21 (1985) · doi:10.1364/ON.11.2.000011 |
| [11] | Farhi E., Goldstone J., Gutmann S., Lapan J., Lundgren A., Preda D.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292(5516), 472–476 (2001) · Zbl 1226.81046 · doi:10.1126/science.1057726 |
| [12] | Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution. http://arXiv.org/list/quant-ph/0001106 , 2000 |
| [13] | Fisher D.S.: Critical behavior of random transverse-field Ising spin chains. Phys. Rev. B 51(10), 6411–6461 (1995) · doi:10.1103/PhysRevB.51.6411 |
| [14] | Hastings, M.: Personal communication |
| [15] | Hastings, M.: An area law for one dimensional quantum systems. JSTAT. P08024 (2007) |
| [16] | Hastings, M., Terhal, B.: Personal communication |
| [17] | Irani, S.: The complexity of quantum systems on a one-dimensional chain. http://arXiv.org/abs/0705.4067v2[quant-ph] , 2007 |
| [18] | Jordan S.P., Farhi E., Shor P.W.: Error-correcting codes for adiabatic quantum computation. Phys. Rev. A 74, 052322 (2006) · doi:10.1103/PhysRevA.74.052322 |
| [19] | Janzing, D., Wocjan, P., Zhang, S.: A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation. http://arXiv.org/abs/0710.1615v2[quant-ph] , 2007 |
| [20] | Kay A.: The computational power of symmetric hamiltonians. Phys. Rev. A. 78, 012346 (2008) · doi:10.1103/PhysRevA.78.012346 |
| [21] | Kempe J., Kitaev A., Regev O.: The complexity of the Local Hamiltonian problem. SIAM J. Comp. 35(5), 1070–1097 (2006) · Zbl 1102.81032 · doi:10.1137/S0097539704445226 |
| [22] | Kitaev, A.Y., Shen, A.H., Vyalyi, M.N.: Classical and Quantum Computation. Providence, RI: Amer. Math. Soc., 2002 · Zbl 1022.68001 |
| [23] | Nagaj, D.: Local Hamiltonians in Quantum Computation. PhD thesis, MIT. http://arXiv.org/abs/0808.2117v1[quant-ph] , 2008 · Zbl 1311.81082 |
| [24] | Nagaj D., Wocjan P.: Hamiltonian quantum cellular automata in 1d. Phys. Rev. A 78, 032311 (2008) · doi:10.1103/PhysRevA.78.032311 |
| [25] | Osborne T.: Efficient approximation of the dynamics of one-dimensional quantum spin systems. Phys. Rev. Lett. 97, 157202 (2006) · doi:10.1103/PhysRevLett.97.157202 |
| [26] | Osborne T.: Ground state of a class of noncritical one-dimensional quantum spin systems can be approximated efficiently. Phys. Rev. A 75, 042306 (2007) · doi:10.1103/PhysRevA.75.042306 |
| [27] | Oliveira R., Terhal B.: The complexity of quantum spin systems on a two-dimensional square lattice. Quant. Inf. Comp. 8(10), 0900–0924 (2008) |
| [28] | Schollwöck U.: The density-matrix renormalization group. Rev. Mod. Phys. 77, 259–316 (2005) · Zbl 1205.82073 · doi:10.1103/RevModPhys.77.259 |
| [29] | Shepherd D.J., Franz T., Werner R.F.: Universally programmable quantum cellular automaton. Phys. Rev. Lett. 97, 020502 (2006) · doi:10.1103/PhysRevLett.97.020502 |
| [30] | Suzuki M.: Relationship between d-dimensional quantal spin systems and (d+1)-dimensional ising systems. Prog. Theor. Phys. 56(5), 1454–1469 (1976) · Zbl 1097.82507 · doi:10.1143/PTP.56.1454 |
| [31] | van Emde Boas, P.: Handbook of Theoretical Computer Science. volume A, Chapter 1. Cambridge, MA: MIT Press, 1990, pp. 1–66 |
| [32] | Valiant L.G., Vazirani V.V.: NP is as easy as detecting unique solutions. Theor. Comput. Sci. 47(3), 85–93 (1986) · Zbl 0621.68030 · doi:10.1016/0304-3975(86)90135-0 |
| [33] | Watrous, J.: On one-dimensional quantum cellular automata. In: Proc. 36th Annual IEEE Symp. on Foundations of Computer Science (FOCS), Los Alamitos, CA: IEEE Comp. Sci, 1995, pp. 528–537 · Zbl 0938.68733 |
| [34] | White S.R.: Density matrix formulation for quantum renormalization groups. Phys. Rev. Lett. 69, 2863 (1992) · doi:10.1103/PhysRevLett.69.2863 |
| [35] | White S.R.: Density-matrix algorithms for quantum renormalization groups. Phys. Rev. B 48, 10345 (1993) · doi:10.1103/PhysRevB.48.10345 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
