Nonunitary quantum computation in the ground space of local Hamiltonians

A central result in the study of quantum Hamiltonian complexity is that the $k$-local Hamiltonian problem is quantum-Merlin-Arthur–complete. In that problem, we must decide if the lowest eigenvalue of a Hamiltonian is bounded below some value, or above another, promised one of these is true. Given the ground state of the Hamiltonian, a quantum computer can determine this question, even if the ground state itself may not be efficiently quantum preparable. Kitaev's proof of QMA-completeness encodes a unitary quantum circuit in QMA into the ground space of a Hamiltonian. However, we now have quantum computing models based on measurement instead of unitary evolution; furthermore, we can use postselected measurement as an additional computational tool. In this work, we generalize Kitaev's construction to allow for nonunitary evolution including postselection. Furthermore, we consider a type of postselection under which the construction is consistent, which we call tame postselection. We consider the computational complexity consequences of this construction and then consider how the probability of an event upon which we are postselecting affects the gap between the ground-state energy and the energy of the first excited state of its corresponding Hamiltonian. We provide numerical evidence that the two are not immediately related by giving a family of circuits where the probability of an event upon which we postselect is exponentially small, but the gap in the energy levels of the Hamiltonian decreases as a polynomial.

Figure 1

Hadamard gadget. A measurement of the Pauli-$X$ observable is performed on the first qubit. By postselecting on obtaining the outcome $+1$ corresponding to eigenvector $|+\rangle$, a Hadamard gate is applied to the unmeasured qubit.

Figure 2

Unitary operator is applied to an unknown state $|\psi \rangle$ and an ancilla, before the system is measured. This results in subnormalized unitary being applied to the ancilla.

Figure 3

Three Hadamard gadgets are implemented using three additional qubits.

Figure 4

Scaling of the eigenvalues of the Hamiltonian as a function of Hadamard gadgets, with Hamiltonian in Eq. (9). Here, we fit the data to an exponential function $y=A{e}^{bc}+c$, yielding $A=8.802,b=0.727$, and $c=-28.767$.

Figure 5

Each box is a postselected circuit implementing the identity on the input qubit $|\psi \rangle$ and recycling qubits, since the ancillas will always be in the state $|+\rangle$.

Figure 6

Scaling of the reciprocal of the smallest eigenvalue of the Hamiltonian corresponding to circuit family ${\mathcal{F}}_2$, as shown in Eq. (10). Here, we fit the data to a quadratic function $y=a{x}^2+bx+c$, and obtain $a=6.5,b=0.04$, and $c=1.4$.