BQNP: The quantum analogue of NP
Introduction
Complexity classes are the bread and butter of Theoretical Computer Science, defining the categories of problems we wish to solve based on certain resources, like time and memory, and models of computation, such as deterministic and non-deterministic. The most popular among these include the famous P and NP, but a natural question arises once we consider the possibilities of quantum computation: are there quantum analogues for these well studied classes? The answer, if you can believe it, is yes, and in this article, as an interesting example, we’ll choose to focus on the class BQNP, also known as Bounded-error Quantum Non-deterministic Polynomial-time, which generalizes NP.
Some definitions
In order to define classes in quantum computation in a sane manner, we first have to introduce some notions which will come in handy.
A partially defined Boolean function is a function F : 𝔹ⁿ → {0, 1, “undefined”}.
We say that F is in NP if there exists a partially defined function R ∈ P in two variables, such that if F(x) = 1, then ∃ y such that |y| < q(|x|) and R(x, y) = 1, and if F(x) = 0, then ∀ y with |y| < q(|x|), R(x, y) = 0. Note that q(⋅ ) is a polynomial.
Analogously, we say that F is in BQNP if there exists a polynomial time classical algorithm that computes a function x ↦ Z(x), where Z(x) is a description of a quantum circuit, realizing an operator
such that
Here,
and p₀ and p₁ satisfy the condition that p₀ — p₁ ≥ Ω(n⁻ᵃ), for some constant a ≥ 0. More intuitively, the problem can be interpreted as an Arthur-Merlin game: Merlin sends a quantum message |ξ⟩ to Arthur, who then checks it by applying the operator Uₓ. Then, he’ll be convinced that F(x) = 1 with probability at least p₁ and, if F(x) = 0, Merlin can fool Arthur with probability at most p₀. Similarly to the classes BPP and BQP, we can choose p₀ and p₁ with great flexibility through the amplification lemma, which is formulated analogously for BQNP.
Complete problems
One of the most interesting aspects of complexity classes is the idea of completeness, basically reducing a whole array of problems to a singular, (usually) very hard to solve problem from the same class. We’re all familiar with 3SAT and 3COLOR, and it turns out that such problems also exist in the class BQNP. Note that reductions in this class are the same as in NP (polynomial time reductions).
To provide an example, we’ll spend the majority of the article discussing the Local Hamiltonian problem, the quantum analogue of 3SAT, in that locality is basically a bound on the number of variables in each class. Then, an operator H is a k-local Hamiltonian if it can be written in the form
where each Hⱼ is a Hermitian operator acting on a set of qubits Sⱼ with size at most k.
Statement
Let z = (description of k-local Hamiltonian H, a, b), where k = O(1), 0 ≤ a < b and b - a = Ω(n⁻ˡ), for some positive l. Then,
Claim
The Local Hamiltonian is BQNP-complete.
Local Hamiltonian ∈ BQNP
The general idea for this step is to construct a circuit W that when applied to a state |η⟩, outputs 1 with probability p = 1 - r ⁻¹⟨η|H|η⟩, where r is the number of terms in H. Then, if |η⟩ corresponds to an eigenvalue λ ≤ a, the probability of outputting 1 is p ≥ 1 - r⁻¹a, and if every eigenvalue exceeds b, then p ≤ 1 - r⁻¹b.
To do this, we first construct such a circuit for a single term. We let Hⱼ = ∑ₛ λₛ |ψₛ⟩⟨ψₛ| which acts on at most k qubits. Hence, we can realize the operator
by a circuit of constant size. Then, Pⱼ(1) = 1 - ⟨η|H|η⟩.
For the general circuit W, we choose the integer j randomly and uniformly, and then apply the corresponding operator. This can be done by the measuring operator ∑ⱼ |j⟩⟨j| ⊗ Wⱼ applied to the initial vector
which gives us the desired results.
Local Hamiltonian is BQNP-hard
The main idea for this will be to construct a Hamiltonian, which is a mathematical representation of the energy of a quantum system, from a quantum circuit. This is a crucial step in the study of quantum systems, as the Hamiltonian provides important information about the behavior of a quantum system and its underlying physical laws.
To that end, suppose we have a circuit U = Uₗ …U₁ of size L. We assume that U acts on N qubits, the first m of which contain the message |ξ⟩, and the rest of which are 0.
The Construction
Suppose our Hamiltonian is H. Then, it will act on the space
where the first factor is the space on which the circuit acts, and the second factor is the space of a step counter.
Then, it will consist of three terms:
- Hᵢₙ, which corresponds to the condition that all the m qubits are initially in the state |0⟩. Explicitly,
where the first term is the projection onto the subspace of vectors for which the s-th qubit equals 1. Intuitively, each term of the sum adds 1 to the cost function whenever the s-th qubit is in the state |1⟩ while the counter is in state |0⟩.
2. Hₒᵤₜ, which corresponds to the final state and equals
Here, we assume that at set L, the first qubit has to be in state |1⟩, or else we collect a penalty.
3. Hₚᵣₒₚ, which describes the propagation of a quantum state through the circuit. Hence, it will consist of L terms, each of which corresponds to the transition from j - 1 to j:
Each term Hⱼ acts on two qubits of the circuit space, as well as on the space of the counter.
Putting all of this together, we find that H = Hᵢₙ + Hₒᵤₜ + Hₚᵣₒₚ. We want to find the minimum eigenvalue of this Hamiltonian, which is equivalent to the minimum of f(|η⟩) = ⟨η|H|η⟩ over all |η⟩ of unit length. The previous construction is defined in such a way as to ensure the existence of a small eigenvalue if and only if there exists some quantum state |ξ⟩ which causes U to output 1 with high probability. Then, the minimizing vector will be
The circuit to Hamiltonian construction lies at the basis of this proof, and we’ll return to it with some more algorithm examples towards the end of the article. The following steps in the proof will be defined less formally, since the proofs can get quite technical and the details in there are not terribly instructive.
Change of basis
To simplify our lives a bit more and represent H in a more readable manner, we’ll change the basis we’re using with the one given by the operator
Then, H will be replaced by its conjugate (alongside all of its components) so that at the end,
where
Sorry for the huge formula dump, but this exemplifies the motivation of our basis change perfectly: more concise and readable forms are obtained from doing it.
If the circuit outputs 1, then the Hamiltonian has a small eigenvalue
Suppose that our circuit outputs 1 with high probability (at least 1 - ϵ) for some state |ξ⟩. Hence,
Then, consider
and change the basis of the |η⟩ defined in the construction phase as we try to estimate ⟨η|H|η⟩. Then, since E|ψ⟩ = 0, Hᵢₙ and Hₚᵣₒₚ will be 0 under the bra-ket operation. However, using the inequality from above and the definition of Hₒᵤₜ, we find that ⟨η|Hₒᵤₜ|η⟩ is less than ϵ/(L+1). Hence, H has a small eigenvalue.
If the circuit outputs 0, then the Hamiltonian‘s eigenvalues are bounded below
The proof of this is long and tedious, so we’re not going to present it here. The main result is that if for any vector |ξ⟩ the probability of the output being 1 does not exceed ϵ², then all eigenvalues of H are ≥ c(1- ϵ)L⁻³, for some constant c.
Wrapping up
We are almost done, but have one final problem: the counter is unfortunately not a qubit. But fear not, we can remedy this by embedding the counter space in a larger space, which will map our Hamiltonian H to a new Hamiltonian Hₑₓₜ, which maps H’s counter space to itself and acts on it exactly like H. The intuition here is that by enlarging the space we’re working in, we can translate the L steps from our counter and translate them into qubits while maintaining all of the properties we’ve defined and proven above.
This final step completes the proof, and so the Local Hamiltonian problem is BQNP-complete!
Final words about BQNP
Another fun part about TCS is exploring the relationships between all of the complexity classes. We know that P ⊂ NP ⊂ PSPACE, and it turns out that such a result hold for BQNP too: BQNP ⊂ PSPACE! We won’t cover the proof here, but this result is surprising for two reasons: first, it shows just how big PSPACE actually is, and secondly, it shows the power of BQNP, since this class fully encapsulates the possibilities of quantum computation.
Some fun stuff before we leave
Before we wrap up this article, I wanted to outline some other circuit to Hamiltonian constructions for some algorithms we studied in class. Hopefully, this is all correct!
- QPE (quantum phase estimation algorithm)
The Hamiltonian H of QPE can be constructed by defining a set of controlled U gates, where each controlled U gate represents the interaction between a qubit and the unitary operator U, and can be represented as a sum of two terms: the control term and the evolution term.
The control term describes the interaction between the auxiliary qubits and the unitary operator U and is given by
where n is the number of auxiliary qubits, |i⟩ is the state of the i-th auxiliary qubit, and the last therm is the identity operator for the unity operator U.
The evolution term describes the time evolution of the quantum system under the Hamiltonian, and is given by
where the first term is the identity operator for the auxiliary qubits, and U is the unitary operator representing the Hamiltonian of the quantum systems.
2. The Quantum Ising Model
The Hamiltonian of the quantum Ising model is a mathematical representation of a quantum system consisting of a number of interacting spins. The Hamiltonian is given by:
where J is the coupling constant between the neighboring spins, which defines the strength of the interaction between them, and h is the magnetic field strength, which determines the effect of an external magnetic field on the spins. Summing over pairs of (i, j) represents a sum over all pairs of nearest-neighbor spins.
References
- A. Yu. Kitaev, A. H. Shen, and M . N. Vyalyi. Classical and Quantum Computation. American Mathematical Society, 2000.
2. https://qiskit.org/textbook
3. Adam D. Bookatz, QMA-complete problems, 2012
