Efficiently generating ground states is hard for postselected quantum computation
share
Although quantum computing is expected to outperform universal classical computing, an unconditional proof of this assertion seems to be hard because an unconditional separation between BQP and BPP implies P≠ PSPACE. Because of this, the quantum-computational-supremacy approach has been actively studied; it shows that if the output probability distributions from a family of quantum circuits can be efficiently simulated in classical polynomial time, then the polynomial hierarchy collapses to its second or third level. Since it is widely believed that the polynomial hierarchy does not collapse, this approach shows one kind of quantum advantage under a plausible assumption. On the other hand, the limitations of universal quantum computing are also actively studied. For example, it is believed to be impossible to generate ground states of any local Hamiltonians in quantum polynomial time. In this paper, we give evidence for this 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 the counting hierarchy collapses to its first level. Our evidence is superior to the existing findings in the sense that we reduce the impossibility to an unlikely relation between classical complexity classes. Furthermore, our argument can be used to give evidence that at least one 3-local Hamiltonian exists such that its ground state cannot be represented by a polynomial number of bits, which may be related to a gap between QMA and QCMA.
READ FULL TEXT