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].