By Abhijit Mudigonda, Richard Wang, and Lisa Yang
This is part of a series of blog posts for CS 229r: Physics and Computation. In this post, we will talk about progress made towards resolving the quantum PCP conjecture. We’ll briefly talk about the progression from the quantum PCP conjecture to the NLTS conjecture to the NLETS theorem, and then settle on providing a proof of the NLETS theorem. This new proof, due to Nirkhe, Vazirani, and Yuen, makes it clear that the Hamiltonian family used to resolve the NLETS theorem cannot help us in resolving the NLTS conjecture.
We are all too familiar with NP problems. Consider now an upgrade to NP problems, where an omniscient prover (we’ll call this prover Merlin) can send a polynomial-sized proof to a BPP (bounded-error probabilistic polynomial-time) verifier (and we’ll call this verifier Arthur). Now, we have more decision problems in another complexity class, MA (Merlin-Arthur). Consider again, the analogue in the quantum realm where now the prover sends over qubits instead and the verifier is in BQP (bounded-error quantum polynomial-time). And now we have QMA (quantum Merlin-Arthur).
We can show that there is a hierarchy to these classes, where NP MA QMA.
Our goal is to talk about progress towards a quantum PCP theorem (and since nobody has proved it in the positive or negative, we’ll refer to it as a quantum PCP conjecture for now), so it might be a good idea to first talk about the PCP theorem. Suppose we take a Boolean formula, and we want to verify that it is satisfiable. Then someone comes along and presents us with a certificate — in this case, a satisfying assignment — and we can check in polynomial time that either this is indeed a satisfying assignment to the formula (a correct certificate) or it is not (an incorrect certificate).
But this requires that we check the entire certificate that is presented to us. Now, in comes the PCP Theorem (for probabilistically checkable proofs), which tells us that a certificate can be presented to us such that we can read a constant number of bits from the certificate, and have two things guaranteed: one, if this certificate is correct, then we will never think that it is incorrect even if we are not reading the entire certificate, and two, if we are presented with an incorrect certificate, we will reject it with high probability .
In short, one formulation of the PCP theorem tells us that, puzzingly, we might not need to read the entirety of a proof in order to be convinced with high probability that it is a good proof or a bad proof. But a natural question arises, which is to ask: is there a quantum analogue of the PCP theorem?
The answer is, we’re still not sure. But to make progress towards resolving this question, we will present the work of Nirkhe, Vazirani, and Yuen in providing an alternate proof of an earlier result of Eldar and Harrow on the NLETS theorem.
Before we state the quantum PCP conjecture, it would be helpful to review information about local Hamiltonians and the -local Hamiltonian problem. A previous blog post by Ben Edelman covers these topics. Now, let’s state the quantum PCP conjecture:
(Quantum PCP Conjecture): It is QMA-hard to decide whether a given local Hamiltonian (where each ) has ground state energy at most or at least when for some universal constant .
Recall that MAX--SAT being NP-hard corresponds to the -local Hamiltonian problem being QMA-hard when . (We can refer to Theorem 4.1 in these scribed notes of Ryan O’Donnell’s lecture, and more specifically to Kempe-Kitaev-Regev’s original paper for proof of this fact.) The quantum PCP conjecture asks if this is still the case when the gap is .
Going back to the PCP theorem, an implication of the PCP theorem is that it is NP-hard to approximate certain problems to within some factor. Just like its classical analogue, the qPCP conjecture can be seen as stating that it is QMA-hard to approximate the ground state energy to a factor better than .
Reformulation: NLTS conjecture
Let’s make the observation that, taking to be the ground state energy, the qPCP conjecture sort of says that there exists a family of Hamiltonians for which there is no trivial state (a state generated by a low depth circuit) such that the energy is at most above the ground state energy.
Freedman and Hastings came up with an easier goal called the No Low-Energy Trivial States conjecture, or NLTS conjecture. We expect that ground states of local Hamiltonians are sufficiently hard to describe (if NP QMA). So low-energy states might not be generated by a quantum circuit of constant depth. More formally:
(NLTS Conjecture): There exists a universal constant and a family of local Hamiltonians where acts on particles and consists of local terms, s.t. any family of states satisfying requires circuit depth that grows faster than any constant.
To reiterate, if we did have such a family of NLTS Hamiltonians, then it we wouldn’t be able to give “easy proofs” for the minimal energy of a Hamiltonian, because we couldn’t just give a small circuit which produced a low energy state.
Progress: NLETS theorem
-error states are states that differ from the ground state in at most qubits. Now, consider -error states (which “agree” with the ground state on most qubits). Then for bounded-degree local Hamiltonians (analogously in the classical case, those where each variable participates in a bounded number of clauses), these states are also low energy. So any theorem which applies to low energy states (such as the NLTS conjecture), should also apply to states with -error (as in the NLETS theorem).
To define low-error states more formally:
Definition 2.1 (-error states): Let (the space of positive semidefinite operators of trace norm equal to 1 on ). Let be a local Hamiltonian acting on . Then:
- is an -error state of if of size at most s.t. .
- is an -error state for if s.t. and is an -error state for .
Here, see that is just the partial trace on some subset of integers , like we’re tracing out or “disregarding” some subset of qubits.
In 2017, Eldar and Harrow showed the following result which is the NLETS theorem.
Theorem 1 (NLETS Theorem): There exists a family of 16-local Hamiltonians s.t. any family of -error states for requires circuit depth where .
In the next two sections, we will provide background for an alternate proof of the NLETS theorem due to Nirkhe, Vazirani, and Yuen. After this, we will explain why the proof of NLETS cannot be used to prove NLTS, since the local Hamiltonian family we construct for NLETS can be linearized. Nirkhe, Vazirani, and Yuen’s proof of NLETS makes use of the Feynman-Kitaev clock Hamiltonian corresponding to the circuit generating the cat state (Eldar and Harrow make use of the Tillich-Zemor hypergraph product construction; refer to section 8 of their paper). What is this circuit? It is this one:
First, we apply the Hadamard gate (drawn as ) which maps the first qubit . Then we can think of the CNOT gates (drawn as ) as propagating whatever happens to the first qubit to the rest of the qubits. If we had the first qubit mapping to 0, then the rest of the qubits map to 0, and likewise for 1. This generates the cat state , which is highly entangled.
Why do we want a highly entangled state? Roughly our intuition for using the cat state is this: if the ground state of a Hamiltonian is highly entangled, then any quantum circuit which generates it has non-trivial depth. So if our goal is to show the existence of local Hamiltonians which have low energy or low error states that need deep circuits to generate, it makes sense to use a highly entangled state like the cat state.
(We’ll write that the state of a qudit – a generalization of a qubit to more than two dimensions, and in this case dimensions – is a vector in . In our diagram above, we’ll see 4 qudits, labelled appropriately.)
Let’s briefly cover the definitions for the quantum circuits we’ll be using.
Let be a unitary operator acting on a system of qudits (in other words, acting on ), where . Here, each is a unitary operator (a gate) acting on at most two qudits, and is a product of such operators.
If there exists a partition into products of non-overlapping two-qudit unitaries (we call these layers and denote them as , where each here is in layer ) such that then we say has layers.
In other words, has size and circuit depth .
Lightcones, effect zones, shadow zones
Consider and an operator.
For define as the gates in layer whose supports overlap that of any gate in , …, or with .
Definition 3.1 (lightcone): The lightcone of with respect to is the union of : .
So we can think of the lightcone as the set of gates spreading out of all the way to the first layer of the circuit. In our diagram, the lightcone of is the dash-dotted region. We have , , and .
We also want a definition for what comes back from the lightcone: the set of gates from the first layer (the widest part of the cone) back to the last layer.
Define . For , let be the set of gates whose supports overlap with any gate in .
Definition 3.2 (effect zone): The effect zone of with respect to is the union .
In our diagram, see that , , and . The effect zone of is the dotted region.
Definition 3.3 (shadow of the effect zone): The shadow of the effect zone of with respect to is the set of qudits acted on by the gates in the effect zone.
In our diagram, the first three qudits are effected by gates in the effect zone. So .
Given all of these definitions, we make the following claim which will be important later, in a proof of a generalization of NLETS.
Toward the Feynman-Kitaev clock
Now we’ll give some definitions that will become necessary when we make use of the Feynman-Kitaev Hamiltonian in our later proofs.
Let’s define a unary clock. It will basically help us determine whatever happened at any time little along the total time big . Let . For our purposes today, we won’t worry about higher dimensional clocks. So we’ll write , but we’ll really only consider the case where , which corresponds to . For simplicity’s sake, we will henceforth just write .
Our goal is to construct something a little similar to the tableaux in the Cook-Levin theorem, so we also want to define a history state:
Definition 4.1 (History state): Let be a quantum circuit that acts on a witness register and an ancilla register. Let denote the sequence of two-local gates in . Then for all , a state is a -dimensional history state of if:
where we have the clock state to keep track of time and is some state such that and . With this construction, we should be able to make a measurement to get back the state at time .
Proof of NLETS
We provide a proof of (a simplified case of) the NLETS theorem proved by Nirkhe, Vazirani, and Yuen in .
Theorem 2 (NLETS): There exists a family of -local Hamiltonians on a line (Each Hamiltonian can be defined on particles arranged on a line such that each local Hamiltonian acts on a particle and its two neighbors) such that for all , the circuit depth of any -error ground state for is at least logarithmic in .
First, we’ll show the circuit lower bound. Then we’ll explain why these Hamiltonians can act on particles on a line and what this implies about the potential of these techniques for proving NLTS.
Proof: We will use the Feynman-Kitaev clock construction to construct a -local Hamiltonian for the circuit : .
Fix and let have size . The Hamiltonian acts on qubits and consists of several local terms depending on :
We can think of a qubit state as representing a step computation on qubits (i.e. for each time , we have a bit computation state of ). Intuitively, a qubit state has energy with respect to iff it is the history state of . This is because checks that at time , consists of the input to . Each checks that proceed correctly from (i.e. that the th gate of is applied correctly). Then checks that at time , the output is . Finally, checks that the qubit state is a superposition only over states where the first qubits represent “correct times” (i.e. a unary clock state where time is represented by zeros followed by ones).
Therefore, has a unique ground state, the history state of , with energy :
Later we will show how to transform into a Hamiltonian on qutrits on a line. Intuitively, the structure of allows us to fuse the time qubits and state qubits and represent unused state qubits by . For the Hamiltonian , the ground state becomes
For the rest of this proof, we work with respect to .
Let be an -error state and let be the subset of qutrits such that . We define two projection operators which, when applied to alone, produce nontrivial measurements, but when applied to together, produce trivial measurements.
Definition 5.1: For any , the projection operator
projects onto the subspace spanned by on the th qutrit.
For any , the projection operator
projects onto the subspace spanned by on the th qutrit.
Claim 5.1: For , . For , . Note that these values are positive for any .
Proof: If , then measurements on the th qutrit are the same for and .
If , then any qutrit pure state cannot have nonzero weight in both and (every pure state ends in some number of s which tells which (if any) it can be a part of). Therefore,
If , then projecting onto the th qutrit gives with probability . Therefore, .
Claim 5.2: For such that , .
Proof: As before, we can calculate
If , then the th qutrit of is so . If , then because the first qutrits of contain the state so under any measurement, the and th qutrits must be the same.
Now we use these claims to prove a circuit lower bound. Let be a circuit generating (a state with density matrix) . Let be the depth of .
Consider some . For any operator acting on the th qutrit, its lightcone consists of at most gates so its effect zone consists of at most gates which act on at most qudits (called the shadow of the effect zone).
Assume towards contradiction that . Then the shadow of any operator acting only on the th qutrit has size at most since . So there is some outside of the shadow which is in the complement of . By Claim 3.1, we have found two indices such that any pair of operators acting on and have disjoint lightcones in . WLOG let . The lightcones of are disjoint which implies
By the two claims above, we get a contradiction.
Therefore, . We can take any constant epsilon: letting , we get
This analysis relies crucially on the fact that any -error state matches the groundstate on most qudits. However, NLTS is concerned with states which may differ from the groundstate on many qudits, as long as they have low energy.
Remark 2.1: The paper of Nirkhe, Vazirani, and Yuen  actually proves more:
Back to NLTS – Tempering our Optimism
So far, we’ve shown a local Hamiltonian family for which all low-error (in “Hamming distance”) states require logarithmic quantum circuit depth to compute, thus resolving the NLETS conjecture. Now, let’s try to tie this back into the NLTS conjecture. Since it’s been a while, let’s recall the statement of the conjecture:
Conjecture (NLTS): There exists a universal constant and a family of local Hamiltonians where acts on particles and consists of local terms, s.t. any family of states satisfying requires circuit depth that grows faster than any constant.
In order to resolve the NLTS conjecture, it thus suffices to exhibit a local Hamiltonian family for which all low-energy states require logarithmic quantum circuit depth to compute. We might wonder if the local Hamiltonian family we used to resolve NLETS, which has “hard ground states”, might also have hard low-energy states. Unfortunately, as we shall show, this cannot be the case. We will start by showing that Hamiltonian families that lie on constant-dimensional lattices (in a sense that we will make precise momentarily) cannot possibly be used to resolve NLTS, and then show that the Hamiltonian family we used to prove NLTS can be linearized (made to lie on a one-dimensional lattice!).
The Woes of Constant-Dimensional Lattices
Definition 6.1: A local Hamiltonian acting on qubits is said to lie on a graph if there is an injection of qubits into vertices of the graph such that the set of qubits in any interaction term correspond to a connected component in the graph.
Theorem 2: If is a local Hamiltonian family that lies on an -dimensional lattice, then has a family of low-energy states with low circuit complexity. In particular, if is a local Hamiltonian on a -dimensional lattice acting on qubits for large enough , then for any , there exists a state that can be generated by a circuit of constant depth and such that where is the ground-state energy.
Proof: In what follows, we’ll omit some of the more annoying computational details in the interest of communicating the high-level idea.
Start by partitioning the -dimensional lattice (the one that lives on) into hypercubes of side length . We can “restrict” to a given hypercube (let’s call it ) by throwing away all local terms containing a qubit not in . This gives us a well-defined Hamiltonian on the qubits in . Define to be the -qubit ground state of , and define
where is an -qubit state. Each can be generated by a circuit with at most gates, hence at most depth. Then, can be generated by putting all of these individual circuits in parallel – this doesn’t violate any sort of no-cloning condition because the individual circuits act on disjoint sets of qubits. Therefore, can be generated by a circuit of depth at most . and are both constants, so can be generated by a constant-depth circuit.
We claim that, for the right choice of , is also a low-energy state. Intuitively, this is true because can only be “worse” than a true ground state of on local Hamiltonian terms that do not lie entirely within a single hypercube (i.e. the boundary terms), and by choosing appropriately we can make this a vanishingly small fraction of the local terms of . Let’s work this out explicitly.
Each hypercube has surface area , and there are hypercubes in the lattice. Thus, the total number of qubits on boundaries is at most . The number of size -connected components containing a given point in a -dimensional lattice is a function of and . Both of these are constants. Therefore, the number of size -connected components containing a given vertex, and hence the number of local Hamiltonian terms containing a given qubit, is constant. Thus, the total number of violated local Hamiltonian terms is at most . Taking to be , we get the desired bound. Note that to be fully rigorous, we need to justify that the boundary terms don’t blow up the energy, but this is left as an exercise for the reader.
Linearizing the Hamiltonian
Now that we have shown that Hamiltonians that live on constant-dimensional lattices cannot be used to prove NLTS, we will put the final nail in the coffin by showing that our NLETS Hamiltonian (the Feynman-Kitaev clock Hamiltonian on the circuit ) can be made to lie on a line (a -dimensional lattice). To do so, we will need to understand the details of a bit better.
Proposition 6.1: for the circuit is -local.
Proof: Recall that we defined
Let’s go through the right-hand-side term-by-term. We will use to denote the qubit of the time register and to denote the qubit of the state register.
- needs to serially access the qubit pairs for all and ensure that they are all set to . Thus, is -local.
- Each term needs to access the states , and and ensure that the state transitions are correct. Thus, is -local.
- needs to access the states and ensure that the progression of the time register is correct. Thus, is -local.
Now, we follow an approach of  to embed into a line.
Theorem 3: The Feynman-Kitaev clock Hamiltonian can be manipulated into a -local Hamiltonian acting on qutrits on a line.
Proof: Rather than having act on total qubits ( time qubits and state qubits), let’s fuse each and pair into a single qudit of dimension . If we view as acting on the space of particles , we observe that, following Proposition 6.1, each local term needs to check at most the particles corresponding to times , , and . Therefore, is -local and on a line, as desired.
To see that we can have act on particles of dimension (qutrits) rather than particles of dimension , note that the degree of freedom corresponding to is unused, as the qubit of the state is never nonzero until timestamp . Thus, we can take the vectors
as a basis for each qutrit.
Even though we’ve shown that the clock Hamiltonian for our original circuit cannot be used to prove NLTS (which is still weaker than the original Quantum PCP conjecture) this does not necessarily rule out the use of this approach for other “hard” circuits which might then allow us to prove NLTS. Furthermore, NLETS is independently interesting, as the notion of being low “Hamming distance” away from vectors is exactly what is used in error-correcting codes.
-  Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.
-  Chinmay Nirkhe, Umesh Vazirani, and Henry Yuen. Approximate low-weight check codes and circuit lower bounds for noisy ground states. arXiv preprint arXiv:1802.07419, 2018.
-  Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. Adiabatic quantum computation is equivalent to standard quantum computation. SIAM J. Comput., 2007.