Built on

C. Davis and W. M. Kahan, “Some new bounds on perturbation of subspaces,” Bull. Amer. Math. Soc. 75
1969
Earlier work this paper cites.
S. Piddock and J. Bausch, “Universal translationally-invariant hamiltonians,” (2020), arXiv:2001.08050 [quant-ph]
Original
2001
Earlier work this paper cites.
H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, “Quantum fingerprinting,” Physical Review Letters 87
2001
Earlier work this paper cites.
A. Y. Kitaev, A. Shen, and M. N. Vyalyi, “Classical and quantum computing,” in Quantum Information (Springer New York, New York, NY, 2002) pp. 203–217
2002
Earlier work this paper cites.
T. Kohler, S. Piddock, J. Bausch, and T. Cubitt, “Translationally-invariant universal quantum hamiltonians in 1d,” (2020), arXiv:2003.13753 [quant-ph]
Original
2003
Earlier work this paper cites.
J. Kempe and O. Regev, “3-local Hamiltonian is QMA-complete,” Quantum information and computation , 0302079 (2003)
2003
Earlier work this paper cites.
C. Marriott and J. Watrous, “Quantum arthur-merlin games,” (2005), arXiv:cs/0506068 [cs.CC]
2005
Earlier work this paper cites.
D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, “Adiabatic quantum computation is equivalent to standard quantum computation,” SIAM Journal of Computing 37
2007
Earlier work this paper cites.

Similar

A. Deshpande, A. V. Gorshkov, and B. Fefferman, “The importance of the spectral gap in estimating ground-state energies,” (2020), arXiv:2007.11582 [quant-ph]
Original
2007
Cited alongside, same era.
D. Aharonov, M. Ben-Or, F. G. S. L. Brandao, and O. Sattath, “The pursuit for uniqueness: Extending valiant-vazirani theorem to the probabilistic and quantum settings,” (2008), arXiv:0810.4840 [quant-ph]
Original
2008
Cited alongside, same era.
S. Bravyi, D. P. DiVincenzo, and D. Loss, “Schrieffer–wolff transformation for quantum many-body systems,” Annals of Physics 326
2011
Cited alongside, same era.
T. S. Cubitt and A. Montanaro, “Complexity Classification of Local Hamiltonian Problems,” in 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (IEEE, 2014) pp. 120–129, arXiv:1311.3161
Original
2014
Cited alongside, same era.

Then

S. Bravyi and M. Hastings, “On complexity of the quantum Ising model,” Communications in Mathematical Physics 349
2017
Later among the works it cites.
T. Cubitt, A. Montanaro, and S. Piddock, “Universal Quantum Hamiltonians,” Proceedings of the National Academy of Sciences 115
2018
Later among the works it cites.
T. Kohler and T. Cubitt, “Toy models of holographic duality between local hamiltonians,” Journal of High Energy Physics 2019
2019
Later among the works it cites.
L. Zhou and D. Aharonov, “Strongly universal hamiltonian simulators,” (2021), arXiv:2102.02991 [quant-ph]
Original
2021
Closest in time.
M. Morgado and S. Whitlock, “Quantum simulation and computing with rydberg-interacting qubits,” AVS Quantum Science 3
2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2021

General conditions for universality of Quantum Hamiltonians

Kohler, Tamara, Piddock, Stephen, Bausch, Johannes et al.

Understand

Recent work has demonstrated the existence of universal Hamiltonians - simple spin lattice models that can simulate any other quantum many body system to any desired level of accuracy.

Until now proofs of universality have relied on explicit constructions, tailored to each specific family of universal Hamiltonians.
In this work we go beyond this approach, and completely classify the simulation ability of quantum Hamiltonians by their complexity classes.
We do this by deriving necessary and sufficient complexity theoretic conditions characterising universal quantum Hamiltonians.

Built on

C. Davis and W. M. Kahan, “Some new bounds on perturbation of subspaces,” Bull. Amer. Math. Soc. 75
1969
Earlier work this paper cites.
S. Piddock and J. Bausch, “Universal translationally-invariant hamiltonians,” (2020), arXiv:2001.08050 [quant-ph]
Original
2001
Earlier work this paper cites.
H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, “Quantum fingerprinting,” Physical Review Letters 87
2001
Earlier work this paper cites.
A. Y. Kitaev, A. Shen, and M. N. Vyalyi, “Classical and quantum computing,” in Quantum Information (Springer New York, New York, NY, 2002) pp. 203–217
2002
Earlier work this paper cites.
T. Kohler, S. Piddock, J. Bausch, and T. Cubitt, “Translationally-invariant universal quantum hamiltonians in 1d,” (2020), arXiv:2003.13753 [quant-ph]
Original
2003
Earlier work this paper cites.
J. Kempe and O. Regev, “3-local Hamiltonian is QMA-complete,” Quantum information and computation , 0302079 (2003)
2003
Earlier work this paper cites.
C. Marriott and J. Watrous, “Quantum arthur-merlin games,” (2005), arXiv:cs/0506068 [cs.CC]
2005
Earlier work this paper cites.
D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, “Adiabatic quantum computation is equivalent to standard quantum computation,” SIAM Journal of Computing 37
2007
Earlier work this paper cites.

Similar

A. Deshpande, A. V. Gorshkov, and B. Fefferman, “The importance of the spectral gap in estimating ground-state energies,” (2020), arXiv:2007.11582 [quant-ph]
Original
2007
Cited alongside, same era.
D. Aharonov, M. Ben-Or, F. G. S. L. Brandao, and O. Sattath, “The pursuit for uniqueness: Extending valiant-vazirani theorem to the probabilistic and quantum settings,” (2008), arXiv:0810.4840 [quant-ph]
Original
2008
Cited alongside, same era.
S. Bravyi, D. P. DiVincenzo, and D. Loss, “Schrieffer–wolff transformation for quantum many-body systems,” Annals of Physics 326
2011
Cited alongside, same era.
T. S. Cubitt and A. Montanaro, “Complexity Classification of Local Hamiltonian Problems,” in 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (IEEE, 2014) pp. 120–129, arXiv:1311.3161
Original
2014
Cited alongside, same era.

Then

S. Bravyi and M. Hastings, “On complexity of the quantum Ising model,” Communications in Mathematical Physics 349
2017
Later among the works it cites.
T. Cubitt, A. Montanaro, and S. Piddock, “Universal Quantum Hamiltonians,” Proceedings of the National Academy of Sciences 115
2018
Later among the works it cites.
T. Kohler and T. Cubitt, “Toy models of holographic duality between local hamiltonians,” Journal of High Energy Physics 2019
2019
Later among the works it cites.
L. Zhou and D. Aharonov, “Strongly universal hamiltonian simulators,” (2021), arXiv:2102.02991 [quant-ph]
Original
2021
Closest in time.
M. Morgado and S. Whitlock, “Quantum simulation and computing with rydberg-interacting qubits,” AVS Quantum Science 3
2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

G. De las Cuevas and T. S. Cubitt, “Simple universal models capture all classical spin physics,” Science 351

2016

Cited alongside, same era.

B. Fefferman and C. Y.-Y. Lin, “A Complete Characterization of Unitary Quantum Space,” in Leibniz International Proceedings in Informatics (LIPIcs) (9th Innovations in Theoretical Computer Science Conference, 2016) arXiv:1604.01384

Original

2016

Cited alongside, same era.

J. Bausch and S. Piddock, “The complexity of translationally invariant low-dimensional spin lattices in 3D,” Journal of Mathematical Physics 58

Original

2017

Cited alongside, same era.

D. Gottesman and S. Irani, “The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems,” Theory of Computing 9

Original

Cited in the paper.

D. Gottesman and S. Irani, “The quantum and classical complexity of translationally invariant tiling and hamiltonian problems,” (2009b), arXiv:0905.2419 [quant-ph]

Original

Cited in the paper.

PGQMA is a similar class to QMA with the added condition that the acceptance operator of the verification circuit has an inverse polynomial spectral gap. Note that for PGQMA the gap is required to be between the lowest and second lowest eigenvalue, unlike in our definition

Cited in the paper.

Although any equivalent model of computation could be substituted into the definition

Cited in the paper.

Here n ′ n^{\prime} is the number of spins in the encoded witness state ℰ ( | w μ ⟩ ) \mathcal{E}\left(\left\lvert{w_{\mu}}\right\rangle\right) . Since this is a reduction to QMA we have n ′ = O ⁡ ( poly ⁡ ( n ) ) n^{\prime}=\BigO(\poly(n))

Cited in the paper.

P. Scholl, M. Schuler, H. J. Williams, A. A. Eberharter, D. Barredo, K.-N. Schymik, V. Lienhard, L.-P. Henry, T. C. Lang, T. Lahaye, and et al., “Quantum simulation of 2d antiferromagnets with hundreds of rydberg atoms,” Nature 595

2021

Closest in time.

X. Wu, X. Liang, Y. Tian, F. Yang, C. Chen, Y.-C. Liu, M. K. Tey, and L. You, “A concise review of rydberg atom based quantum computation and quantum simulation*,” Chinese Physics B 30

2021

Closest in time.