Verifying quantum computations at scale: A cryptographic leash on quantum devices

Abstract

Rapid technological advances point to a near future where engineered devices based on the laws of quantum mechanics are able to implement computations that can no longer be emulated on a classical computer. Once that stage is reached, will it be possible to verify the results of the quantum device?

Recently, Mahadev introduced a solution to the following problem: Is it possible to delegate a quantum computation to a quantum device in a way that the final outcome of the computation can be verified on a classical computer, given that the device may be faulty or adversarial and given only the ability to generate classical instructions and obtain classical readout information in return?

Mahadev’s solution combines the framework of interactive proof systems from complexity theory with an ingenious use of classical cryptographic techniques to tie a “cryptographic leash” around the quantum device. In these notes I give a self-contained introduction to her elegant solution, explaining the required concepts from complexity, quantum computing, and cryptography, and how they are brought together in Mahadev’s protocol for classical verification of quantum computations.

Quantum mechanics has been a source of endless fascination throughout the 20th century—and continues to be in the 21st. Two of the most thought-provoking aspects of the theory are the exponential scaling of parameter space (a pure state of $n$ qubits requires $2^n-1$ complex parameters to be fully specified), and the uncertainty principle (measurements represented by noncommuting observables cannot be performed simultaneously without perturbing the state). The conceptual difficulty of the problem of verification of quantum computations stems from both aspects. Suppose we are given the description of an experiment that can be modeled in quantum mechanics—say, a number $n$ of individual photons are emitted by lasers in a certain configuration, then made to interact according to optical equipment such as mirrors and beam-splitters, and finally some observation is made, for example counting the number of photons that hit a strategically located detector within a certain time period. Quantum mechanics provides a set of formal rules that, in principle, allow for the computation of the distribution of possible outcomes obtained in this experiment—what is the probability that any number of photons hit the detector within the prescribed time frame? These rules yield extremely precise predictions that have been verified in countless experiments. In general however, computing the prediction requires a number of operations that scales exponentially with $n$, the total number of photons in the experiment. What this means in practice is that as soon as $n$ exceeds, say, $80$, it becomes all but infeasible, using even the most powerful supercomputers available today, to predict the outcome of any nontrivial quantum experiment.

In addition to the intrinsic exponential scaling of quantum mechanics, other quantum phenomena, such as the uncertainty principle, place fundamental limits on our ability to verify that a quantum mechanical evolution proceeds as expected. Any attempt by the experimentalist at making intermediate observations on the state of a subset of the elementary particles involved in her experiment risks altering its outcome, so that it is not clear at all if the results of low-level benchmarks can be meaningfully pieced together to certify the final result.

These obstructions should come as no surprise. Indeed it is the same difficulty, of classical simulation of quantum evolutions, that prompted Feynman to bring forward the idea of a quantum computer in the first place: a computer that by its very nature would have the ability to efficiently simulate any quantum process 15. While such a universal quantum simulator remains a distant technological challenge, smaller-scale quantum devices have begun to appear that will soon have the capacity to simulate the evolution of specific quantum-mechanical systems, enabling physicists to, e.g., make predictions regarding properties of new materials (see, e.g., 7). Such simulators will become interesting the day when they are able to generate predictions that could not have been obtained on a classical computer. Assuming that such a classically unsimulatable quantum simulator exists, can one check that the simulator accomplishes the task it was asked to perform—given that the task could not have been accomplished on a classical computer? If the simulator makes a wrong prediction—be it due to a fault in its implementation, or even due to malice on the implementer’s part—is there any way that the error can be detected without having to rely on yet another quantum simulator to duplicate the first simulator’s results?

Not all is lost. There obviously are some quantum computations whose outcome can be easily checked. A standard example is factoring: having run Shor’s quantum algorithm for finding a prime factor $p$ of an integer $n$, it is easy to execute Euclid’s algorithm to check that $p|n$. In the language of complexity theory, the complexity class⁠¹ associated with the set of languages that can be decided efficiently with the help of a classical (probabilistic) computer is denoted BPP (for bounded-error probabilistic polynomial-time), while with a quantum computer one gets BQP (for bounded-error quantum polynomial-time). Factoring is an example of a problem that lies in the class BQP, but is not known to lie in the class BPP.⁠²

¹

A complexity class is a collection of languages, and a language is a set of strings; for example, the set of all binary representations of graphs that are $3$-colorable is a language. See Section 1 for more background on complexity theory.

✖

²

Technically, one would have to associate a language (i.e., a set of bitstrings) to factoring. An example is $L_{factoring} = \{$binary representations of a pair of integers $(n,k_1,k_2)$ such that $n$ has a prime factor $p$ such that $k_1\leq p \leq k_2\}$.

✖

As emphasized above, the factoring problem has the additional property that solutions to it are easily verifiable. Recognizing that many algorithmically difficult problems seemed to share the feature of having easily verifiable solutions (other examples are the problem if deciding if two graphs are isomorphic and the problem of deciding if a graph is $3$-colorable), Karp introduced in 1970 the complexity class NP (for nondeterministic polynomial-time). Informally, NP is the class of all languages that can be efficiently verified on a classical computer, given the right witness, or proof. If every problem in BQP (i.e., every problem that can be solved efficiently on a quantum computer) had this property—that the correct outcome of the computation can be efficiently verified on a classical computer—then the question of classical verifiability of quantum computation would be moot. However, there are very good reasons to think that this is not the case.

Indeed, complexity theorists strongly believe that there are problems in BQP that do not lie in NP.⁠³ One candidate for such a problem is the forrelation problem introduced in 1. The input to this problem is a pair of Boolean functions $f,g:\mathbb{Z}_2^n \to \{-1,1\}$, and it is promised that $g$ and the Fourier transform $\hat{f}$ of $f$ are either highly correlated, $|\langle \hat{f},g\rangle | \geq 0.9$, or barely correlated, $|\langle \hat{f},g\rangle | \leq 0.1$.⁠⁴ The goal is to determine which of the two cases hold. There is an easy quantum algorithm for this problem that requires a single evaluation of the functions $f$ and $g$, whereas it was shown in 27 that, if access to $f$ and $g$ is restricted to evaluation queries, then the problem lies beyond even the polynomial hierarchy, which is a vast extension of the class NP. The open challenge is to find an explicit family of functions $f$, $g$ for which the problem remains hard, even when given the explicit description of the functions (such as an evaluation circuit) as input.

³

They also believe that there are problems in NP, such as the traveling salesman problem or any NP-complete problem, that are not in BQP, so that the two classes are incomparable.

✖

⁴

To be precise, the definition is $\langle \hat{f},g\rangle = 2^{-3n/2} \sum _{x,y\in \mathbb{Z}_2^n} (-1)^{x\cdot y} f(x)g(y)$.

✖

Figure 1.

Known inclusions between complexity classes. Note that NP is not known to contain BPP because in NP, the verification procedure is assumed deterministic. With a randomized verifier, one obtains the class MA (for Merlin–Arthur) that does contain BPP.

There exists a wide range of problems that are known to be efficiently solvable on a quantum computer, but for which there is no obvious efficiently verifiable proof (such as the forrelation problem). Is it possible to design theoretical experiments, or protocols, based on quantum mechanics, for such problems such that the proper execution of the experiment, or computation, can be certified correct using a verification procedure that does not itself rely on the manipulation of quantum information?

In these notes I present an elegant solution to this problem due to Mahadev 24. Before presenting the solution, a first step is to formalize the question. This is done in two steps. First, in Section 1 I introduce the complexity-theoretic formalism of interactive proofs and arguments that forms the conceptual backdrop against which Mahadev’s result is formulated. Second, in Section 2 I give standard background in quantum computing that allows me to formalize the complexity class BQP and state Mahadev’s theorem. The remainder of the document is devoted to a presentation of the main ideas that constitute the proof of Mahadev’s result. Very roughly, the proof proceeds through the following steps.

•

An arbitrary quantum computation can be specified classically by providing the gate-by-gate description of a quantum circuit, as well as a classical description of the input on which the circuit is to be evaluated (generally, this will be a zero state representing a default initialization of all wires of the circuit). The first step is to reduce the problem of evaluating the output of such a circuit $C$ to the problem of verifying that a local Hamiltonian $H$, that can be efficiently computed from $C$ classically, has a smallest eigenvalue that is below a certain threshold. Informally, this step is the quantum analogue of encoding the tableau of a classical computation into an instance of the Ising spin problem. This step is described in Section 3.

•

The previous step has reduced the verification problem to the problem of classically certifying that a local Hamiltonian has an eigenstate with small enough eigenvalue. Section 4 introduces the idea of a commitment, which is an interactive procedure by which a party can commit to a certain value $b$, without revealing information about $b$, yet in a way that is binding: the party is unable to later “change its mind” with respect to $b$ and claim that it in fact had committed to some $b'\neq b$. The notion of a commitment protocol for quantum states is the key ingredient in Mahadev’s protocol and is presented in Section 5.

•

Armed with the notion of a quantum commitment scheme, we describe the verification protocol itself in Section 6. Informally, in the protocol the prover first provides classical information that is meant to indicate the prover’s commitment to being in the possession of a unique, well-defined quantum state $\psi$. Then, the verifier challenges the prover to reveal measurement outcomes performed on the state $\psi$ that it committed to, in a way that allows the verifier to estimate the associated energy $\psi ^* H \psi$ and verify that it is sufficiently small.

The security of Mahadev’s quantum commitment scheme, on which her result ultimately rests, relies on a computational assumption regarding the impossibility of efficiently solving a problem known as the Learning with Errors (LWE) problem. This problem is described in Section 7.

These notes are written in a way that aims to make the most important insights of Mahadev’s work accessible to any mathematician, with or without background in complexity theory and quantum information. As a result, the presentation will remain rather informal, and we alert the reader whenever the discussion makes an important shortcut.

To keep the presentation focused, we do not survey prior works and other approaches to verification in any depth. The question has a long history that, prior to Mahadev’s work, had resulted in partial answers, obtained in a variety of models of verification. Some of the most important results include the concurrent works of Aharonov et al. 2 and Broadbent et al. 12 which showed how to achieve verification in a model where the verification procedure can make use of a small, trusted quantum computer, and the work of Reichardt et al. 29 in a model where the verification procedure is entirely classical but has access to two spatially isolated quantum computers, sharing entanglement, who jointly implemented a quantum computation it aims to verify. In contrast to Mahadev’s result presented here, these works achieve information-theoretic (instead of computational) guarantees in their respective models. For an in-depth discussion of these and related works, I recommend the recent survey by Gheorghiu et al. 17.

1. Interactive poofs and arguments

The concept of an interactive proof system can be difficult to digest for the mathematician, in part because it involves some amount of personification. When they talk of an interactive protocol, computer scientists are accustomed to refer to imaginary beings known as the verifier and the prover. Even worse, these imaginary beings are endowed with intentions: the prover is trying to demonstrate something to the verifier, while the verifier attempts to catch any cheating behavior from the prover. This is not the kind of language that is frequently used in, say, the theory of differential equations or operator spaces. Please bear with me—interactive proofs are one of the most powerful ideas to have emerged out of complexity theory since the 1990s, and they are a key element of Mahadev’s solution.

It all starts with the complexity class NP, whose study originates in the works of Cook, Karp, and Levin in the 1970s. A complexity class is a collection of languages. A (promise) language $L$ is a pair of subsets $L_{yes},L_{no} \subseteq \{0,1\}^*$, where $\{0,1\}^*$ is the set of all bit strings, which are sequences of arbitrary but finite length over the alphabet $\{0,1\}$. For example, $L_{yes}$ could be the set of (suitably encoded) $3$-SAT formulas that admit a satisfying assignment,⁠⁵ and $L_{no}$ could be the set of formulas that are not satisfiable. The language $L=(L_{yes}, L_{no})$ is called $3$-SAT. Informally, a language $L$ is in the class NP if valid statements have an efficiently verifiable proof, and invalid statements have no valid proof. To formalize the notion of valid proof, we introduce the notion of verifier, represented by a polynomial-time Turing machine $V$ (for our purposes, the reader may replace the intimidating notion of Turing machine by any intuitive notion of efficient computation, such as an algorithm) whose goal is to verify claimed proofs. Thus a language $L$ is in the class NP if there exists a real polynomial $p$ and a Turing machine $V$ such that for all $x\in L_{yes}\cup L_{no}$,

⁵

A $3$-SAT formula is an AND of $3$-variable ORs, i.e., a Boolean formula of the form $\varphi = (x_1\vee x_2 \vee \overline{x_3}) \wedge (\overline{x_2} \vee x_5 \vee \overline{x_6}) \wedge \cdots$, where the variables $x_i\in \{0,1\}$ and $\overline{x_i}$ denotes variable negation.

✖

(i)

if $x\in L_{yes}$, then there exists a $w$, the witness, or proof, such that $V(x,w)$ halts in at most $p(|x|)$ steps, where $|x|$ denotes the length of $x$, and returns $1$ (for “accept”); and

(ii)

if $x\in L_{no}$, then for any $w$, $V(x,w)$ halts in at most $p(|x|)$ steps and returns $0$ (for “reject”).

Property (i) is usually referred to as the completeness condition and (ii) as the soundness condition. The fact that $3$-SAT is in NP follows since given as input a $3$-SAT formula $\varphi$, if the formula is satisfiable, then there exists a witness $w$ (a satisfying assignment for $\varphi$) that proves this, whereas if the formula is not satisfiable, it is easy for $V$ to check that any given purported assignment $w$ is indeed invalid.

Informally, NP captures the collection of problems that have efficiently verifiable solutions, such as factoring, $3$-SAT, the traveling salesman problem, or mathematical theorems (that have reasonably short proofs within a prespecified axiomatic system).

1.1. Interactive proof systems

A key insight from research in complexity theory in the 1990s is that the collection of languages that admit efficient verification can be substantially extended beyond the class NP by allowing interactive protocols for verification 518. Consider a verification procedure $V$, referred to as the verifier (personification, here it comes…), that is allowed to “ask questions” to another entity, the prover, about a claimed proof, as illustrated in Figure 2. Can this allow verification of languages other than the languages in NP, which admit static proofs?

The verifier in an interactive proof system is modeled as a randomized polynomial-time procedure. Informally, this refers to any algorithm that makes a total number of steps that is bounded by a polynomial function (that may depend on the algorithm) of the bitlength of its input and that has access to a source of uniformly random bits. Formally, the verifier is modeled by a randomized interactive Turing machine, but we will not need to descend to that level of detail. It is important that the verifier be randomized: indeed, interactive proof systems with deterministic verifiers reduce to NP because, in the case of deterministic messages from the verifier, there is no advantage to interaction (the prover can send the entire transcript as “proof”). A randomized verifier may sometimes make an erroneous decision, as long as for every input the probability of making an error in deciding that input is small: this ensures that repeating the verification procedure sufficiently many times and taking the majority decision yields an outcome that is erroneous with arbitrarily small probability.

Definition 1.1.

A language $L=(L_{yes},L_{no})$ has an interactive proof system if there exists a randomized polynomial-time verifier $V$ such that the following hold.

•

Completeness. For any $x\in L_{yes}$, there exists a prover $P$, referred to as the honest prover, such that $V$ accepts $P$ on input $x$ with probability at least $\frac{2}{3}$.

•

Soundness. For any $x\in L_{no}$ and any prover $P^*$, $V$ accepts $P^*$ on input $x$ with probability at most $\frac{1}{3}$.

The collection of languages for which there exists an interactive proof system is denoted IP.

Note the asymmetry between the completeness and soundness conditions in the definition, which reflects a similar asymmetry in the definition of NP: it is always assumed that the prover aims to convince the verifier that the input is in the language (e.g., for the case of NP, that a 3-SAT formula is satisfiable). The verifier, in turn, aims to make the right decision by taking information from the prover but “verifying” it before making a decision, so as not to wrongly accept a negative instance.

To gain intuition as to how interaction may help, consider the following toy problem. The input $x$ is interpreted as a bivariate polynomial $P(y,z)$ defined over a prime field $\mathbb{F}_p$, such that $P$ has degree at most $d$ in each of its variables. Think of $p$ as much larger than $d$: the input size, measured in number of bits, is roughly $(d+1)^2 \log p$ (a list of coefficients), and $p$ could be exponentially larger. Let $L_{yes}$ be the set of all such polynomials such that $S = \sum _{y,z} P(y,z) = 0$, and let $L_{no}$ be the set of polynomials such that $S\neq 0$. Computing $S$ naïvely takes time $O(p^2)$, where the $O(\cdot )$ hides a multiplicative factor of order the time it takes to evaluate $P$ at any given point, i.e., a polynomial in $d$ and $\log p$. Consider the following protocol, using which the verifier can be led to making the right decision while having to invest a computational effort of $O(p)$ only. The first step in the protocol is a message from the prover to the verifier, which consists in the claimed value of $S$, together with a supporting statement in the form of a degree-$d$ polynomial $Q(z)$ such that $S = \sum _{y} Q(z)$. (The honest prover can find such a $Q$ without difficulty by setting $Q(z)=\sum _y P(y,z)$.) Upon receipt of an arbitrary $(S,Q)$, the verifier first checks the equality $S = \sum _{z} Q(z)$, which takes $O(p)$ time. Next, she selects a uniformly random $z^*\in \mathbb{F}_p$ and checks that $Q(z^*) = \sum _{y} P(y,z^*)$, which again requires time $O(p)$. Note that, if it was the case that $Q(\cdot )\neq \sum _y P(y,\cdot )$, by the Schwartz–Zippel lemma the probability that $Q(z^*) = \sum _y P(y,z^*)$ would be at most $d/p$, which is small provided $p$ is much larger than $d$, as we assumed. Thus the verifier makes the right decision with high probability, on any input $P$.

This protocol reduces the verifier’s effort from order $p^2$ to order $p$, since the verifier only needs to perform summations over a single variable at a time, instead of both variables for the naïve computation. The attentive reader will have realized that the protocol is in fact noninteractive—there is a single message from the prover to the verifier. Applying the same idea to polynomials with more variables yields an interactive protocol, in which variables are randomly fixed by the verifier one at a time, with exponential savings in the amount of time required for verification, from order $p^m$ to order $mp$, with $m$ representing the number of variables. This idea, of efficiently verifying claims about the sum of the values taken by a multivariate polynomial, is central to the proof of a celebrated result in complexity theory, namely the inclusion of PSPACE (the class of languages that can be decided using polynomial space but arbitrary time) in IP 2330. While the state of the art in complexity theory does not allow one to prove that PSPACE is a strictly larger class than NP, this is generally believed to be the case, so that interaction seems to significantly broaden the class of languages that have efficient verifiers.

In fact, the possibility of interaction sufficiently strengthens the verifier so as to allow it to verify a class of languages that includes the class BQP of languages that can be efficiently decided on a quantum computer! Using the idea of Feynman path integrals, the probability that a quantum circuit returns the outcome “$1$” can be expressed as the sum of exponentially many complex numbers, each of which can be directly computed by taking a product of entries of the matrices that specify the quantum gates of the circuit; this exponential sum can be exactly computed (modulo finite-precision issues) in polynomial space. Given that PSPACE is in IP, it follows that there exists an interactive protocol, of the form described above, that allows a classical polynomial-time verifier to verify the outcome of a quantum computation by asking questions to an untrusted prover. But there is a hitch. The model of interactive proofs does not place limitations on the computational effort required of the prover. In the protocol for computing sums of polynomials described earlier, the prover has to compute multiple exponential-sized intermediate sums, that in general may take time $p^m$ to compute. Unfortunately, following the proofs that BQP is in PSPACE is in IP leads to a very similar protocol, in which the prover has to compute exponentially large sums that do not seem to be amenable to efficient computation even by a quantum procedure. There has been very little progress in tweaking the protocols obtained in this way to decrease the computational effort required for the honest prover (see, e.g., 3 for a discussion).

1.2. Interactive arguments

If we are to make the requirement that the actions of the honest prover (i.e., the prover in charge of convincing the verifier in the case of an input in $L_{yes}$) can be implemented efficiently (on a quantum computer), it is reasonable also to ask, not that there does not exist a $P^*$ that would improperly convince the verifier to accept an input in $L_{no}$, but merely that no such $P^*$ exists that can be implemented in (quantum) polynomial time. Interactive proof systems such that the soundness condition holds under such a computational assumption are called arguments, a notion introduced in 11.

Since it is not known that the classes P and NP, or even P and IP, are distinct, in order for the assumption to be effective, we further need to posit that a particular problem cannot be solved in (quantum) polynomial time. For example, we could make the assumption that the problem of factoring an integer cannot be solved in probabilistic polynomial time. Another example is that a certain explicit family of functions $f=\{f_\lambda : \{0,1\}^{n(\lambda )} \to \{0,1\}^{m(\lambda )}\}$, where $\lambda \in \mathbb{N}$ plays the role of the input size parameter, cannot be inverted with nonnegligible (in $\lambda$) success probability in (quantum) polynomial time.⁠⁶ We refer to any such assumption as a computational assumption. The following definition parallels Definition 1.1.

⁶

A negligible function $\varepsilon (\lambda )$ is one such that $\varepsilon (\lambda )p(\lambda )\to _{\lambda \to \infty } 0$ for any polynomial $p(\lambda )$. A nonnegligible function grows faster than any negligible function.

✖

Definition 1.2.

A language $L=(L_{yes},L_{no})$ has an interactive argument under computational assumption (A) if there exists a randomized polynomial-time verifier $V$ such that the following hold.

•

Completeness. For any $x\in L_{yes}$, there exists a prover $P$ such that $V$ accepts $P$ on input $x$ with probability at least $\frac{2}{3}$.⁠⁷

⁷

The definition of the completeness property does not explicity require $P$ to be efficient. In practice, the properties of the honest prover are discussed on a case-by-case basis, depending on the argument system considered.

✖

•

Soundness. For any $x\in L_{no}$ and any (quantum) polynomial-time prover $P^*$, $V$ accepts $P^*$ on input $x$ with probability at most $\frac{1}{3}$.

The relaxed soundness condition of an interactive argument has proved fruitful to design more efficient proof systems than are known otherwise. For example, there are arguments for languages in NP such that the total communication is only polylogarithmic in the size of the input 22; no such protocol is known in the interactive proof model. The construction of such arguments rests upon two notions: probabilistically checkable proofs and commitments. Intuitively, the computational assumption is used by the verifier to delegate parts of its own verification procedure to the prover. The notion of commitment is used to tie the prover to performing the right actions. We discuss commitments in Section 4, as they play a central role in Mahadev’s interactive argument for quantum computation. To formulate her result precisely, it only remains to introduce the formalism of quantum computation and the associated complexity class BQP. This is done in the next section.

2. Quantum computation

In this section we give a light introduction to the formalism of quantum computing. Our goal in doing so is to provide the minimal background required to formally state Mahadev’s theorem, which is given at the end of the section, as well as to describe the main ideas of her proof, introduced in the following sections. (The reader already familiar with quantum computing may directly skip ahead to the statement of Theorem 2.3 at the end of the section.)

2.1. Quantum states and observables

2.1.1. States

An $n$-qubit quantum state is specified by a density matrix, a positive semidefinite matrix $\rho$ on the $2^n$-dimensional Hilbert space $\mathcal{H}= (\mathbb{C}^2)^{\otimes n}$ such that $\rho$ has trace $1$. Density matrices generalize classical probability distributions over $n$ bits, as the latter can be represented by a probability vector $p:\{0,1\}^n\to [0,1]$ that we can embed on the diagonal of a density matrix.

Even though in general the formalism of quantum mechanics extends to arbitrary separable Hilbert spaces, for convenience in these notes Hilbert spaces always come endowed with a canonical decomposition as a tensor product of $n$ copies of $\mathbb{C}^2$, for some finite integer $n$, such that each copy of $\mathbb{C}^2$ has a canonical basis $(e_0,e_1)$. We use the notation “ket” to write the canonical basis as $|0\rangle = e_0$, $|1\rangle =e_1$, and we refer to this basis as the computational basis. A quantum state is called pure if its density matrix has rank $1$; in this case we can also represent the state as a unit vector expressed in the canonical basis $\{e_{x_1}\otimes \cdots \otimes e_{x_n},\, x\in \{0,1\}^n\}$, or $\{|e_{x_1}\cdots e_{x_n}\rangle \}$ in the more compact ket notation. An arbitrary pure state thus has an expansion $|\psi \rangle = \sum _{x\in \{0,1\}^n} \alpha _x |x\rangle$, where the $\{\alpha _x\}$ are complex coefficients such that $\sum _x |\alpha _x|^2 = 1$. The associated density matrix is the rank-$1$ projection $\rho = |\psi \rangle (|\psi \rangle )^\dagger = |\psi \rangle \langle \psi |$, where the “bra” notation $\langle \psi | = (|\psi \rangle )^\dagger$ is used for the conjugate-transpose. For a density matrix $\rho$ that lies in the tensor product of multiple spaces we write e.g. $\rho _{{\mathsf{AB}}} \in \mathcal{H}_{{\mathsf{A}}} \otimes \mathcal{H}_{{\mathsf{B}}}$ using sans serif ${\mathsf{A}}$, ${\mathsf{B}}$ to identify the different subsystems, often referred to as registers.

2.1.2. Observables

A measurement of a set of qubits is specified by an orthonormal basis of the Hilbert space associated with the qubits. The outcome of the measurement is the label of one of the basis vectors, and the probability with which each basis vector is obtained equals the squared norm of the component of the state that is in the direction of that basis vector. Formally, suppose $|\psi \rangle$ is a state in $(\mathbb{C}^2)^{\otimes n} \otimes (\mathbb{C}^2)^{\otimes m}$, and that the first $n$ qubits of $|\psi \rangle$ are measured in the orthonormal basis $\{|\phi _i\rangle \}_{i\in 1,\ldots , 2^n}$ of $(\mathbb{C}^2)^{\otimes n}$. To compute the probability of the $i$th outcome being obtained, we expand $|\psi \rangle$ in the basis $\{|\phi _i\rangle \}$ as

$$\begin{equation*} |\psi \rangle \,=\, \sum _{i=1}^{2^n} \,|\phi _i\rangle \otimes |\phi '_i\rangle \;, \end{equation*}$$

where the $|\phi '_i\rangle$ are arbitrary vectors in $(\mathbb{C}^2)^{\otimes m}$ (not necessarily normalized or orthogonal). The probability of the $i$th outcome is given by $\| |\phi '_i\rangle \|^2$. It will later be important to remember that a measurement collapses the state: once the outcome $i$ has been obtained and recorded, the state undergoes a nonunitary evolution $|\psi \rangle \mapsto |\psi _i\rangle =\frac{ |\phi _i\rangle |\phi '_i\rangle }{\||\phi '_i\rangle \|}$.⁠⁸

⁸

If the conflict between the statements that “quantum mechanics requires all evolutions to be unitary” and “a measurement is an irreversible process” puts you ill at ease, you are not alone.

✖

A measurement in the basis $\{|\phi _i\rangle \}$, together with a choice of a real number $\lambda _i$ associated with each outcome $i$, can be succinctly represented as an observable $O = \sum _i \lambda _i |\phi _i\rangle \langle \phi _i|$. For a quantum state $\rho$, the real number $\operatorname {Tr}(O\rho )$ is precisely the expectation of $\lambda _i$, under the distribution on $i$ obtained by measuring the state $\rho$ in the basis $\{|\phi _i\rangle \}$. An example is the observable associated with a measurement of a qubit in the computational basis $\{|0\rangle ,|1\rangle \}$, labeling the first outcome “$1$” and the second “$-1$”. The associated observable is the Pauli $\sigma _Z$ matrix,

$$\begin{equation*} \sigma _Z \,=\, |0\rangle \!\langle 0|-|1\rangle \!\langle 1|\,=\, \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}\;. \end{equation*}$$

Similarly, a measurement in the Hadamard basis $\{H|0\rangle ,H|1\rangle \}$ is represented by the Pauli $\sigma _X$ observable,

$$\begin{equation*} \sigma _X \,=\, H\sigma _Z H^\dagger \,=\,\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}\;. \end{equation*}$$

2.2. Circuits

Evolution in quantum mechanics is unitary. Given a unitary $U$, a pure state $|\psi \rangle$ evolves as $|\psi \rangle \mapsto U |\psi \rangle$, and a density matrix $\rho$ evolves as $\rho \mapsto U\rho U^\dagger$.

Not every unitary requires the same amount of resources to be implemented. Multiple models have been introduced to evaluate the complexity of implementing a unitary transformation. These include quantum Turing machines, the quantum circuit model, measurement-based computation, adiabatic computation, topological computation, and others. All these models have been shown equivalent up to a polynomial rescaling of the resources required. For our purposes, the simplest and most convenient model is the circuit model that we describe next.

In the circuit model, in order to implement an $n$-qubit unitary $U$, the unitary must first be decomposed as a product $U = U_T\cdots U_1$, where each $U_i$ is a unitary that acts nontrivially on at most two qubits; i.e., it can be written as a tensor product of a unitary on $\mathbb{C}^2 \otimes \mathbb{C}^2$ with the identity on the remaining space. Moreover, each $U_i$ should be taken from a finite gate set of allowed operations on the computer. A widely used gate set is $\{H,T,CNOT\}$, where $H = \frac{1}{\sqrt {2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ is the Hadamard gate, $T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi /4} \end{pmatrix}$ is the $T$ (sometimes also called $\pi /8$) gate, and CNOT is the two-qubit unitary that sends $|a\rangle |b\rangle \mapsto |a\rangle |a\oplus b\rangle$ for any $a,b\in \{0,1\}$.

A fundamental theorem in quantum computing, the Solovay–Kitaev theorem, states that for the purpose of efficient circuit representation any finite set of $1$ and $2$-qubit gates is as good as any other, as long as it generates a dense subgroup in $SU(2)$ (which is the case for the above-defined set). More formally,

Theorem 2.1 (Solovay and Kitaev, 1997).

There is a constant $c$ such that for any finite gate set $G \subseteq SU(2)$ such that the group $\langle G \rangle$ generated by $G$ is dense in $SU(2)$ and $G$ is closed under inverse, for any $\varepsilon >0$ there is an $\ell = O(\log ^c(1/\varepsilon ))$ such that $G^\ell$ is an $\varepsilon$-net in $SU(2)$.⁠⁹

⁹

An $\varepsilon$-net is a set of points $S\subseteq SU(2)$ such that for all $U\in SU(2)$, there is $V\in S$ such that $\|U-V\|\leq \varepsilon$. Here the norm is the operator norm, but any norm would give essentially the same result since the space has small dimension.

✖

We can now define the class BQP of problems that we are concerned about.

Definition 2.2.

A promise language $L = (L_{yes},L_{no})$ is in BQP if there exists a classical deterministic polynomial-time Turing machine such that, on input $x\in L_{yes}\cup L_{no}$ the Turing machine returns the description of a quantum circuit $C$ over the gate set $\{H,T,CNOT\}$, together with a specially designated output qubit for the circuit, such that the following hold.

•

If $x\in L_{yes}$, then the probability that a measurement of the output qubit of $C$, when all input qubits are initialized to the $|0\rangle$ state, is $1$, is at least $\frac{2}{3}$;

•

If $x\in L_{no}$, then the same probability is at most $\frac{1}{3}$.

Due to the fact that quantum gates are by necessity reversible, it may not be immediately obvious that quantum computations generalize classical computation. In fact, given a function $f:\{0,1\}^n \to \{0,1\}^m$ specified by a classical circuit, it is always possible to devise a quantum circuit of comparable size for the unitary $U_f$ that maps $|x\rangle |b\rangle$ to $|x\rangle |f(x) \oplus b\rangle$ for $x\in \{0,1\}^n$, $b\in \{0,1\}^m$. This can be achieved by showing that any classical circuit over, say, $\{AND,OR,NOT\}$ can be efficiently simulated by a reversible circuit; we omit the details. We often consider the application of the unitary $U_f$ in superposition: by linearity,

$$\begin{equation*} U_f : \quad \sum _{x\in \{0,1\}^n} \alpha _x |x\rangle |0^m\rangle \mapsto \sum _{x\in \{0,1\}^n} \alpha _x |x\rangle |f(x)\rangle \;. \end{equation*}$$

We close this section by stating the main result that these notes aim to present. The computational assumption that underlies soundness of the interactive argument, the learning with errors assumption, is a standard assumption in post-quantum cryptography (classical cryptography designed to be secure against quantum adversaries) that we review in Section 7.

Theorem 2.3 (Mahadev, 2018).

Any language in BQP has an interactive argument that is computationally sound against quantum polynomial-time provers under the LWE assumption. Moreover, the verifier runs in probabilistic polynomial time, the honest prover can be executed in quantum polynomial-time, and the interaction between verifier and prover consists of two rounds (four messages) only.

It is an important open question if the same theorem can be stated in the formalism of interactive proofs, instead of arguments (i.e., without making a computational assumption on the cheating prover), while still keeping the condition that the honest prover can be executed in quantum polynomial time. Intuitively, in Mahadev’s proof system the post-quantum cryptographic assumption is used to restore symmetry between the quantum prover and the less powerful classical verifier. A specific cryptographic construction, a quantum commitment scheme, is used to “tie the prover’s hands” in a way such that it has no choice but to implement the required computation—unless it has the power to break the cryptographic assumption. Nevertheless, while it is clear how the assumption is leveraged in the design of the protocol, it is not known whether one could do without it.

3. Certificates for computation

The first step in the proof of Theorem 2.3 is to identify a quantum certificate for the validity of a given quantum computation (i.e., a certificate that the probability that a quantum circuit provided as input returns the outcome “$1$”, when all input qubits are initialized to the $|0\rangle$ state, is at least $\frac{2}{3}$; cf. Definition 2.2). This is achieved by the main theorem of this section, Theorem 3.1, that is due to Kitaev and predates Mahadev’s work. In the following sections we will show how the existence of the kind of certificate provided by Theorem 3.1 can be verified using an interactive argument with a classical verifier.

We first consider the case of a classical computation. Given the description of a classical circuit as input, what is a good certificate for the claim that the circuit returns the value $1$ when all input bits are initialized to the $0$ state? While such a certificate is not really needed, as the verifier can simply execute the circuit by itself, this solution does not generalize well to the case of a quantum circuit and a classical verifier. In the following section we leverage the theory of NP-completeness to identify a particular kind of certificate for the validity of a classical circuit that has the advantage that it will generalize to the case of quantum circuits.

3.1. Warmup: the Ising spin problem

We consider a problem from classical statistical physics and show how to reduce the verification of a classical computation to it. Consider a graph with $n$ vertices, such that each vertex $i\in \{1,\ldots ,n\}$ is associated a value (or state) $\sigma _i\in \{0,1\}$, and each edge $(i,j)$ is associated a real weight (or coupling constant) $J_{ij}$ such that $|J_{ij}|\leq 1$. (See Figure 3.) Vertices represent particles that can be in one of two states, $\sigma _i=0$ or $\sigma _i=1$, and edges represent interactions between particles, where the interaction can be attractive ($J_{ij} \geq 0$) or repulsive ($J_{ij}<0$). The energy of a configuration $\sigma \in \{0,1\}^n$ is defined as⁠¹⁰

¹⁰

Technically the expression in 3.1 can take negative values, which may not seem appropriate for an “energy”. Correcting this is a matter of introducing an additive shift.

✖

$$\begin{equation} H_{ising}(\sigma ) \,=\, - \sum _{(i,j)} \,J_{ij}\, (-1)^{\sigma _i+ \sigma _j}\;. {\tag{3.1}} \end{equation}$$

Informally, the energy functional (a.k.a. Hamiltonian) $H_{ising}$ measures the number of interaction constraints that are not satisfied by an assignment $\sigma$, with each violation giving a penalty of $|J_{ij}|$. It is well-known that the problem of deciding, given $n$ as input, the coefficients $J_{ij}$, and two thresholds $a,b$ such that $b-a$ is at least a constant independent of $n$,⁠¹¹ whether the minimum of $H_{ising}$ over all $\sigma \in \{0,1\}^n$ is less than $a$, or larger than $b$, is an NP-complete problem (i.e., any problem in NP reduces to it); moreover, this holds even for the case where $J_{ij}\in \{-1,0,1\}$ for all $(i,j)$.

¹¹

It is typical to normalize $H_{ising}$ by dividing by its norm $\sum _{i,j} |J_{ij}|$, in which case the promise on the gap $b-a$ becomes that it is at least an inverse polynomial in $n$.

✖

To understand why the Ising problem is as hard as any problem in NP, let us see how we can reduce to it the problem of deciding whether, given a classical circuit $\mathcal{C}$ acting on $n+m+r$ bits and an input string $x\in \{0,1\}^n$, there exists a string $w\in \{0,1\}^m$ such that the circuit accepts $(x,w,0^r)$. By definition any problem in NP can be expressed in this form, with $x$ as the input, $w$ as the witness, and $\mathcal{C}$ as the verifier’s circuit. In general $\mathcal{C}$ is specified by a sequence of gates $(C_1,\ldots ,C_\ell )$ taken from some fixed gate set, that we may without loss of generality restrict to the sole NAND gate.⁠¹² Next consider the tableau of the computation performed by the circuit $\mathcal{C}$. (See also Figure 4.) This is simply a list of values associated with each wire in the circuit: the input wires (initialized to $(x,w,0^r)$), the output wire of any gate in the circuit, and the final output wire (that should equal $1$, which stands for “accept”). Given a tableau, it is possible to verify that the tableau is correct by checking the propagation of each gate, one at a time: if the inputs to a NAND gate are $\sigma _{i_1},\sigma _{i_2}\in \{0,1\}$, the output should be $(\sigma _{i_3}=\sigma _{i_1},\sigma _{i_4} = 1-\sigma _{i_1}\sigma _{i_2})$. Wires corresponding to the input string $x$ should be initialized to the corresponding input bit, whereas wires associated with the witness string $w$ can take arbitrary values. We can express this set of constraints as a Hamiltonian $H_\mathcal{C}:\{0,1\}^T \to \mathbb{R}$, where $T$ is the total number of wires in the circuit:

¹²

The NAND gate maps $(a,b)$ to $(a,1-ab)$. (The first output is included for convenience, to keep the number of wires constant, but is not necessary.) It is a universal gate, meaning that any circuit can be simulated by one made of NAND games only with a polynomial overhead in the total number of gates.

✖

$$\begin{equation} H_\mathcal{C}\,=\, H_{in} + H_{prop} + H_{out}\;, {\tag{3.2}} \end{equation}$$

where $H_{in}$ is a summation of energy penalties⁠¹³ $1_{\sigma _{i_k}\neq x_k} = \frac{1}{2}(1-(-1)^{x_k+\sigma _{i_k}})$ with $i_k$ the input wire associated with the $k$th bit of $x$ and $1_{\sigma _{i_j}\neq 0}$ with $i_j$ the input wire associated with the $j$th ancilla bit, $H_{prop}$ a summation of penalties of the form $1_{\sigma _{i_k}\neq \sigma _{i_j}} + 1_{\sigma _{i_{k+1}}\neq 1-\sigma _{i_j}\sigma _{i_\ell }}$ for each NAND gate mapping $(i_j,i_\ell )$ to $(i_k,i_{k+1})$, and $H_{out}$ consists of a single penalty term $1_{\sigma _{i_T}\neq 1}$ for $i_T$ the output wire. Then, $H_\mathcal{C}$ is such that there exists $\sigma$ such that $H_\mathcal{C}(\sigma )=0$ if and only if there is a witness $w$ such that $\mathcal{C}$ accepts $(x,w,0^r)$; otherwise, $H_\mathcal{C}(\sigma )\geq 1$ for all $\sigma$.

¹³

We use the notation $1_E$ for the indicator that event $E$ occurs.

✖

Note that $H_\mathcal{C}$ does not quite have the form 3.1 of an Ising spin Hamiltonian yet: some of its terms involve three variables at a time, and moreover not all terms are directly expressed as a function of the parity of the sum of two variables. With a little more work using so-called gadgets, it is possible to complete the reduction and find an $H'_\mathcal{C}$ that is equivalent to $H_\mathcal{C}$ (in terms of capturing the same decision problem) but is of the form 3.1 6.

Using the trivial observation that P $\subseteq$ NP (any language that can be efficiently decided can be efficiently verified by ignoring the witness and performing the efficient decision procedure), it follows from the above discussion that the problem of deciding whether a classical circuit returns $1$ on the all $0$ input, which is complete for P, can be efficiently reduced to the problem of deciding whether an Ising Hamiltonian has a configuration with energy at most some threshold value $a$ (that can be efficiently determined by following the steps of the reduction), or if all configurations have energy at least $b$, for some $b$ such that $b-a = \Omega (1)$. (Explicitly, the Hamiltonian is obtained by adding penalty terms $1_{\sigma _{i_k}\neq 0}$ for all input wires associated to $w$ to the Hamiltonian $H_\mathcal{C}$ obtained from the reduction described in the preceding paragraphs.)

Our next step is to devise a quantum analogue of this reduction.

3.2. Quantum spin problems

We can interpret the Hamiltonian $H_{ising}$ introduced in 3.1 as an energy functional that associates an energy to any configuration $\sigma$. In quantum mechanics, a Hamiltonian is any linear operator on Hilbert space, with the restriction that the operator should be Hermitian (and bounded; for convenience here we only consider finite-dimensional spaces, so that the latter condition is automatic). The interpretation is that the Hamiltonian associates a definite energy $\lambda _i \in \mathbb{R}$ to any quantum state that happens to be in one of the Hamiltonian’s eigenstates $|\phi _i\rangle$. The energy of an arbitrary state $\rho$ is then computed as $\operatorname {Tr}(H\rho )$.⁠¹⁴ Often it is also required that the Hamiltonian be local, meaning that