A Simple PromiseBQP-complete Matrix Problem
by Dominik Janzing and Pavel 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]. [ .pdf ] |
| [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]. [ .html ] |
| [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]. [ .html ] |
| [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]. [ http ] |
| [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]. [ .pdf ] |
| [25] |
P. Wocjan and S. Zhang: Several natural BQP-complete problems.
2006.
[arXiv:quant-ph/0606179]. |
This file has been generated by bibtex2html 1.81.