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.

arXiv comment8 pages, 4 figures, close to published version

References in corpus (28)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A variational eigenvalue solver on a quantum processor
• Quantum Annealing in the Transverse Ising Model
• Characterizing Quantum Supremacy in Near-Term Devices
• Experimental quantum computing without entanglement
• Boson Sampling on a Photonic Chip
• Quantum Computational Supremacy
• Experimental Boson Sampling
• Experimental boson sampling in arbitrary integrated photonic circuits
• Boson sampling with 20 input photons in 60-mode interferometers at $10^{14}$ state spaces
• Gaussian Boson Sampling
• Boson Sampling from Gaussian States
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Experimental Scattershot Boson Sampling
• On the hardness of classically simulating the one clean qubit model
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Verification of Many-Qubit States
• Direct certification of a class of quantum simulations
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Anticoncentration theorems for schemes showing a quantum speedup
• Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
• Non-Unitary Quantum Computation in the Ground Space of Local Hamiltonians
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• Ancilla-driven instantaneous quantum polynomial time circuit for quantum supremacy
• Finding resource states of measurement-based quantum computing is harder than quantum computing