Hardness of efficiently generating ground states in postselected quantum computation

Abstract

Generating ground states of any local Hamiltonians seems to be impossible in quantum polynomial time. In this paper, we give evidence for the impossibility by applying an argument used in the quantum-computational-supremacy approach. More precisely, we show that if ground states of any $3$-local Hamiltonians can be approximately generated in quantum polynomial time with postselection, then $\mathsf{PP}=\mathsf{PSPACE}$. Our result is superior to the existing findings in the sense that we reduce the impossibility to an unlikely relation between classical complexity classes. We also discuss what makes efficiently generating the ground states hard for postselected quantum computation.

8 pages, 4 figures, close to published version

References in corpus (8)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Experimental quantum computing without entanglement
• Quantum Computational Supremacy
• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Experimental Scattershot Boson Sampling
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy