A Simple PromiseBQP-complete Matrix Problem

by Dominik Janzing and Pawel Wocjan

Theory of Computing, Volume 3(4), pp. 61-79, 2007

Bibliography with links to cited articles

[1]   D. Aharonov: A simple proof that Toffoli and Hadamard are quantum universal. 2003. [arXiv:quant-ph/0301040].

[2]   D. Aharonov and I. Arad: The BQP-hardness of approximating the Jones polynomial. 2006. [arXiv:quant-ph/0605181].

[3]   D. Aharonov, V. Jones, and Z. Landau: A polynomial quantum algorithm for approximating the Jones polynomial. 2005. [arXiv:quant-ph/0511096].

[4]   D. Aharonov and A. Ta-Shma: Adiabatic quantum state generation and statistical zero knowledge. In Proc. 35th Annual ACM Symp. on Theory of Computing, pp. 20–29, 2003. [STOC:10.1145/780542.780546].

[5]   E. Bernstein and U. Vazirani: Quantum complexity theory. SIAM Journal on Computing, 26(5):1411–1473, 1997. [SICOMP:10.1137/S0097539796300921].

[6]   D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders: Efficient quantum algorithms for simulating sparse Hamiltonians. Comm. Math. Phys., 270(2):359–371, 2007. [Springer:hk7484445j37r228].

[7]   D. E. Browne and H. Briegel: One-way quantum computation - a tutorial introduction. 2006. [arXiv:quant-ph/0603226].

[8]   A. Childs: Quantum information processing in continuous time. PhD thesis, Massachusetts Institute of Technology, 2004.

[9]   A. M. Childs, D. W. Leung, and M. A. Nielsen: Unified derivations of measurement-based schemes for quantum computation. Phys. Rev. A, 71:032318, 2005. [PRA:10.1103/PhysRevA.71.032318].

[10]   S. Even, A. L. Selman, and Y. Yacobi: The complexity of promise problems with applications to public-key cryptography. Inform. and Control, pp. 159–173, 1984.

[11]   M. Freedman, A. Kitaev, and Z. Wang: Simulation of topological field theories by quantum computers. Comm. Math. Phys., 227(3):587–603, 2002. [Springer:btldwt3g5t0308da].

[12]   O. Goldreich: On promise problems. Technical Report 18, Electr. Colloquium Computational Complexity, 2005. [ECCC:TR05-018].

[13]   W. Hoeffding: Probability inequalities for sums of bounded random variables. Journ. Am. Stat. Ass., 58(301):13–30, 1963.

[14]   D. Janzing: Spin-1/2 particles moving on a 2d lattice with nearest-neighbor interactions can realize an autonomous quantum computer. Physical Review, A(75):012307, 2007. [PRA:10.1103/PhysRevA.75.012307].

[15]   D. Janzing and P. Wocjan: Ergodic quantum computing. Quant. Inf. Process., 4(2):129–158, 2005. [Springer:wq1g61v1236574t4].

[16]   D. Janzing, P. Wocjan, and T. Beth: “Non-Identity check” is QMA-complete. Int. Journ. Quant. Inf., 3(3):463–473, 2005. [doi:10.1142/S0219749905001067].

[17]   J. Kempe, A. Kitaev, and O. Regev: The complexity of the local Hamiltonian problem. SIAM J. Computing, 35(5):1070–1097, 2006. [SICOMP:10.1137/S0097539704445226].

[18]   A. Kitaev, A. Shen, and M. Vyalyi: Classical and Quantum Computation. Am. Math. Soc., Providence, Rhode Island, 2002.

[19]   E. Knill and R. Laflamme: Quantum computation and quadratically signed weight enumerators. Inf. Process. Lett., 79(4), 2001. [IPL:10.1016/S0020-0190(00)00222-2].

[20]   M. Nielsen and I. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000.

[21]   R. Oliveira and B. Terhal: The complexity of quantum spin systems on a two-dimensional square lattice. 2005. [arXiv:quant-ph/0504050].

[22]   R. Raussendorf and H. Briegel: A one-way quantum computer. Phys. Rev. Lett., 86(22):5188–5191, 2001. [PRL:10.1103/PhysRevLett.86.5188].

[23]   P. Wocjan, D. Janzing, Th. Decker, and Th. Beth: Measuring 4-local n-qubit observables could probabilistically solve PSPACE. In Proc. Winter International Symp. on Information and Communication Technologies, 2004. (Proceedings contain only the abstract). [arXiv:quant-ph/0308011].

[24]   P. Wocjan and J. Yard: The Jones polynomial: quantum algorithms and applications in quantum complexity theory. 2006. [arXiv:quant-ph/0603069].

[25]   P. Wocjan and S. Zhang: Several natural BQP-complete problems. 2006. [arXiv:quant-ph/0606179].