Two Bases Suffice for QMA₁-Completeness

Our proof of ˜1.1 consists of two parts. To show $\mathrm{𝖰𝖬𝖠}{\text{<sub class="ltx\_sub">1</sub>}}^{{𝒢}_2}$-completeness of our problem, we must show that it is both contained in $\mathrm{𝖰𝖬𝖠}{\text{<sub class="ltx\_sub">1</sub>}}^{{𝒢}_2}$ and that it is $\mathrm{𝖰𝖬𝖠}{\text{<sub class="ltx\_sub">1</sub>}}^{{𝒢}_2}$-hard. The containment follows along standard lines: we construct a verifier for XZ-Quantum-$6$-Sat instances that samples a random term from the Hamiltonian and coherently measures it on the witness state. The only nontrivial step in this construction is showing that the verifier’s gate set ${𝒢}_2$ can exactly simulate a controlled Hadamard gate, since this gate is needed to perform the measurement of the witness in the appropriate basis.

The bulk of the proof is concerned with the $\mathrm{𝖰𝖬𝖠}{\text{<sub class="ltx\_sub">1</sub>}}^{{𝒢}_2}$-hardness. We build on the Kitaev circuit-to-Hamiltonian construction [15], which is a quantum analog of the fundamental construction used by Cook and Levin [9, 16] to show that Sat is $\mathrm{𝖭𝖯}$-complete. Let us consider a circuit consisting of gates $U_1,U_2,\mathrm{\dots },U_T$, acting on a Hilbert space $\mathscr{H}$. Kitaev’s construction associates this circuit to a Hamiltonian $H$ acting on a space $\mathscr{H}\otimes {\mathscr{H}}_{\mathrm{clock}}$, where ${\mathscr{H}}_{\mathrm{clock}}$ is the Hilbert space of an ancillary “clock” register. The space ${\mathscr{H}}_{\mathrm{clock}}$ contains at least $T+1$ orthonormal states $|\widehat{0}⟩,|\widehat{1}⟩,\mathrm{\dots },|\widehat{T}⟩$, but typically has a much larger dimension – $2^T$ in Kitaev’s original construction. The full Hamiltonian $H$ can be written as a sum of four components:

where each component is a sum of local projectors. Moreover, Kitaev’s analysis shows that, when applied to a $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$ circuit $U_1,\mathrm{\dots },U_T$ that accepts some witness state with certainty, the Hamiltonian $H$ has a $0$- energy ground state, and otherwise, if applied to a circuit that rejects all witnesses with high probability, then the minimum energy of $H$ is at least $1/\mathrm{poly}(n)$.

Our approach is to use Kitaev’s construction, but modify the terms $H_{\mathrm{prop}}$ and $H_{\mathrm{format}}$, as well as the encoding of the clock states $|\widehat{0}⟩,\mathrm{\dots },|\widehat{T}⟩$, so that the resulting Hamiltonian $H$ satisfies our two-basis constraint. Since we will not modify them significantly, for now let us ignore the terms $H_{\mathrm{init}}$ and $H_{\mathrm{out}}$, and study the ground space of the remaining two terms. These are designed in Kitaev’s construction so that they always have a nonempty 0-energy ground space, which consists of history states of the form

This is achieved in two ways:

• $\mathrm{■}$

  The “format” Hamiltonian $H_{\mathrm{format}}$ forces the state to be supported only on the “good” clock register states $|\widehat{0}⟩,\mathrm{\dots },|\widehat{T}⟩$. This is done in Kitaev’s construction by taking ${\mathscr{H}}_{\mathrm{clock}}$ to be a space of $T$ qubits, and taking the good clock states to be encodings of $0,\mathrm{\dots },T$ in unary in the standard basis, so that

  $$|\widehat{t}⟩={|\text{1}⟩}_1\mathrm{\dots }{|\text{1}⟩}_{t-1}{|\text{1}⟩}_t{|\text{0}⟩}_{t+1}\mathrm{\dots }{|\text{0}⟩}_T.$$

  To force the state to be supported only on these states, $H_{\mathrm{format}}$ consist of projectors that enforce the constraint on each pair of adjacent qubits $(t,t+1)$ that a $0$ can never be followed by a $1$. These constraints are already diagonal in the $Z$-basis.

• $\mathrm{■}$

  The “propagation” Hamiltonian $H_{\mathrm{prop}}$ consists of a sum of $T$ constraints, each of which forces the $|\widehat{t-1}⟩$ and $|\widehat{t}⟩$ components of the state to be related by an application of the unitary $U_t$. In Kitaev’s construction, these terms take the form

  	$H_{\mathrm{prop},t}$	$={\displaystyle \frac{1}{2}}I\otimes {(|\text{11}\text{0}⟩⟨\text{11}\text{0}|+|\text{1}\text{00}⟩⟨\text{1}\text{00}|)}_{t-1,t,t+1}$
  		$-{\displaystyle \frac{1}{2}}{U}_t\otimes {(|\text{11}\text{0}⟩⟨\text{1}\text{00}|)}_{t-1,t,t+1}-{\displaystyle \frac{1}{2}}{U}_t^{†}\otimes {(|\text{1}\text{00}⟩⟨\text{11}\text{0}|)}_{t-1,t,t+1},$

  where the second tensor factor acts on the specified qubits of the clock register. It can be checked that for general choices of $U_t$, these terms are not diagonal in either the $X$-basis or the $Z$-basis.

To make progress, we must modify the propagation terms. To do this, we make the following key observation: the terms $H_{\mathrm{prop},t}$ are “almost” diagonal in the $X$-basis whenever the unitary $U_t$ itself is diagonal in the $X$-basis and is Hermitian (i.e. $U_t=U_t^{†}$). Specifically, in this case, $H_{\mathrm{prop},t}$ can be written as

which is diagonal when all qubits are placed in the $X$-basis except for qubits $t-1,t+1$ of the clock register, which remain in the $Z$-basis. Moreover, the same property would hold, with $X$ and $Z$ interchanged, if the good clock states were $X$-basis states, and $U_t$ were Hermitian and diagonal in the $Z$-basis.

This suggests the following modifications:

• $\mathrm{■}$

  Encode good clock states by putting alternating qubits in the $X$- and $Z$-bases. This means that valid clock states would look like

  $$|\widehat{0}⟩=|\text{0+0+0+}\mathrm{\dots }⟩,|\widehat{1}⟩=|\text{1}\text{+0+0+}\mathrm{\dots }⟩,|\widehat{2}⟩=|\text{1-}\text{0+0+}\mathrm{\dots }⟩,|\widehat{3}⟩=|\text{1-1}\text{+0+}\mathrm{\dots }⟩,\mathrm{\dots }.$$

• $\mathrm{■}$

  Choose a universal gate set where each gate is Hermitian and diagonal in either the $X$- or $Z$-basis. We construct such a gate set and show that it is computationally equivalent to ${𝒢}_2$.

• $\mathrm{■}$

  Padding the circuit so that each $X$-basis gate falls on an odd timestep and each $Z$-basis timestep falls on an even timestep. This makes the propagation terms fully diagonal in the $X$-basis for odd times, and the $Z$-basis for even times: e.g. for odd $t$,

  $$H_{\mathrm{prop},t}=\frac{1}{2}(I\otimes I_t-U_t\otimes X_t)\otimes |\text{-}\text{+}⟩{⟨\text{-}\text{+}|}_{t-1,t+1}.$$

With these changes, every term in $H_{\mathrm{prop},t}$ is diagonal in either the $X$- or $Z$-basis. However, now that we have changed the encoding of the clock, we must also change $H_{\mathrm{format}}$, and it is not hard to see that any Hamiltonian that restricts us only to valid clock states will not be diagonal in either basis. The solution to this is somewhat surprising.

• $\mathrm{■}$

  We modify $H_{\mathrm{format}}$ to include checks that only check consistency separately on the $X$- and $Z$-basis parts of the clock state. Specifically, our new $H_{\mathrm{format}}$ checks that the clock register in a state $|t_Z,t_X⟩$ consisting of an “interleaving” of some valid unary-encoding of an integer $t_Z$ in the $Z$-basis in odd positions, and an integer $t_X$ in the $X$-basis in even positions. It does not check that these two interleaved times are synchronized with each other, meaning that this Hamiltonian accepts invalid sates such as

  $$|\text{0}\text{-}\text{0}\text{-}\text{0+}\mathrm{\dots }\text{0+0}⟩,$$

  which do not correspond to valid clock states. We call these states “fake” states.

• $\mathrm{■}$

  Surprisingly, we show that, in fact, $H_{\mathrm{prop}}+H_{\mathrm{format}}$ together force the ground state to supported only on valid clock states. This is because every fake clock state is coupled by some term in $H_{\mathrm{prop}}$ to a “bad” clock state, which incurs an energy penalty from $H_{\mathrm{format}}$. We analyze this quantitatively by relating the Hamiltonian to a graph Laplacian.

The majority of the technical work in our analysis consists in (a) proving universality of our new gate set, and (b) quantitatively bounding the minimum energy of $H_{\mathrm{format}}+H_{\mathrm{prop}}$ on the subspace of invalid clock strings.

We see several possibilities for future work with a quantum PCP flavor.

1. 1.

   Our construction, since it is based on the Feynman-Kitaev clock, cannot achieve the NLTS property: indeed, the product state $|0⟩\otimes |\widehat{0}⟩$ violates only a single propagation term of the Hamiltonian. To get to NLTS while maintaining the two-basis structure, can we apply our ideas to the tensor-network-based circuit-to-Hamiltonian construction of [4]?

2. 2.

   What do random instances of our two-basis Hamiltonians look like? Can we find a distribution such that Hamiltonians sampled from this distribution have a zero-energy ground state with high probability, but where finding the ground state is computationally hard? It would be especially interesting to relate this to work on the combinatorial NLTS property for tensor network Hamiltonians constructed from random SAT instances [3].

3. 3.

   One candidate approach to proving the quantum PCP conjecture is to design a “locality-preserving gap amplification” procedure, that operates on instances of local Hamiltonians by increasing the minimum energy of unsatisfiable Hamiltonians (amplifying the “promise gap”), while preserving the locality of the Hamiltonian. To build towards such a procedure, can we apply classical “gap-amplification” or “locality-reduction” transformations separately to one of the two bases and make some kind of meaningful progress towards gap amplification? Moreover, is there an analog of “distance balancing” for CSS codes [20], whereby a code with high distance in one basis but low distance in the other can be converted into a code with decent distance in both bases?

4. 4.

   In this paper we have taken the point of view that $\mathrm{𝖰𝖬𝖠}{\text{<sub class="ltx\_sub">1</sub>}}^{{𝒢}_2}$ is likely to be qualitatively similar to $\mathrm{𝖰𝖬𝖠}$ in power. But if $\mathrm{𝖰𝖬𝖠}{\text{<sub class="ltx\_sub">1</sub>}}^{{𝒢}_2}$ is in fact much weaker, could our completeness result give us a route to showing this by putting the problem XZ-Quantum-$6$-Sat into a smaller class like $\mathrm{𝖰𝖢𝖬𝖠}$? One very speculative route to doing this is to give an efficient classical description of ground states of such Hamiltonians, perhaps using tools from additive combinatorics, since Hamiltonian terms in the $X$-basis can be viewed as additive constraints on the support of the ground state in the standard basis.

We briefly set up the basic formalism of quantum computation. For a more detailed exposition, we refer the reader to [17].

An $n$-qubit quantum state $|\psi ⟩$ is a unit vector in a complex Hilbert space ${({ℂ}^2)}^{\otimes n}$. A $k$-qubit quantum operation is a unitary operator $U$ acting on a $k$-qubit space ${({ℂ}^2)}^{\otimes k}$. We follow the conventions of Dirac notation. We use $U^{†}$ to denote the adjoint of an operator. Let $[n]=\{1,\mathrm{\dots },n\}$. We can extend $U$ to an operation $U\otimes I_{[n]\setminus S}$ on $n$-qubit space, where $S\subseteq [n]$ is the set of $k$ qubits which $U$ acts on, and $I_{[n]\setminus S}$ is the identity operator on the remaining qubits.

We now fix some notation for relevant states and operations. As usual, $|0⟩$ and $|1⟩$ refer to the single-qubit standard basis states, while $|+⟩$ and $|-⟩$ are the Hadamard basis states. We will often omit tensor products, e.g. $|00⟩=|0⟩\otimes |0⟩$. Let $X$ and $Z$ be the corresponding single-qubit Pauli operations. We will also refer to the standard and Hadamard bases as the $Z$ basis and $X$ basis respectively. Let $\widehat{H}$ be the Hadamard gate (we put the hat to avoid confusion with a Hamiltonian $H$). Let $CX$, $CZ$, and $\mathrm{SWAP}$ denote the two-qubit CNOT, controlled-$Z$ and swap operations respectively. Let $CCX$ denote the Toffoli gate and $CCZ$ the controlled-controlled-$Z$ gate.

A quantum circuit on $n$ qubits is an $n$-qubit operation $U$ which can be decomposed into a sequence of gates $U=G_m\mathrm{\cdots }{G}_1$, where each $G_i$ is a quantum operation from some fixed gate set; typically, this gate set contains operations which each acts nontrivially on just a small number of qubits. In our protocols, we will consider projective measurements of the first qubit in the $Z$ basis, which is given by the orthogonal projectors $\{|0⟩⟨0{|}_1\otimes I,|1⟩⟨1{|}_1\otimes I\}$, where the subscript indicates the first qubit register, and the identity operation acts on the remaining qubits.

We now define the model of quantum verification of interest in this work. A promise problem is a pair $(L_{\mathrm{yes}},L_{\mathrm{no}})$ of subsets of bitstrings $L_{\mathrm{yes}},L_{\mathrm{no}}\subseteq {\{0,1\}}^{\star }$ which satisfies $L_{\mathrm{yes}}\cap L_{\mathrm{no}}=\mathrm{\varnothing }$. Promise problems generalize languages, a notion from classical complexity theory: a language is just a promise problem which additionally satisfies $L_{\mathrm{yes}}\cup L_{\mathrm{no}}={\{0,1\}}^{\star }$.

A quantum verifier is a uniform family of quantum circuits $\{V_x\}$ whose goal is to determine whether a given string $x$ is in $L_{\mathrm{yes}}$ or $L_{\mathrm{no}}$, promised that one is the case. On an input $x$ of length $n$, the verifier is given access to a quantum proof state $|\psi ⟩$ and a register of ancilla qubits all initialized to $|0⟩$. The circuit is efficient, in the sense that both the proof and ancilla registers have $\mathrm{poly}(n)$ qubits, and there are $\mathrm{poly}(n)$ gates in the circuit.

After the circuit is applied, the final step of the verification is to measure the first qubit in the $Z$ basis. We say the verifier accepts if the measurement outcome is $1$ and rejects if the outcome is $0$. The probability that the verifier $V_x$ accepts is then

We now define $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$ and $\mathrm{𝖰𝖬𝖠}$; we will mainly be interested in $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$ in this work.

We refer to the first condition as completeness and the second condition as soundness. Importantly, the definition of $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$ is not known to be independent of the choice of gate set for the circuits. In this work, we choose the gate set

for $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$. When needing to explicitly refer to $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$ with this gate set, we use the notation $\mathrm{𝖰𝖬𝖠}{\text{<sub class="ltx\_sub">1</sub>}}^{{𝒢}_2}$. We now make some observations about the chosen gate set.

$\mathrm{𝖰𝖬𝖠}$ is defined in the same way as $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$, except the completeness parameter is $2/3$, i.e. for $x\in L_{\mathrm{yes}}$, the verifier must accept with probability at least $2/3$. In contrast to $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$, the definition of $\mathrm{𝖰𝖬𝖠}$ is independent of the choice of gate set, since the Solovay-Kitaev theorem [11] shows that any quantum gate can be efficiently approximated using gates from a universal gate set. This argument does not straightforwardly extend to $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$, since approximating a gate may not preserve the perfect completeness required of a $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$ protocol.

The classical theory of $\mathrm{𝖭𝖯}$-completeness generalizes to $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$ and $\mathrm{𝖰𝖬𝖠}$ in a straightforward way. A promise problem $K=(K_{\mathrm{yes}},K_{\mathrm{no}})$ has an efficient reduction to a promise problem $L=(L_{\mathrm{yes}},L_{\mathrm{no}})$ if there is an efficient deterministic algorithm $A$ which maps a bitstring $x$ to a bitstring $A(x)$ such that $A(x)\in L_{\mathrm{yes}}$ if $x\in K_{\mathrm{yes}}$, and $A(x)\in L_{\mathrm{no}}$ if $x\in K_{\mathrm{no}}$. A promise problem $L$ is $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$-hard if for every $K\in \mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$, there is an efficient reduction from $K$ to $L$. A promise problem $L$ is $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$-complete if $L$ is in $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$ and $L$ is $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$-hard. The definitions for $\mathrm{𝖰𝖬𝖠}$ are analogous.

In this section, we define the Quantum-$k$-Sat problem and introduce its basis-restricted variant. An $n$-qubit Hamiltonian is a Hermitian operator acting on $n$ qubits. A $k$-local operator on $n$ qubits is an operator which acts nontrivially on at most $k$ of the qubits. The energy of a state $|\psi ⟩$ with respect to Hamiltonian $H$ is $⟨\psi |H|\psi ⟩$. Note that this quantity is always real and non-negative, since $H$ is Hermitian.

The $\mathrm{𝖭𝖯}$-complete problem $k$-Sat can be viewed as a special case of Quantum-$k$-Sat with a highly restricted Hamiltonian: each projector term is diagonal in the same, predetermined basis (namely, the $Z$ basis) [2]. Let us refer to this as a classical Hamiltonian. This brings into view one of the guiding questions of this work: if we relax the restrictions placed on a classical Hamiltonian, at what point does the Hamiltonian become “quantum”? This question has been previously studied for the relaxation in which the Hamiltonian is no longer required to be classical, but instead the Hamiltonian terms must pairwise commute. In this work, we introduce a new way of generalizing classical Hamiltonians which we call basis restriction.

As an example, if for all $n$ we let ${ℬ}_n$ include just the $Z$ basis on $n$ qubits, then an instance of $ℬ$-Quantum-$k$-Sat is a Hamiltonian $H={\sum }_i{h}_i$ for which each $h_i$ is diagonal in the $Z$ basis. Then $H$ is a classical Hamiltonian and $ℬ$-Quantum-$k$-Sat is in $\mathrm{𝖭𝖯}$.

We are interested in the complexity of basis-restricted Quantum-$k$-Sat when we allow for more than one “type” of basis. In particular, is there some setting in which the problem already becomes $\mathrm{𝖰𝖬𝖠}$-hard, even though the number of basis types is small? We answer this question in the following sections by considering the problem XZ-Quantum-$k$-Sat, which we define as basis-restricted Quantum-$k$-Sat problem where each $h_i$ is diagonal in either the $Z$ or the $X$ basis.

Recall that our gate set for $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$ is ${𝒢}_2=\{X,CX,CCX,\widehat{H}\otimes \widehat{H}\}$. Define a new gate set

where $\widehat{G}$ is defined as the two-qubit operation equivalent to

We show that ${𝒢}_{XZ}$ and ${𝒢}_2$ are interchangeable gate sets, in the following sense:

We now sketch the original Kitaev construction and note which parts of the construction carry through to the proof of ˜1.1 unchanged. Let $(L_{\mathrm{yes}},L_{\mathrm{no}})$. be a promise problem in $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$, and let $V_x$ be the corresponding circuit which verifies a length $n$ bitstring $x$, given a proof state $|\psi ⟩$. Recall that the verification starts from state $|\mathrm{init}⟩=|\psi ⟩{|0\mathrm{\cdots }0⟩}_{\mathrm{anc}}$. Let $\mathscr{H}$ denote the Hilbert space in which the initial state lives. Let $Q_{\mathrm{proof}}$ and $Q_{\mathrm{anc}}$ denote the indices of the qubits in the proof and ancilla registers. Write the circuit as $V_x=U_T\mathrm{\cdots }{U}_1$, where each $U_i$ is a gate from the chosen gate set for $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$.

The Kitaev construction is an efficient mapping from the circuit $V_x$ to a Hamiltonian

$H$ acts on Hilbert space $\mathscr{H}\otimes {\mathscr{H}}_{\mathrm{clock}}$, where ${\mathscr{H}}_{\mathrm{clock}}$ is an additional $T$-qubit clock register. The Kitaev clock states $|\widehat{t}⟩\in {\mathscr{H}}_{\mathrm{clock}},t\in \{0,\mathrm{\dots },T\}$ are defined as $|\widehat{t}⟩=|{\text{1}}^t{\text{0}}^{T-t}⟩$ (the definition of clock states will differ in our construction). This reduction has the following properties:

Completeness

If $x\in L_{\mathrm{yes}}$, then the history state

$|\mathrm{hist}⟩={\displaystyle \frac{1}{\sqrt{T+1}}}{\displaystyle \sum _{t=0}^T}{U}_t\mathrm{\cdots }{U}_1|\mathrm{init}⟩\otimes |\widehat{t}⟩$

(2)

is a zero-energy state of $H$.

Soundness

If $x\in L_{\mathrm{no}}$, then any state $|\phi ⟩$ has at least $\frac{1}{\mathrm{poly}(n)}$ energy with respect to $H$.

Instance of Quantum-Sat

$H$ is a sum of projectors. Moreover, if each gate in the chosen gate is $k$-local, then $H$ is $(k+3)$-local.

Each term in the Hamiltonian represents a constraint on the proof state (which is claimed to be the history state); an energy penalty is given if the constraint is not met.

Our construction differs from the Kitaev construction in the definition of $H_{\mathrm{prop}}$ and $H_{\mathrm{format}}$, which we define in this section. First, we make a simple observation that the verification circuit $V_x$ can be assumed to be in a standard form.

The terms $H_{\mathrm{in}}$ and $H_{\mathrm{out}}$ of the Kitaev construction remain unchanged in our construction, and we state them here:

Within the subspace of clock states, the local check $|\text{0}⟩{⟨\text{0}|}_1$ projects onto the subspace spanned by $|\widehat{0}⟩$. Thus, $H_{\mathrm{in}}$ assigns an energy penalty to states whose $|\widehat{0}⟩$ clock component contains ancilla qubits which are not initialized to $|0⟩$. Likewise, $H_{\mathrm{out}}$ assigns an energy penalty when the $|\widehat{T}⟩$ clock component of the state does not have a $|1⟩$ on the first qubit of $\mathscr{H}$ (recall that this is qubit measured at the end of the $\mathrm{𝖰𝖬𝖠}\text{<sub class="ltx\_sub">1</sub>}$ verification). Note that $⟨\mathrm{hist}|H_{\mathrm{in}}|\mathrm{hist}⟩=⟨\mathrm{hist}|H_{\mathrm{out}}|\mathrm{hist}⟩=0$.