Fetching the paper…
Reading the bibliography…
In this paper we give an overview of the quantum computational complexity class QMA and a description of known QMA-complete problems to date.
F. Barahona, On the computational complexity of Ising spin glass models , J. Phys. A: Math and Gen., 15(10), 3241, 1982; http://dx.doi.org/10.1088/0305-4470/15/10/028
1982
Earlier work this paper cites.
R. P. Feynman, Quantum mechanical computers , Found. Phys., 16, pp. 507-531, 1986; originally published in Optics News (February 1985), pp. 11-20; http://dx.doi.org/10.1007/BF01886518
1985
Earlier work this paper cites.
E. Knill, Quantum randomness and nondeterminism , 1996; http://arxiv.org/abs/quant-ph/9610012
1996
Earlier work this paper cites.
J. Watrous, Succinct quantum proof for properties of finite groups , Proc. 41st Foundations on Computer Science, pp. 537–546, 2000; http://dx.doi.org/10.1109/SFCS.2000.892141
2000
Earlier work this paper cites.
A. Y. Kitaev, A. H. Shen, and M. N. Vyalyi, Classical and quantum computation , Graduate Studies in Mathematics, Vol. 47 (AMS, Providence, RI), 2002
2002
Earlier work this paper cites.
D. Janzing, P. Wocjan, and T. Beth, Non-identity check is QMA-complete , International Journal of Quantum Information, 3(3), pp. 463–473, 2005; http://www.worldscientific.com/doi/abs/10.1142/S0219749905001067
2005
Earlier work this paper cites.
C. Marriott and J. Watrous, Quantum Arthur-Merlin games , Computational Complexity, 14(2), 122152, 2005; http://dx.doi.org/10.1007/s00037-005-0194-x
2005
Earlier work this paper cites.
S. Bravyi, Efficient algorithm for a quantum analogue of 2-SAT , 2006; http://arxiv.org/abs/quant-ph/0602108
2006
Earlier work this paper cites.
J. Kempe, A. Kitaev, and O. Regev, The complexity of the local Hamiltonian problem , SIAM J. Comput., 35(5), pp. 1070-1097, 2006; http://epubs.siam.org/doi/pdf/10.1137/S0097539704445226
2006
Earlier work this paper cites.
Y.-K. Liu, Consistency of local density matrices is QMA-complete , Proc. 10 10 th International Workshop on Randomization and Computation, RANDOM 2006, Lecture Notes in Computer Science 4110, pp. 438-449, 2006; http://dx.doi.org/10.1007/11830924_40
2006
Earlier work this paper cites.
A. Kay, Quantum-Merlin-Arthur-complete translationally invariant Hamiltonian problem and the complexity of finding ground-state energies in physical systems , Phys. Rev. A, 76(3), 030307, 2007; http://link.aps.org/doi/10.1103/PhysRevA.76.030307
2007
Earlier work this paper cites.
Y.-K. Liu, M. Christandl, and F. Verstraete, Quantum computational complexity of the N-representability problem: QMA complete , Phys. Rev. Lett. 98, 110503, 2007; http://link.aps.org/doi/10.1103/PhysRevLett.98.110503
2007
Earlier work this paper cites.
D. Nagaj and S. Mozes, A new construction for a QMA-complete 3-local Hamiltonian , J. Math. Phys. 48, 072104, 2007, http://dx.doi.org/10.1063/1.2748377
2007
Earlier work this paper cites.
J. D. Biamonte and P. J. Love, Realizable Hamiltonians for universal adiabatic quantum computers , Phys. Rev. A, 78(1), 012352, 2008; http://link.aps.org/doi/10.1103/PhysRevA.78.012352
2008
Cited alongside, same era.
S. Bravyi, D. DiVincenzo, R. Oliveira, and B. M. Terhal, The complexity of stoquastic local Hamiltonian problems , Quant. Inf. Comp. 8(5), pp. 0361-0385, 2008; http://arxiv.org/abs/quant-ph/0606140
2008
Cited alongside, same era.
L. Eldar and O. Regev, Quantum SAT for a qutrit-cinquit pair is QMA 1 -complete , Proceedings of the 35th International Colloquium on Automata, Languages and Programming, pp. 881-892, 2008; http://dx.doi.org/10.1007/978-3-540-70575-8_72
2008
Cited alongside, same era.
A. Kay, The computational power of symmetric Hamiltonians , Phys. Rev. A, 78(1), 012346, 2008; http://link.aps.org/doi/10.1103/PhysRevA.78.012346
2008
Cited alongside, same era.
T.-C. Wei, M. Mosca, and A. Nayak, Interacting Boson problems can be QMA hard , Phys. Rev. Lett., 104, 040501, 2010; http://link.aps.org/doi/10.1103/PhysRevLett.104.040501
2010
Later among the works it cites.
B. Rosgen, Testing non-isometry is QMA-complete , Theory of Quantum Computation, Communication, and Cryptography, pp63-76, 2011; http://dx.doi.org/10.1007/978-3-642-18073-6_6
2011
Later among the works it cites.
2011
Later among the works it cites.
A. Chailloux and O. Sattath, The complexity of the separable Hamiltonian problem , 2012 IEEE 27th Annual Conference on Computational Complexity, pp.32-41, 2012; http://dx.doi.org/10.1109/CCC.2012.42
2012
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2008
Cited alongside, same era.
R. Oliveira and B. Terhal, The complexity of quantum spin systems on a two-dimensional square lattice , Quant. Inf. Comp. 8(10), pp. 900-924, 2008; http://arxiv.org/abs/quant-ph/0504050
2008
Cited alongside, same era.
K. G. H. Vollbrecht and J. I. Cirac, Quantum Simulators, Continuous-Time Automata, and Translationally Invariant Systems , Phys. Rev. Lett. 100(1), 010501, 2008; http://link.aps.org/doi/10.1103/PhysRevLett.100.010501
2008
Cited alongside, same era.
D. Aharonov, D. Gottesman, S. Irani, and J. Kempe, The power of quantum systems on a line , Communications in Mathematical Physics 287(1), pp.41-65, 2009; http://dx.doi.org/10.1007/s00220-008-0710-3
2009
Cited alongside, same era.
S. Bravyi and B. Terhal, Complexity of stoquastic frustration-free Hamiltonians , SIAM J. Comput. 39(4), p. 1462, 2009; http://dx.doi.org/10.1137/08072689X
2009
Cited alongside, same era.
2009
Cited alongside, same era.
A. Kay, Role of rotational invariance in the properties of Hamiltonians , Phys. Rev. A, 80(4), 040301, 2009; http://link.aps.org/doi/10.1103/PhysRevA.80.040301
2009
Cited alongside, same era.
2009
Cited alongside, same era.
S. Gharibian and J. Kempe, Approximation algorithms for QMA-complete problems , SIAM J. Comput., 41(4), pp. 1028-1050, 2012; http://epubs.siam.org/doi/pdf/10.1137/110842272
2012
Closest in time.
2012
Closest in time.
2012
Closest in time.
A. D. Bookatz, S. P. Jordan, Y.-K. Liu, and P. Wocjan, Quantum nonexpander problem is quantum-Merlin-Arthur-complete , Phys. Rev. A, 87(4), 042317 , 2013; http://link.aps.org/doi/10.1103/PhysRevA.87.042317
2013
Closest in time.
D. Gosset and D. Nagaj, Quantum 3-SAT is QMA 1 -complete , 2013; http://arxiv.org/abs/1302.0290
2013
Closest in time.
D. Gottesman and S. Irani, The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems , Theory of Computing 9(2), pp. 31-–116, 2013; http://dx.doi.org/10.4086/toc.2013.v009a002
2013
Closest in time.
S. Hallgren, D. Nagaj, and S. Narayanaswami, The local Hamiltonian problem on a line with eight states is QMA-complete , Quant. Inf. Comp. 13(9-10), pp. 721-750, 2013; http://www.rintonpress.com/xxqic13/qic-13-910/0721-0750.pdf
2013
Closest in time.