Verification of Quantum Computation: An Overview of Existing Approaches

The concept of blind computing is highly relevant to quantum verification. Here, we simply give a succinct outline of the subject. For more details, see this review of blind quantum computing protocols by Fitzsimons [34] as well as [35‐39]. Note that, while the review of Fitzsimons covers all of the material presented in this section (and more), we restate the main ideas, so that our review is self-consistent and also in order to establish some of the notation that is used throughout the rest of the paper.

Blindness is related to the idea of computing on encrypted data [40]. Suppose a client has some input x and would like to compute a function f of that input, however, evaluating the function directly is computationally infeasible for the client. Luckily, the client has access to a server with the ability to evaluate \(f(x)\). The problem is that the client does not trust the server with the input x, since it might involve private or secret information (e.g. medical records, military secrets, proprietary information etc). The client does, however, have the ability to encrypt x, using some encryption procedure \(\mathcal {E}\), to a ciphertext \(y \leftarrow \mathcal {E}(x)\). As long as this encryption procedure hides x sufficiently well, the client can send y to the server and receive in return (potentially after some interaction with the server) a string z which decrypts to \(f(x)\). In other words, \(f(x) \leftarrow \mathcal {D}(z)\), where \(\mathcal {D}\) is a decryption procedure that can be performed efficiently by the client.⁶ The encryption procedure can, roughly, provide two types of security: computational or information-theoretic. Computational security means that the protocol is secure as long as certain computational assumptions are true (for instance that the server is unable to invert one-way functions). Information-theoretic security (sometimes referred to as unconditional security), on the other hand, guarantees that the protocol is secure even against a server of unbounded computational power. See [45] for more details on these topics.

In the quantum setting, the situation is similar to that of \(\mathsf {QPIP}\) protocols: the client is restricted to \(\mathsf {BPP}\) computations, but has some limited quantum capabilities, whereas the server is a \(\mathsf {BQP}\) machine. Thus, the client would like to delegate \(\mathsf {BQP}\) functions to the server, while keeping the input and the output hidden. The first solution to this problem was provided by Childs [35]. His protocol achieves information-theoretic security but also requires the client and the server to exchange quantum messages for a number of rounds that is proportional to the size of the computation. This was later improved in a protocol by Broadbent et al. [36], known as universal blind quantum computing (UBQC), which maintained information-theoretic security but reduced the quantum communication to a single message from the client to the server. UBQC still requires the client and the server to have a total communication which is proportional to the size of the computation, however, apart from the first quantum message, the interaction is purely classical. Let us now state the definition of perfect, or information-theoretic, blindness from [36]:

The definition is essentially saying that the server’s “view” of the protocol should be independent of the input, when given the length of the input. This view consists, on the one hand, of the classical information he receives, which is independent of X, given \(L(X)\). On the other hand, for any fixed choice of this classical information, his quantum state should also be independent of X, given \(L(X)\). Note that the definition can be extended to the case of multiple servers as well. To provide intuition for how a protocol can achieve blindness, we will briefly recap the main ideas from [35, 36]. We start by considering the quantum one-time pad.

This subsection is dedicated to the two protocols presented in [25, 26] by Aharonov et al. These protocols are extensions of Quantum Authentication Schemes (QAS), a security primitive introduced in [52] by Barnum et al. A QAS is a scheme for transmitting a quantum state over an insecure quantum channel and being able to indicate whether the state was corrupted or not. More precisely, a QAS involves a sender and a receiver. The sender has some quantum state \({\left \vert {\psi }\right \rangle }{\left \vert {flag}\right \rangle }\) that it would like to send to the receiver over an insecure channel. The state \({\left \vert {\psi }\right \rangle }\) is the one to be authenticated, while \({\left \vert {flag}\right \rangle }\) is an indicator state used to check whether the authentication was performed successfully. We will assume that \({\left \vert {flag}\right \rangle }\) starts in the state \({\left \vert {acc}\right \rangle }\). It is also assumed that the sender and the receiver share some classical key k, drawn from a probability distribution \(p(k)\). To be able to detect the effects of the insecure channel on the state, the sender will first apply some encoding procedure Enc_k thus obtaining \(\rho = {\sum }_{k} p(k) Enc_{k}({\left \vert {\psi }\right \rangle }{\left \vert {acc}\right \rangle })\). This state is then sent over the quantum channel where it can be tampered with by an eavesdropper resulting in a new state \(\rho ^{\prime }\). The receiver, will then apply a decoding procedure to this state, resulting in \(Dec_{k}(\rho ^{\prime })\) and decide whether to accept or reject by measuring the flag subsystem.¹⁵ Similar to verification, this protocol must satisfy two properties:

To make the similarities between QAS and prepare-and-send protocols more explicit, suppose that, in the above scheme, the receiver were trying to authenticate the state \(U{\left \vert {\psi }\right \rangle }\)instead of\({\left \vert {\psi }\right \rangle }\), for some unitary U. In that case, we could view the sender as the verifier at the beginning of the protocol, the eavesdropper as the prover and the receiver as the verifier at the end of the protocol. This is illustrated in Fig. 4, reproduced from [47]. If one could therefore augment a QAS scheme with the ability of applying a quantum circuit on the state, while keeping it authenticated, then one would essentially have a prepare-and-send verification protocol. This is what is achieved by the two protocols of Aharonov et al. (Fig. 4).

To see how this lemma is applied, recall that any CPTP map admits a Kraus decomposition, so we can express the eavesdropper’s action as: where, \(\{ K_{i} \}_{i}\) is the set of Kraus operators, satisfying: Additionally, recall that the n-qubit Pauli group is a basis for all \(2^{n} \times 2^{n}\) matrices, which means that we can express each Kraus operator as: where j ranges over all indices for n-qubit Pauli operators and \(\{ \alpha _{ij} \}_{i,j}\) is a set of complex numbers such that: For simplicity, assume that the phase information of each Pauli operator, i.e. whether it is \(+ 1\), \(-1\), \(+i\) or \(-i\), is absorbed in the \(\alpha _{ij}\) terms. One can then re-express the eavesdropper’s deviation as:

We would now like to use Lemma 1 to see how this deviation affects the encoded state. Given that the encoding procedure involves applying a random Clifford operation to the initial state, which we will denote \(\left \vert {{\Psi }_{in}}\right \rangle = \left \vert {\psi }\right \rangle \left \vert {acc}\right \rangle \), the state received by the eavesdropper will be:

Acting with \(\mathcal {E}\) on this state and using (21) yields: The receiver takes this state and applies the decoding operation, which involves inverting the Clifford that was applied by the sender. This will produce the state: Finally, using Lemma 1 we can see that all terms which act with different Pauli operations on both sides (i.e. \(j \neq k\)) will vanish, resulting in:

Let us take a step back and understand what happened. We saw that any general map can be expressed as a combination of Pauli operators acting on both sides of the target state, \(\rho \). Importantly, the Pauli operators on both sides needed not be equal. However, if the target state is an equal mixture of Clifford terms acting on some other state (in our case \(\left \vert {{\Psi }_{in}}\right \rangle \left \langle {{\Psi }_{in}}\right \rangle \)), which are then “undone” by the decoding procedure, the Clifford twirl lemma makes all non-equal Pauli terms vanish. In the resulting state, σ, we notice that each Pauli term is conjugated by Clifford operators from the set \(\mathfrak {C}_{t}\). We know that conjugating a Pauli matrix by a Clifford operator results in a new Pauli matrix. Moreover, we know that for all j it is the case that: In other words, averaging over the Clifford group results in an equal mixture of all Pauli operations. From this and since \(\alpha _{ij}\alpha ^{*}_{ij} = |\alpha _{ij}|^{2}\) is a positive real number and \({\sum }_{ij} \alpha _{ij}\alpha ^{*}_{ij} = 1\), the resulting state is a uniform convex combination of Pauli operators acting on the initial state. Mathematically, this means: where \(0 \leq \beta \leq 1\).

The last element in the proof is to compute \(Tr(P_{incorrect} \sigma )\). Since the first term in the mixture is the ideal state, we will be left with: The terms in the summation will be non-zero whenever \(P_{i}\) acts as identity on the flag subsystem. The number of such terms can be computed to be exactly \(4^{n} 2^{m} - 1\) and using the fact that \(t = m + n\) and \(1 - \beta \leq 1\), we have: concluding the proof.

As mentioned, in all prepare-and-send protocols we assume that the verifier will prepare some state \({\left \vert {\psi }\right \rangle }\) on which it wants to apply a quantum circuit denoted \(\mathcal {C}\). Since we are assuming that the verifier has a constant-size quantum device, the state \({\left \vert {\psi }\right \rangle }\) will be a product state, i.e. \({\left \vert {\psi }\right \rangle } = {\left \vert {\psi _{1}}\right \rangle } \otimes {\left \vert {\psi _{2}}\right \rangle } \otimes ... \otimes {\left \vert {\psi _{n}}\right \rangle }\). For simplicity, assume each \({\left \vert {\psi _{i}}\right \rangle }\) is one qubit, though any constant number of qubits is allowed. In Clifford-QAS VQC the verifier will use the prover as an untrusted quantum storage device. Specifically, each \({\left \vert {\psi _{i}}\right \rangle }\), from \({\left \vert {\psi }\right \rangle }\), will be paired with a constant-size flag system in the accept state, \({\left \vert {acc}\right \rangle }\), resulting in a block of the form \({\left \vert {block_{i}}\right \rangle } = {\left \vert {\psi _{i}}\right \rangle }{\left \vert {acc}\right \rangle }\). Each block will be encoded, by having a random Clifford operation applied on top of it. The verifier prepares these blocks, one at a time, for all \(i \in \{1,... n\}\), and sends them to the prover. The prover is then asked to return pairs of blocks to the verifier so that she may apply gates from \(\mathcal {C}\) on them (after undoing the Clifford operations). The verifier then applies new random Clifford operations on the blocks and sends them back to the prover. The process continues until all gates in \(\mathcal {C}\) have been applied.

But what if the prover corrupts the state or deviates in some way? This is where the QAS enters the picture. Since each block has a random Clifford operation applied, the idea is to have the verifier use the Clifford QAS scheme to ensure that the quantum state remains authenticated after each gate in the quantum circuit is applied. In other words, if the prover attempts to deviate at any point resulting in a corrupted state, this should be detected by the authentication scheme. Putting everything together, the protocol works as follows:

We can see that the security of this protocol reduces to the security of the Clifford QAS. Moreover, it is also clear that if the prover behaves honestly, then the verifier will obtain the correct output state exactly. Hence:

This result is identical to the Clifford twirl lemma, except the Clifford operations are replaced with Pauli operators.²⁰ The result is also valid for qubits.

Using these two results, and the ideas from the Clifford QAS scheme, it is not difficult to prove the security of the above described authentication scheme. As before, the eavesdropper’s map is decomposed into Kraus operators which are then expanded into Pauli operations. Since the sender’s state is one-time padded (and the receiver will undo the one-time pad), the Pauli twirl lemma will turn the eavesdropper’s deviation into a convex combination of Pauli deviations: which can be split into the identity and non-identity Pauli terms: where \(\beta _{Q}\) are positive real coefficients satisfying: The receiver takes this state and applies the inverse encoding operation, resulting in: But now we know that \(\epsilon = Tr(P_{incorrect} \rho )\), and using Lemma 3 together with the facts that \(Tr(P_{incorrect} {\left \vert {{\Psi }_{in}}\right \rangle }{\left \langle {{\Psi }_{in}}\right \vert }) = 0\) and that the \(\beta _{Q}\) coefficients sum to 1 we end up with:

There are two more aspects to be mentioned before giving the steps of the Poly-QAS VQC protocol. The first is that the encoding procedure for the signed polynomial code is implemented using the following interpolation operation: The inverse operation \(D_{k}^{\dagger }\) can be though of as a decoding of one term from the superposition in (31). Akin to Lemma 3, the signed polynomial code has the property that, when averaging over all sign keys, k, if such a term had a non-identity Pauli applied to it, when decoding it with \(D_{k}^{\dagger }\), the probability that its last d qudits are not \(\left \vert {0}\right \rangle \) states is upper bounded by \(2^{-d}\).

The second aspect is that, as mentioned, the signed polynomial code is transversal for Clifford operations. However, in order to apply non-Clifford operations it is necessary to measure encoded states together with so-called magic states (which will also be encoded). This manner of performing gates is known as gate teleportation [54]. The target state, on which we want to apply a non-Clifford operation, and the magic state are first entangled using a Clifford operation and then the magic state is measured in the computational basis. The effect of the measurement is to have a non-Clifford operation applied on the target state, along with Pauli errors which depend on the measurement outcome. For the non-Clifford operations, Aharonov et al use Toffoli gates.²¹

Given all of these, the Poly-QAS VQC protocol works as follows: The protocol is schematically illustrated in Fig. 5.

As with the previous protocol, the security is based on the security of the authentication scheme. However, there is a significant difference. In the Clifford-QAS VQC protocol, one could always assume that the state received by the verifier was the correctly encoded state with a deviation on top that was independent of this encoding. However, in the Poly-QAS VQC protocol, the quantum state is never returned to the verifier and, moreover, the prover’s instructed actions on this state are adaptive based on the responses of the verifier. Since the prover is free to deviate at any point throughout the protocol, if we try to commute all of his deviations to the end (i.e. view the output state as the correct state resulting from an honest run of the protocol, with a deviation on top that is independent of the secret parameters), we find that the output state will have a deviation on top which depends on the verifier’s responses. Since the verifier’s responses depend on the secret keys, we cannot directly use the security of the authentication scheme to prove that the protocol is 2^−d-verifiable.

The solution, as explained in [26], is to consider the state of the entire protocol comprising of the prover’s system, the verifier’s system and the transcript of all classical messages exchanged during the protocol. For a fixed interaction transcript, the prover’s attacks can be commuted to the end of the protocol. This is because, if the transcript is fixed, there is no dependency of the prover’s operations on the verifier’s messages. We simply view all of his operations as unitaries acting on the joint system of his private memory, the input quantum state and the transcript. One can then use Lemma 2 and Lemma 3 to bound the projection of this state onto the incorrect subspace with acceptance. The whole state, however, will be a mixture of all possible interaction transcripts, but since each term is bounded and the probabilities of the terms in the mixture must add up to one, it follows that the protocol is \(2^{-d}\)-verifiable:

Let us briefly summarize the two protocols in terms of the verifier’s resources. In both protocols, if one fixes the security parameter, \(\epsilon \), the verifier must have a O(log(1/𝜖))-size quantum computer. Additionally, both protocols are interactive with the total amount of communication (number of messages times the size of each message) being upper bounded by \(O(|\mathcal {C}| \cdot log(1/\epsilon ))\), where \(\mathcal {C}\) is the quantum circuit to be performed.²³ However, in Clifford-QAS VQC, this communication is quantum whereas in Poly-QAS VQC only one quantum message is sent at the beginning of the protocol and the rest of the interaction is classical.

Before ending this subsection, we also mention the result of Broadbent et al. from [55]. This result generalises the use of quantum authentication codes for achieving verification of delegated quantum computation (not limited to decision problems). Moreover, the authors prove the security of these schemes in the universal composability framework, which allows for secure composition of cryptographic protocols and primitives [56].

In this subsection we discuss Verifiable Universal Blind Quantum Computing (VUBQC), which was developed by Fitzsimons and Kashefi in [27]. The protocol is written in the language of MBQC and relies on two essential ideas. The first is that an MBQC computation can be performed blindly, using UBQC, as described in Section 1.1. The second is the idea of embedding checks or traps in a computation in order to verify that it was performed correctly. Blindness will ensure that these checks remain hidden and so any deviation by the prover will have a high chance of triggering a trap. Notice that this is similar to the QAS-based approaches where the input state has a flag subsystem appended to it in order to detect deviations and the whole state has been encoded in some way so as to hide the input and the flag subsystem. This will lead to a similar proof of security. However, as we will see, the differences arising from using MBQC and UBQC lead to a reduction in the quantum resources of the verifier. In particular, in VUBQC the verifier requires only the ability to prepare single qubit states, which will be sent to the prover, in contrast to the QAS-based protocols which required the verifier to have a constant-size quantum computer.

Recall the main steps for performing UBQC. The client, Alice, sends qubits of the form \({\left \vert {+_{\theta _{i}}}\right \rangle }\) to Bob, the server, and instructs him to entangle them according to a graph structure, G, corresponding to some universal graph state. She then asks him to measure qubits in this graph state at angles \(\delta _{i} = \phi ^{\prime }_{i} + \theta _{i} + r_{i} \pi \), where \(\phi ^{\prime }_{i}\) is the corrected computation angle and \(r_{i} \pi \) acts a random \(\mathsf {Z}\) operation which flips the measurement outcome. Alice will use the measurement outcomes, denoted \(b_{i}\), provided by Bob to update the computation angles for future measurements. Throughout the protocol, Bob’s perspective is that the states, measurements and measurement outcomes are indistinguishable from random. Once all measurements have been performed, Alice will undo the \(r_{i}\) padding of the final outcomes and recover her output. Of course, UBQC does not provide any guarantee that the output she gets is the correct one, since Bob could have deviated from her instructions.

Transitioning to VUBQC, we will identify Alice as the verifier and Bob as the prover. To augment UBQC with the ability to detect malicious behaviour on the prover’s part, the verifier will introduce traps in the computation. How will she do this? Recall that the qubits which will comprise \({\left \vert {G}\right \rangle }\) need to be entangled with the \(\mathsf {CZ}\) operation. Of course, for X Y-plane states \(\mathsf {CZ}\) does indeed entangle the states. However, if either qubit, on which \(\mathsf {CZ}\) acts, is \({\left \vert {0}\right \rangle }\) or \({\left \vert {1}\right \rangle }\), then no entanglement is created. So suppose that we have a \({\left \vert {+_{\theta }}\right \rangle }\) qubit whose neighbours, according to G, are computational basis states. Then, this qubit will remain disentangled from the rest of the qubits in \({\left \vert {G}\right \rangle }\). This means that if the qubit is measured at its preparation angle, the outcome will be deterministic. The verifier can exploit this fact to certify that the prover is performing the correct measurements. Such states are referred to as trap qubits, whereas the \({\left \vert {0}\right \rangle }\), \({\left \vert {1}\right \rangle }\) neighbours are referred to as dummy qubits. Importantly, as long as G’s structure remains that of a universal graph state²⁴ and as long as the dummy qubits and the traps are chosen at random, adding these extra states as part of the UBQC computation will not affect the blindness of the protocol. The implication of this is that the prover will be completely unaware of the positions of the traps and dummies. The traps effectively play a role that is similar to that of the flag subsystem in the authentication-based protocols. The dummies, on the other hand, are there to ensure that the traps do not get entangled with the rest of qubits in the graph state. They also serve another purpose. When a dummy is in a \({\left \vert {1}\right \rangle }\) state, and a \(\mathsf {CZ}\) acts on it and a trap qubit, in the state \({\left \vert {+_{\theta }}\right \rangle }\), the effect is to “flip” the trap to \({\left \vert {-_{\theta }}\right \rangle }\) (alternatively \({\left \vert {-_{\theta }}\right \rangle }\) would have been flipped to \({\left \vert {+_{\theta }}\right \rangle }\)). This means that if the trap is measured at its preparation angle, \(\theta \), the measurement outcome will also be flipped, with respect to the initial preparation. Conversely, if the dummy was initially in the state \({\left \vert {0}\right \rangle }\), then no flip occurs. Traps and dummies, therefore, serve to also certify that the prover is performing the \(\mathsf {CZ}\) operations correctly. Thus, by using the traps (and the dummies), the verifier can check both the prover’s measurements and his entangling operations and hence verify his MBQC computation.

We are now ready to present the steps of VUBQC:

The protocol is illustrated schematically in Fig. 6, where all the parameters have been labelled by their position, \((i, j)\), in a rectangular cluster state.

One can see that VUBQC has correctness \(\delta = 1\), since if the prover behaves honestly then all trap measurements will produce the correct result and the computation will have been performed correctly. What about verifiability? We will first answer this question for the case where there is a single trap qubit (T = 1) at a uniformly random position in \({\left \vert {G}\right \rangle }\), denoted \({\left \vert {+_{\theta _{t}}}\right \rangle }\). Adopting a similar notation to that from [27], we let: denote the outcome density operator of all classical and quantum messages exchanged between the verifier and the prover throughout the protocol, excluding the last round of measurements (which corresponds to measuring the output of the computation). Additionally, \(\nu \) denotes the set of secret parameters of Alice (i.e. the positions of the traps and dummies as well as the sets \(\{ \phi _{i} \}_{i}\), \(\{ \theta _{i} \}_{i}\) and \(\{ r_{i} \}_{i}\)); j ranges over the possible strategies of the prover²⁷ with \(j = 0\) corresponding to the honest strategy; \(\mathbf {s}\) is a binary vector which ranges over all possible corrected values of the measurement outcomes sent by the prover; lastly, \(\rho _{\nu , j}^{\mathbf {s}}\) is the state of the unmeasured qubits, representing the output state of the computation (prior to the final measurement). To match Definition 2, one also considers: to be the projection onto the orthogonal complement of the correct output together with the trap state being projected onto acceptance. The dependence on \(\nu \), for the trap qubit, arises because the acceptance outcome depends on the states of the dummy neighbors for that qubit. This is because if one of the dummies is \({\left \vert {1}\right \rangle }\), the \(\mathsf {CZ}\) operation has the effect of flipping \({\left \vert {+_{\theta _{t}}}\right \rangle }\) to \({\left \vert {-_{\theta _{t}}}\right \rangle }\). Additionally, \(\nu \) also encodes the position of this trap, in the graph state, as well as the \(\mathsf {Z}\) flip specified by the \(r_{i}\) parameter, for \(i=t\). One then needs to find an \(\epsilon \) such that: This is done in a manner similar to the proof of security for the Poly-QAS VQC scheme of the previous section.²⁸ Specifically, one fixes the interaction transcript for the protocol. This just means fixing the measurement angles \(\delta _{i}\), and then considering all possible transcripts compatible with the fixed angles. One can do this because UBQC guarantees that the prover learns nothing from the interaction except for, at most, an upper bound on \(|\mathcal {C}|\). This means that there will be multiple transcripts compatible with the same values for the \(\delta _{i}\)angles. It also means that any deviation that the prover performs is independent of the secret parameters of the verifier (though it can depend on the \(\delta _{i}\) angles) and can therefore be commuted to the end of the protocol. The outcome density operator \(\mathcal {B}_{j}(\nu )\) can then be expressed as the ideal outcome with a CPTP deviation, \(\mathcal {E}_{j}\), on top, that is independent of \(\nu \): The deviation \(\mathcal {E}_{j}\) is then decomposed into Kraus operators which, in turn, are decomposed into Pauli operators leading to: where \(\alpha _{kl}(j)\) (and their conjugates) are the complex coefficients for the Pauli operators. This summation can be split into the terms that act as identity on \(\mathcal {B}_{0}(\nu )\)> and those that do not. Suppose the terms that act trivially have weight \(0 \leq \beta \leq 1\), we then have: where the second term is summing over Pauli operators that act non-trivially. We use this to compute the probability of accepting an incorrect outcome, noting that \(P_{incorrect}^{\nu } \mathcal {B}_{0}(\nu ) = 0\): We now use the fact that \(P^{\nu }_{incorrect} = (I - \mathcal {C} {\left \vert {x}\right \rangle }{\left \langle {x}\right \vert } \mathcal {C}^{\dagger }) \otimes {\left \vert {+^{\nu }_{\theta _{t}}}\right \rangle } {\left \langle {+^{\nu }_{\theta _{t}}}\right \vert }\) and keep only the projection onto the trap qubit. The projection onto the space orthogonal to the correct state is a trace decreasing operation and also \((1 - \beta ) \leq 1\) hence: The summation over \(\nu \) can be broken into two summations: one over the position of the trap (and the dummies) and one over the remaining parameters. This latter sum makes the reduced state appear totally mixed to the prover (a fact which is ensured by UBQC). The above expression then becomes: where \(\nu ^{t}\) denotes the secret parameters for the trap qubit and consists of \(\theta _{t}\), \(r_{t}\) and the position of the trap in the graph. But notice that, on the identity system, the terms in which \(l \neq m\) will have no contribution to the summation. This is because at least one of the Pauli terms (either \(P_{l}\) or \(P_{m}\)) will act on the identity system. Since Pauli operators are traceless, when taking the trace these terms will be zero. For the trap system we will have: Note that we are taking \(p(\nu ^{t})\) to be the uniform distribution over these parameters. By summing over \(\theta _{t}\) and \(r_{t}\), the above expression becomes zero, whenever l≠m. This is a result of the Pauli twirl Lemma 2. Thus, only terms in which \(l = m\) will remain. Substituting this back into expression (48) leads to: In other words, the resulting state is a convex combination of Pauli deviations. The position of the trap is completely randomised so that it is equally likely that any of the N qubits is the trap. Therefore, in the above summation, there will be N terms (corresponding to the N possible positions of the trap), one of which will be zero (the one in which the non-trivial Pauli deviations act on the trap qubit). Hence: We have found that for the case of a single trap qubit, out of the total N qubits, one has \(\epsilon = 1 - \frac {1}{N}\).

If however, there are multiple trap states, the bound improves. Specifically, for a type of resource state called dotted-triple graph, the number of traps can be a constant fraction of the total number of qubits, yielding \(\epsilon = 8/9\). If the protocol is then repeated a constant number of times, d, with the verifier aborting if any of these runs gives incorrect trap outcomes, it can be shown that \(\epsilon = (8/9)^{d}\) [57]. Alternatively, if the input state and computation are encoded in an error correcting code of distance d, then one again obtains \(\epsilon = (8/9)^{d}\). This is useful if one is interested in a quantum output, or a classical bit string output. If, instead, one would only like a single bit output (i.e. the outcome of the decision problem) then sequential repetition and taking the majority outcome is sufficient. The fault tolerant encoding need not be done by the verifier. Instead, the prover will simply be instructed to prepare a larger resource state which also offers topological error-correction. See [27, 58, 59] for more details. An important observation, however, is that the fault tolerant encoding, just like in the Poly-QAS VQC protocol, is used only to boost security and not for correcting deviations arising from faulty devices. This latter case is discussed in Section 5.2. To sum up:

It should be noted that in the original construction of the protocol, the fault tolerant encoding, used for boosting security, required the use of a resource state having \(O(|\mathcal {C}|^{2})\) qubits. The importance of the dotted-triple graph construction is that it achieves the same level of security while keeping the number of qubits linear in \(|\mathcal {C}|\). The same effect is achieved by a composite protocol which combines the Poly-QAS VQC scheme, from the previous section, with VUBQC [51]. This works by having the verifier run small instances of VUBQC in order to prepare the encoded blocks used in the Poly-QAS VQC protocol. Because of the blindness property, the prover does not learn the secret keys used in the encoded blocks. The verifier can then run the Poly-QAS VQC protocol with the prover, using those blocks. This hybrid approach illustrates how composition can lead to more efficient protocols. In this case, the composite protocol maintains a single qubit preparation device for the verifier (as opposed to a O(log(1/𝜖))-size quantum computer) while also achieving linear communication complexity. We will encounter other composite protocols when reviewing entanglement-based protocols in Section 4.

Lastly, let us explicitly state the resources and overhead of the verifier throughout the VUBQC protocol. As mentioned, the verifier requires only a single-qubit preparation device, capable of preparing states of the form \(\left \vert {+_{\theta }}\right \rangle \), with \(\theta \in \{0, \pi /4, 2\pi /4, ... 7\pi /4 \}\), and \(\left \vert {0}\right \rangle \), \(\left \vert {1}\right \rangle \). The number of qubits needed is on the order of \(O(|\mathcal {C}|)\). After the qubits have been sent to the prover, the two interact classically and the size of the communication is also on the order of \(O(|\mathcal {C}|)\).

The final prepare-and-send protocol we describe is the one defined by Broadbent in [28]. While the previous approaches relied on hiding a flag subsystem or traps in either the input or the computation, this protocol has the verifier alternate between different runs designed to either test the behaviour of the prover or perform the desired quantum computation. We will refer to this as the Test-or-Compute protocol. From the prover’s perspective, the possible runs are indistinguishable from each other, thus making him unaware if he is being tested or performing the verifier’s chosen computation. Specifically, suppose the verifier would like to delegate the quantum circuit \(\mathcal {C}\) to be applied on the \({\left \vert {0}\right \rangle }^{\otimes n}\) state,²⁹ where n is the size of the input. The verifier then chooses randomly between three possible runs: It turns out that this suffices in order to test against any possible malicious behavior of the prover, with high probability.

In more detail, the protocol uses a technique for quantum computing on encrypted data, described in [60], which is similar to Childs’ protocol from Section 1.1, except it does not involve two-way quantum communication. The verifier will one-time pad either the \(\left \vert {0}\right \rangle ^{\otimes n}\) state or the \(\left \vert {+}\right \rangle ^{\otimes n}\) state and send the qubits to the prover. The prover is then instructed to apply the circuit \(\mathcal {C}\), which consists of the gates \(\mathsf {X}\), \(\mathsf {Z}\), \(\mathsf {H}\), \(\mathsf {T}\), \(\mathsf {CNOT}\). As we know, the Clifford operations commute (or normalise) with the one-time pad, so the verifier would only need to appropriately update the one-time pad to account for this. However, \(\mathsf {T}\) gates do not commute with the pad. In particular, commuting them past the \(\mathsf {X}\) gates introduces unwanted \(\mathsf {S}\) operations. To resolve this issue, the verifier will use a particular gadget which will allow the prover to apply \(\mathsf {T}\) and correct for \(\mathsf {S}\) at the same time. This gadget is shown in Fig. 7, reproduced from [28].

The gadget works in a gate teleportation fashion. For each qubit, labelled j, on which the prover should apply a \(\mathsf {T}\) gate, the verifier sends a qubit of the form \(\mathsf {X}^{d} \textsf {Z}^{c} \textsf {S}^{y} \textsf {T} {\left \vert {+}\right \rangle }\), as well as the classical bit \(x = a \oplus c \oplus y\), where a is the \(\mathsf {X}\) padding of qubit j and c, d and y are chosen at random. The verifier then instructs the prover to apply a \(\mathsf {CNOT}\) between the sent qubit and qubit j, effectively entangling them, and then measure qubit j in the computational basis. Lastly, the verifier instructs the prover to apply an \(\mathsf {S}^{x}\) gate to the sent qubit. The end result is that this qubit will be the same as the de-one-time padded qubit j but with a \(\mathsf {T}\) and a new one-time pad acting on it. Importantly, the new pad is kept secret from the prover.

The \(\mathsf {T}\) gate gadget allows the verifier to control the application of either a non-Clifford operation or a Clifford operation through gate teleportation. For note that if the verifier does not apply a \(\mathsf {T}\) gate on the qubit sent to the prover, the resulting computation is Clifford. This is what allows the verifier to switch between the computation run and the two test runs. The prover cannot distinguish between the two cases, since his side of the gadget is identical in both instances. Thus, in a test run, the computation the prover performs will be Clifford and the verifier can simply update the one-time pad, of the input, accordingly. There is, however, one complication. In an \(\mathsf {X}\)-test run, the input is \({\left \vert {0}\right \rangle }^{\otimes n}\) and should remain this way until the end of the circuit, up to qubit flips resulting from the one-time pad. But any Hadamard gate in the circuit will map \({\left \vert {0}\right \rangle }\) to \({\left \vert {+}\right \rangle }\). The same is true for \(\mathsf {Z}\)-test runs, where \({\left \vert {+}\right \rangle }\) states can be mapped to \({\left \vert {0}\right \rangle }\). To resolve this issue, Broadbent uses the following identities: The idea is to have the prover implement each Hadamard operation in \(\mathcal {C}\) by applying four \(\mathsf {H}\) gates alternating with \(\mathsf {S} = \textsf {T}^{2}\) gates. Each \(\mathsf {T}^{2}\) operation is performed by using the \(\mathsf {T}\) gate gadget twice. When the verifier chooses a computation run, she will apply the \(\mathsf {T}\) gates in the gadget and therefore, via (52), this leads to a Hadamard operation. Conversely, in a rest run, no \(\mathsf {T}\) gates are applied, hence, from (53), no Hadamard operation will act on the target qubit. Since the output is always measured, by the prover, in the computational basis, in an \(\mathsf {X}\)-test run the verifier simply checks that the de-one-time padded output is \({\left \vert {0}\right \rangle }^{\otimes n}\).

There is, in fact, an additional testing step being performed during an \(\mathsf {X}\)-test run. Consider the \(\mathsf {T}\) gadget for such a run in Fig. 8, reproduced from [28].

Note that the measurement bit, c, provided by the prover to the verifier should be an xor of the original \(\mathsf {X}\) padding of the input and the updated \(\mathsf {X}\) padding of the input. Checking the value of this bit allows the verifier to test that the gadget was applied correctly.

What about the \(\mathsf {Z}\)-test run? In that case, the output should be the \({\left \vert {+}\right \rangle }^{\otimes n}\) which, upon measurement, should collapse with equal probability into any of the \(2^{n}\) possible binary strings. The verifier does not test for this. Instead, each \(\mathsf {H}\) gate that should be applied by the prover has the effect of switching between the \(\mathsf {Z}\)-test run and the \(\mathsf {X}\)-test run. Thus, whenever a Hadamard is applied to a qubit, during a \(\mathsf {Z}\)-test run, the verifier switches to an \(\mathsf {X}\)-test run until the next Hadamard operation. In the \(\mathsf {X}\)-test runs, the verifier will use the \(\mathsf {T}\) gate gadget from Fig. 8. These are the only checks that are performed in the \(\mathsf {Z}\)-test run.

Putting everything together, the protocol starts by having the verifier choose an input x and a quantum computation \(\mathcal {C}\) to act on this input (that includes preparing the input from the \(\left \vert {0}\right \rangle ^{\otimes n}\) state). Then, the verifier will randomly choose to perform one of the following:

The asymmetry between the \(\mathsf {X}\)-test run and the \(\mathsf {Z}\)-test run stems from the fact that the output is always measured in the computational basis. This means that an incorrect output is one which has been bit-flipped. In turn, this implies that only \(\mathsf {X}\) and \(\mathsf {Y}\) operations on the output will act as deviations, since \(\mathsf {Z}\) effectively acts as identity on computational basis states. If the circuit \(\mathcal {C}\) does not contain any Hadamard gates and hence, the computation takes place entirely in the computational basis, then the \(\mathsf {X}\)-test is sufficient for detecting such deviations. However, when Hadamard gates are present, this is no longer the case since deviations can occur in the conjugate basis, \(({\left \vert {+}\right \rangle }, {\left \vert {-}\right \rangle })\), as well. This is why the \(\mathsf {Z}\)-test is necessary. Its purpose is to check that the prover’s operations are performed correctly when switching to the conjugate basis. For this reason, a Hadamard gate will switch a \(\mathsf {Z}\)-test run into an \(\mathsf {X}\)-test run which provides verification using the \(\mathsf {T}\) gate gadget.

In terms of the correctness of the protocol, we can see that if the prover behaves honestly then the correct outcome is obtained in the computation run and the verifier will accept the test runs, hence \(\delta = 1\).³⁰ For verifiability, the analysis is similar to the previous protocols. Suppose that \({\left \vert {\psi }\right \rangle }\) is either the \({\left \vert {0}\right \rangle }^{\oplus n}\) or the \({\left \vert {+}\right \rangle }^{\oplus n}\) state representing the input. Additionally, assuming there are t\(\mathsf {T}\) gates in \(\mathcal {C}\) (including the ones used for performing the Hadamards), let \({\left \vert {\phi }\right \rangle }\) be the state of the t qubits that the verifier sends for the \(\mathsf {T}\) gate gadgets. Then, the one-time padded state that the prover receives is: The prover is then instructed to follow the steps of the protocol in order to run the circuit \(\mathcal {C}\). Note that all of the operations that he is instructed to perform are Clifford operations. This is because any non-Clifford operation from \(\mathcal {C}\) is performed with the \(\mathsf {T}\) gate gadgets (which require only Clifford operations) and the states from \({\left \vert {\phi }\right \rangle }\), prepared by the verifier. In following the notation from [28], we denote the honest action of the protocol as C. As in the previous protocols, the prover’s deviation can be commuted to the end of the protocol, so that it acts on top of the correct state. After expressing the deviation map in terms of Pauli operators one gets: Note that we have also commuted C past the one-time pad so that it acts on the state \({\left \vert {\psi }\right \rangle }{\left \vert {\phi }\right \rangle }\), rather than on the one-time padded versions of these states. This is possible precisely because C is a Clifford operation and therefore normalises Pauli operations. One can then assume that the verifier performs the decryption of the padding before the final measurement, yielding: >We now use the Pauli twirl from Lemma 2 to get: which is a convex combination of Pauli attacks acting on the correct output state. If we now denote M to be the set of non-benign Pauli attacks (i.e. attacks which do not act as identity on the output of the computation), then one of the test runs will reject with probability: This is because non-benign Pauli \(\mathsf {X}\) or \(\mathsf {Y}\) operations are detected by the \(\mathsf {X}\)-test run, whereas non-benign Pauli \(\mathsf {Z}\) operations are detected by the \(\mathsf {Z}\)-test run. Since either test occurs with probability \(1/3\), it follows that, the probability of the verifier accepting an incorrect outcome is at most \(2/3\), hence \(\epsilon = 2/3\).

Note that when discussing the correctness and verifiability of the Test-or-Compute protocol, we have slightly abused the terminology, since this protocol does not rigorously match the established definitions for correctness and verifiability that we have used for the previous protocols. The reason for this is the fact that in the Test-or-Compute protocol there is no additional flag or trap subsystem to indicate failure. Rather, the verifier detects malicious behaviour by alternating between different runs. It is therefore more appropriate to view the Test-or-Compute protocol simply as a \(\mathsf {QPIP}\) protocol having a constant gap between completeness and soundness:

In terms of the verifier’s quantum resources, we notice that, as with the VUBQC protocol, the only requirement is the preparation of single qubit states. All of these states are sent in the first round of the protocol, the rest of the interaction being completely classical.

The protocols, while different, have the common feature that they all use blindness or have the potential to be blind protocols. Out of the five presented protocols, only the Poly-QAS VQC and the Test-or-Compute protocols are not explicitly blind since, in both cases, the computation is revealed to the server. However, it is relatively easy to make the protocols blind by encoding the circuit into the input (which is one-time padded). Hence, one can say that all protocols achieve blindness.

This feature is essential in the proof of security for these protocols. Blindness combined with either the Pauli twirl Lemma 2 or the Clifford twirl Lemma 1 have the effect of reducing any deviation of the prover to a convex combination of Pauli attacks. Each protocol then has a specific way of detecting such an attack. In the Clifford-QAS VQC protocol, the convex combination is turned into a uniform combination and the attack is detected by a flag subsystem associated with a quantum authentication scheme. A similar approach is employed in the Poly-QAS VQC protocol, using a quantum authentication scheme based on a special type of quantum error correcting code. The VUBQC protocol utilizes trap qubits and either sequential repetition or encoding in an error correcting code to detect Pauli attacks. Finally, the Test-or-Compute protocol uses a hidden identity computation acting on either the \({\left \vert {0}\right \rangle }^{\otimes n}\) or \({\left \vert {+}\right \rangle }^{\otimes n}\) states, in order to detect the malicious behavior of the prover.

Because of these differences, each protocol will have different “quantum requirements” for the verifier. For instance, in the authentication-based protocols, the verifier is assumed to be a quantum computer operating on a quantum memory of size \(O(log(1/\epsilon ))\), where \(\epsilon \) is the desired verifiability of the protocol. In VUBQC and Test-or-Compute, however, the verifier only requires a device capable of preparing single-qubit states. Additionally, out of all of these protocols, only Clifford-QAS VQC requires 2-way quantum communication, whereas the other three require the verifier to send only one quantum message at the beginning of the protocol, while the rest of the communication is classical. These facts, together with the communication complexities of the protocols are shown in Table 1.

As mentioned, if we want to make the Poly-QAS VQC and Test-or-Compute protocols blind, the verifier will hide her circuit by incorporating it into the input. The input would then consist of an encoding of \(\mathcal {C}\) and an encoding of x. The prover would be asked to perform controlled operations from the part of the input containing the description of \(\mathcal {C}\), to the part containing x, effectively acting with \(\mathcal {C}\) on x. We stress that in this case, the protocols would have a communication complexity of \(O(|\mathcal {C}| \cdot log(1/\epsilon ))\), just like VUBQC and Clifford-QAS VQC.³¹

In this section we discuss the measurement-only protocol from [31], which we shall simply refer to as the measurement-only protocol. This protocol uses MBQC to perform the quantum computation, like the VUBQC protocol from Section 2.2, however the manner in which verification is performed is more akin to Broabdent’s Test-or-Compute protocol, from Section 2.3. This is because, just like in the Test-or-Compute protocol, the measurement-only approach has the verifier alternate between performing the computation or testing the prover’s operations.

The key idea for this protocol, is the fact that graph states can be completely specified by a set of stabilizer operators. This fact is explained in Section A. To reiterate the main points, recall that for a graph G, with associated graph state \(\left \vert {G}\right \rangle \), if we denote as \(V(G)\) the set of vertices in G and as \(N_{G}(v)\) the set of neighbours for a given vertex v, then the generators for the stabilizer group of \(\left \vert {G}\right \rangle \) are: for all \(v \in V(G)\). In other words, the \(K_{v}\) operators generate the entire group of operators, O, such that \(O{\left \vert {G}\right \rangle } = {\left \vert {G}\right \rangle }\).

When viewed as observables, stabilizers allow one to test that an unknown quantum state is in fact a particular graph state \({\left \vert {G}\right \rangle }\), with high probability. This is done by measuring random stabilizers of \(\left \vert {G}\right \rangle \) on multiple copies of the unknown quantum state. If all measurements return the \(+ 1\) outcome, then, the unknown state is close in trace distance to \(\left \vert {G}\right \rangle \). This is related to a concept known as self-testing, which is the idea of determining whether an unknown quantum state and an unknown set of observables are close to a target state and observables, based on observed statistics. We postpone a further discussion of this topic to the next section, since self-testing is ubiquitous in entanglement-based protocols.

As mentioned, the measurement-only protocol involves a testing phase and a computation phase. The prover will be instructed to prepare multiple copies of a 2D cluster state, \(\left \vert {G}\right \rangle \), and send them, qubit by qubit, to the verifier. The verifier will then randomly use one of these copies to perform the MBQC computation, whereas the other copies are used for testing that the correct cluster state was prepared.³² This testing phase will involve checking all possible stabilizers of \({\left \vert {G}\right \rangle }\). In particular, the verifier will divide the copies to be tested into two groups, which we shall refer to as the \(\mathsf {X}\textsf {Z}\) group and the \(\mathsf {Z}\textsf {X}\) group. In the \(\mathsf {X}\textsf {Z}\) group of states, the verifier will measure the qubits according to the 2D cluster structure, starting with an \(\mathsf {X}\) operator in the upper left corner of the lattice and then alternating between \(\mathsf {X}\) and \(\mathsf {Z}\). In the \(\mathsf {Z}\textsf {X}\) group, she will measure the dual operators by swapping \(\mathsf {X}\) with \(\mathsf {Z}\). The two cases are illustrated in Fig. 10.

Together, the measurement outcomes of the two groups can be used to infer outcomes of all stabilizer measurements defined by the \(K_{v}\) operators. For instance, given that the measurement outcomes for the qubits take values \(\pm 1\), to compute the outcome of a \(K_{v}\) measurement, for some node v that is measured with \(\mathsf {X}\), the verifier simply takes product of the measurement outcomes for all nodes in \(\{v\} \cup N_{v}\). These tests allow the verifier to certify that the prover is indeed preparing copies of the state \({\left \vert {G}\right \rangle }\). She can then use one of these copies to run the computation. Since the prover does not know which state the verifier will use for the computation, any deviation he implements has a high chance of being detected by one of the verifier’s tests. Hence, the protocol works as follows:

As with all protocols, completeness follows immediately, since if the prover behaves honestly, the verifier will accept the outcome of the computation. In the case of soundness, Hayashi and Morimae treat the problem as a hypothesis test. In other words, in the testing phase of the protocol the verifier is checking the hypothesis that the prover prepared \(2k + 1\) copies of the state \({\left \vert {G}\right \rangle }\). Hayashi and Morimae then prove the following theorem:

This theorem is essentially showing that as the number of copies of \({\left \vert {G}\right \rangle }\), requested by the verifier, increases, and the verifier accepts in the testing phase, one gets that the state \(\rho \), used by the verifier for the computation, is close in trace distance to the ideal state, \({\left \vert {G}\right \rangle }\). The confidence level, \(\alpha \), represents the maximum acceptance probability for the verifier, such that the computation state, \(\rho \), does not satisfy (60). Essentially this represents the probability for the verifier to accept a computation state that is far from ideal. Hayashi and Morimae argue that the lower bound, \(\alpha \geq 1/(2k + 1)\), is tight, because if the prover corrupts one of the \(2k + 1\) states sent to the verifier, there is a \(1/(2k + 1)\) chance that that state will not be tested and the verifier accepts.

If one now denotes with C the POVM that the verifier applies on the computation state in order to perform the computation of \(\mathcal {C}\), then it is the case that: What this means is that the distribution of measurement outcomes for the state \(\rho \), sent by the prover in the computation run, is almost indistinguishable from the distribution of measurement outcomes for the ideal state \({\left \vert {G}\right \rangle }\). The soundness of the protocol is therefore upper bounded by \(\frac {1}{\sqrt {\alpha (2k + 1)}}\). This implies that to achieve soundness below \(\epsilon \), for some \(\epsilon > 0\), the number of copies that the prover would have to prepare scales as \(O \left (\frac {1}{\alpha } \cdot \frac {1}{\epsilon ^{2}} \right )\).

In terms of the quantum capabilities of the verifier, she only requires a single qubit measurement device capable of measuring the observables: \(\mathsf {X}, \textsf {Y}, \textsf {Z}, (\textsf {X} + \textsf {Y})/\sqrt {2}, (\textsf {X} - \textsf {Y})/\sqrt {2}\). Recently, however, Morimae, Takeuchi and Hayashi have proposed a similar protocol which uses hypergraph states [32]. These states have the property that one can perform universal quantum computations by measuring only the Pauli observables (X, \(\mathsf {Y}\) and \(\mathsf {Z}\). Hypergraph states are generalizations of graph states in which the vertices of the graph are linked by hyperedges, which can connect more than two vertices. Hence, the entangling of qubits is done with a generalized \(\mathsf {CZ}\) operation involving multiple qubits. The protocol itself is similar to the one from [31], as the prover is required to prepare many copies of a hypergraph state and send them to the verifier. The verifier will then test all but one of these states using stabilizer measurements and use the remaining one to perform the MBQC computation. For a computation, \(\mathcal {C}\), the protocol has completeness lower bounded by \(1 - |\mathcal {C}| e^{-|\mathcal {C}|}\) and soundness upper bounded by\(1/\sqrt {|\mathcal {C}|}\). The communication complexity is higher than the previous measurement-only protocol, as the prover needs to send \(O(|\mathcal {C}|^{21})\) copies of the \(O(|\mathcal {C}|)\)-qubit graph state, leading to a total communication cost of \(O(|\mathcal {C}|^{22})\). We end with the following result:

The protocols we have reviewed so far have all been based on cryptographic primitives. There were reasons to believe, in fact, that any quantum verification protocol would have to use some form of encryption or hiding. This is due to the parallels between verification and authentication, which were outlined in Section 2. However, it was shown that this is not the case when Morimae and Fitzsimons, and independently Hangleiter et al, proposed a protocol for post hoc quantum verification [29, 30]. The name “post hoc” refers to the fact that the protocol is not interactive, requiring a single round of back and forth communication between the prover and the verifier. Moreover, verification is performed after the computation has been carried out. It should be mentioned that the first post hoc protocol was proposed in [22], by Fitzsimons and Hajdušek, however, that protocol utilizes multiple quantum provers, and we review it in Section 4.3.

In this section, we will present the post hoc verification approach, refered to as 1S-Post-hoc, from the perspective of the Morimae and Fitzsimons paper [29]. The reason for choosing their approach, over the Hangleiter et al one, is that the entanglement-based post hoc protocols, from Section 4.3, are also described using similar terminology to the Morimae and Fitzsimons paper. The protocol of Hangleiter et al is essentially identical to the Morimae and Fitzsimons one, except it is presented from the perspective of certifying the ground state of a gapped, local Hamiltonian. Their certification procedure is then used to devise a verification protocol for a class of quantum simulation experiments, with the purpose of demonstrating a quantum computational advantage [30].

The starting point is the complexity class \(\mathsf {QMA}\), for which we have stated the definition in Section A. Recall, that one can think of \(\mathsf {QMA}\) as the class of problems for which the solution can be checked by a \(\mathsf {BQP}\) verifier receiving a quantum state \({\left \vert {\psi }\right \rangle }\), known as a witness, from a prover. We also stated the definition of the k-local Hamiltonian problem, a complete problem for the class \(\mathsf {QMA}\), in Definition 9. We mentioned that for \(k = 2\) the problem is \(\mathsf {QMA}\)-complete [64]. For the post hoc protocol, Morimae and Fitzsimons consider a particular type of 2-local Hamiltonian known as an \(\mathsf {X}\textsf {Z}\)-Hamiltonian.

To define an \(\mathsf {X}\textsf {Z}\)-Hamiltonian we introduce some helpful notation. Consider an n-qubit operator S, which we shall refer to as \(\mathsf {X}\textsf {Z}\)-term, such that \(S = \bigotimes _{j = 1}^{n} P_{j}\), with \(P_{j} \in \{I, \textsf {X}, \textsf {Z}\}\). Denote \(w_{X}(S)\) as the \(\mathsf {X}\)-weight of S, representing the total number of j’s for which \(P_{j} = \textsf {X}\). Similarly denote \(w_{Z}(S)\) as the \(\mathsf {Z}\)-weight for S. An \(\mathsf {X}\textsf {Z}\)-Hamiltonian is then a 2-local Hamiltonian of the form \(H = {\sum }_{i} a_{i} S_{i}\), where the \(a_{i}\)’s are real numbers and the \(S_{i}\)’s are \(\mathsf {X}\textsf {Z}\)-terms having \(w_{X}(S_{i}) + w_{Z}(S_{i}) \leq 2\).

The 1S-Post-hoc protocol starts with the observation that \(\mathsf {BQP} \subseteq \mathsf {QMA}\). This means that any problem in \(\mathsf {BQP}\) can be viewed as an instance of the 2-local Hamiltonian problem. Therefore, for any language \(L \in \mathsf {BQP}\) and input x, there exists an \(\mathsf {X}\textsf {Z}\)-Hamiltonian, H, such that the smallest eigenvalue of H is less than a when \(x \in L\) or larger than b, when \(x \not \in L\), where a and b are a pair of numbers satisfying \(b - a \geq 1/poly(|x|)\). Hence, the lowest energy eigenstate of H (also referred to as ground state), denoted \({\left \vert {\psi }\right \rangle }\), is a quantum witness for \(x \in L\). In a \(\mathsf {QMA}\) protocol, the prover would be instructed to send this state to the verifier. The verifier then performs a measurement on \({\left \vert {\psi }\right \rangle }\) to estimate its energy, accepting if the estimate is below a and rejecting otherwise. However, we are interested in a verification protocol for \(\mathsf {BQP}\) problems where the verifier has minimal quantum capabilities. This means that there will be two requirements: the verifier can only perform single-qubit measurements; the prover is restricted to \(\mathsf {BQP}\) computations. The 1S-Post-hoc protocol satisfies both of these constraints.

The first requirement is satisfied because estimating the energy of a quantum state, \({\left \vert {\psi }\right \rangle }\), with respect to an \(\mathsf {X}\textsf {Z}\)-Hamiltonian H, can be done by measuring one of the observables \(S_{i}\) on the state \({\left \vert {\psi }\right \rangle }\). Specifically, it is shown in [65] that if one chooses the local term \(S_{i}\) according to a probability distribution given by the normalized terms \(|a_{i}|\), and measures \({\left \vert {\psi }\right \rangle }\) with the \(S_{i}\) observables, this provides an estimate for the energy of \({\left \vert {\psi }\right \rangle }\). Since H is an X Z-Hamiltonian, this entails performing at most two measurements, each of which can be either an \(\mathsf {X}\) measurement or a \(\mathsf {Z}\) measurement. This implies that the verifier need only perform single-qubit measurements.

For the second requirement, one needs to show that for any \(\mathsf {BQP}\) computation, there exists an \(\mathsf {X}\textsf {Z}\)-Hamiltonian such that the ground state can be prepared by a polynomial-size quantum circuit. Suppose the computation that the verifier would like to delegate is denoted as \(\mathcal {C}\) and the input for this computation is x. Given what we have mentioned above, regarding the local Hamiltonian problem, it follows that there exists an \(\mathsf {X}\textsf {Z}\)-Hamiltonian H and numbers a and b, with \(b - a \geq 1/poly(|x|)\), such that if \(\mathcal {C}\) accepts x with high probability then the ground state of H has energy below a, otherwise it has energy above b. It was shown in [64, 66, 67], that starting from \(\mathcal {C}\) and x one can construct an \(\mathsf {X}\textsf {Z}\)-Hamiltonian satisfying this property and which also has a ground state that can be prepared by a \(\mathsf {BQP}\) machine. The ground state is known as the Feynman-Kitaev clock state. To describe this state, suppose the circuit \(\mathcal {C}\) has T gates (i.e. \(T=|\mathcal {C}|\)) and that these gates, labelled in the order in which they are applied, are denoted \(\{U_{i}\}_{i = 0}^{T}\). For \(i = 0\) we assume U₀ = I. The Feynman-Kitaev state is the following: This is essentially a superposition over all time steps, t, of the time evolved state in the circuit \(\mathcal {C}\). Hence, the state can be prepared by a \(\mathsf {BQP}\) machine. The X Z-Hamiltonian is then a series of 2-local constraints that are all simultaneously satisfied by this state.

We can now present the steps of the 1S-Post-hoc protocol: Note that the protocol is not blind, since the verifier informs the prover about both the computation \(\mathcal {C}\) and the input x.

As mentioned, the essential properties that any \(\mathsf {QPIP}\) protocol should satisfy are completeness and soundness. For the post hoc protocol, these follow immediately from the local Hamiltonian problem. Specifically, we know that there exist a and b such that \(b - a \geq 1/poly(|x|)\). When \(\mathcal {C}\) accepts x with high probability, the state \(\left \vert {\psi }\right \rangle \) will be an eigenstate of H having eigenvalue smaller than a. Otherwise, any state, when measured under the H observable, will have an energy greater than b. Of course, the verifier is not computing the exact energy \(\left \vert {\psi }\right \rangle \) under H, merely an estimate. This is because she is measuring only one local term from H. However, it is shown in [29] that the precision of her estimate is also inverse polynomial in \(|x|\). Therefore:

The only quantum capability of the verifier is the ability to measure single qubits in the computational and Hadamard bases (i.e. measuring the \(\mathsf {Z}\) and \(\mathsf {X}\) observables). The protocol, as described, suggests that it is sufficient for the verifier to measure only two qubits. However, since the completeness-soundness gap decreases with the size of the input, in practice one would perform a sequential repetition of this protocol in order to boost this gap. It is easy to see that, for a protocol with a completeness-soundness gap of 1/p(|x|), for some polynomial p, in order to achieve a constant gap of at least \(1 - \epsilon \), where \(\epsilon > 0\), the protocol needs to be repeated O(p(|x|) ⋅ log(1/𝜖)) times. It is shown in [30, 68] that \(p(|x|)\) is \(O(|\mathcal {C}|^{2})\), hence the protocol should be repeated \(O(|\mathcal {C}|^{2} \cdot log(1/\epsilon ))\) times and this also gives us the total number of measurements for the verifier.³³ Note, however, that this assumes that each run of the protocol is independent of the previous one (in other words, that the states sent by the prover to the verifier in each run are uncorrelated). Therefore, the \(O(|\mathcal {C}|^{2} \cdot log(1/\epsilon ))\) overhead should be taken as an i.i.d. (independent and identically distributed states) estimate. This is, in fact, mentioned explicitly in the Hangleiter et al result, where they explain that the prover should prepare “a number of independent and identical copies of a quantum state” [30]. Thus, when considering the most general case of a malicious prover that does not obey the i.i.d. constraint, one requires a more thorough analysis involving non-independent runs, as is done in the measurement-only protocol [31] or the steering-based VUBQC protocol [33].

Receive-and-measure protocols are quite varied in the way in which they perform verification. The measurement-only protocols use stabilizers to test that the prover prepared a correct graph state and then has the verifier use this state to perform an MBQC computation. The 1S-Post-hoc protocol relies on the entirely different approach of estimating the ground state energy of a local Hamiltonian. Lastly, the steering-based VUBQC protocol, which we detail in Section 4.1, is different from these other two approaches by having the verifier remotely prepare the VUBQC states on the prover’s side and then doing trap-based verification. Having such varied techniques leads to significant differences in the total number of measurements performed by the verifier, as we illustrate in Table 2.

Of course, the number of measurements is not the only metric we use in comparing the protocols. Another important aspect is how many observables the verifier should be able to measure. The 1S-Post-hoc protocol is optimal in that sense, since the verifier need only measure \(\mathsf {X}\) and \(\mathsf {Z}\) observables. Next is the hypergraph state measurement-only protocol which requires all three Pauli observables. Lastly, the other two protocols require the verifier to be able to measure the \(\mathsf {X}\textsf {Y}\)-plane observables \(\mathsf {X}\), \(\mathsf {Y}\), \((\textsf {X}+\textsf {Y})/\sqrt {2}\) and \((\textsf {X}-\textsf {Y})/\sqrt {2}\) plus the \(\mathsf {Z}\) observable.

Finally, we compare the protocols in terms of blindness, which we have seen plays an important role in prepare-and-send protocols. For receive-and-measure protocols, the 1S-Post-hoc protocol is the only one that is not blind. While this is our first example of a verification protocol that does not hide the computation and input from the prover, it is not the only one. In the next section, we review two other post hoc protocols that are also not blind.

What this means is that, up to a local isometry, the players share a state which is close in trace distance to a tensor product of Bell pairs and their measurements are close to the ideal measurements. This result, known as CHSH game rigidity, is the key idea for performing multi-prover verification using a classical verifier. We will refer to the protocol in this section as the RUV protocol.

Before giving the description of the protocol, let us first look at an example of gate teleportation, which we also mentioned when presenting the Poly-QAS VQC protocol of Section 2.1. Suppose two parties, Alice and Bob, share a Bell state \(\left \vert {{\Phi }_{+}}\right \rangle \). Bob applies a unitary U on his share of the entangled state so that the joint state becomes \((I \otimes U) \left \vert {{\Phi }_{+}}\right \rangle \). Alice now takes an additional qubit, labelled \(\left \vert {\psi }\right \rangle \) and measures this qubit and the one from the \(\left \vert {{\Phi }_{+}}\right \rangle \) state in the Bell basis given by the states: The outcome of this measurement will be two classical bits which we label \(b_{1}\) and \(b_{2}\). After the measurement, the state on Bob’s system will be \(U \textsf {X}^{b_{1}} \textsf {Z}^{b_{2}} \left \vert {\psi }\right \rangle \). Essentially, Bob has a one-time padded version of \(\left \vert {\psi }\right \rangle \) with the U gate applied.

We now describe the RUV protocol. It uses two quantum provers but can be generalized to any number of provers greater than two. Suppose that Alice and Bob are the two provers. They are allowed to share an unbounded amount of quantum entanglement but are not allowed to communicate during the protocol. A verifier will interact classically with both of them in order to delegate and check an arbitrary quantum computation specified by the quantum circuit \(\mathcal {C}\). The protocol consists in alternating randomly between four sub-protocols:

An important aspect, in proving the correctness of the protocol, is the local similarity of pairs of subprotocols. For instance, Alice cannot distinguish between the CHSH subprotocol and the state tomography one, or between the process tomography one and computation. This is because, in those situations, she is asked to perform the same operations on her side, while being unaware of what Bob is doing. Moreover, since the verifier can test all but the computation part, if Alice deviates there will be a high probability of her deviation being detected. The same is true for Bob. In this way, the verifier can, essentially, enforce that the two players behave honestly and thus perform the correct quantum computation. Note, that this is not the same as the blindness property, discussed in relation to the previous protocols. The RUV protocol does, however, posses that property as well. This follows from a more involved argument regarding the way in which the computation by teleportation is performed.

It should be noted that there are only two constraints imposed on the provers: that they cannot communicate once the protocol has commenced and that they produce close to quantum optimal win-rates for the CHSH games. Importantly, there are no constraints on the quantum systems possessed by the provers, which can be arbitrarily large. Similarly, there are no constraints on what measurements they perform or what strategy they use in order to respond to the verifier. In spite of this, the rigidity result shows that for the provers to produce statistics that are accepted by the verifier, they must behave according to the ideal strategy (up to local isometry). Having the ability to fully characterise the prover’s shared state and their strategies in this way is what allows the verifier to check the correctness of the delegated quantum computation. This approach, of giving a full characterisation of the states and observables of the provers, is a powerful technique which is employed by all the other entanglement-based protocols, as we will see.

In terms of practically implementing such a protocol, there are two main considerations: the amount of communication required between the verfier and the provers and the required quantum capabilities of the provers. For the latter, it is easy to see that the RUV protocol requires both provers to be universal quantum computers (i.e. \(\mathsf {BQP}\) machines), having the ability to store multiple quantum states and perform quantum circuits on these states. In terms of the communication complexity, since the verifier is restricted to \(\mathsf {BPP}\), the amount of communication must scale polynomially with the size of the delegated computation. It was computed in [19], that this communication complexity is of the order \(O(|\mathcal {C}|^{c})\), with \(c > 8192\). Without even considering the constant factors involved, this scaling is far too large for any sort of practical implementation in the near future.³⁶

There are essentially two reasons for the large exponent in the scaling of the communication complexity. The first, as mentioned by the authors, is that the bounds derived in the rigidity result are not tight and could possibly be improved. The second and, arguably more important reason, stems from the rigidity result itself. In Theorem 8, notice that \(\epsilon = poly(\delta , 1/n)\) and \(\epsilon \rightarrow 0\) as \(n \rightarrow \infty \). We also know that the provers need to win a fraction \((1-\epsilon )cos^{2}(\pi /8)\) of CHSH games, in order to pass the verifier’s checks. Thus, the completeness-soundness gap of the protocol will be determined by \(\epsilon \). But since, for fixed \(\delta \), \(\epsilon \) is essentially inverse polynomial in n, the completeness-soundness gap will also be inverse polynomial in n. Hence, one requires polynomially many repetition in order to boost the gap to constant.

We conclude with:

Before concluding this section, we describe the steering-based VUBQC protocol that we referenced in Section 3. As mentioned, the GKW protocol can be viewed as a protocol involving a verifier with an untrusted measurement device interacting with a quantum prover. In a subsequent paper, Gheorghiu, Wallden and Kashefi addressed the setting in which the verifier’s device becomes trusted [33]. They showed that one can define a self-testing game for Bell states which involves steering correlations [77] as opposed to non-local correlations. Steering correlations arise in a two-player setting in which one of the players is trusted to measure certain observables. This extra piece of information allows for the characterisation of Bell states with comparatively fewer statistics than in the non-local case. The steering-based VUBQC protocol, therefore, has exactly the same structure as the GKW protocol. First, the verifier uses this steering-based game, between her measurement device and the prover, to certify that the prover prepared a tensor product of Bell pairs. She then measures some of the Bell pairs so as to remotely prepare the resource states of VUBQC on the prover’s side and then performs the trap-based verification. As mentioned in Section 3, the protocol has a communication complexity of \(O(|\mathcal {C}|^{13} log(|\mathcal {C}|))\) which is clearly an improvement over \(O(|\mathcal {C}|^{2048})\). This improvement stems from the trust added to the measurement device. However, the overhead is still too great for any practical implementation.

We saw, in the HPDF protocol, that having multiple non-communicating provers presents a certain advantage in characterising the shared state of these provers, due to the tensor product structure of the provers’ Hilbert spaces. This approach not only leads to simplified proofs, but also to a reduced overhead in characterising this state, when compared to the CHSH rigidity Theorem 8, from [18].

Another approach which takes advantage of this tensor product structure is the one of McKague from [21]. In his protocol, as in HPDF, the verifier will interact with \(O(poly(|\mathcal {C}|))\) provers. Specifically, there are multiple groups of \(O(|\mathcal {C}|)\) provers, each group jointly sharing a graph state \({\left \vert {G}\right \rangle }\). In particular, each prover should hold only one qubit from \({\left \vert {G}\right \rangle }\). The central idea is for the verifier to instruct the provers to measure their qubits to either test that the provers are sharing the correct graph state or to perform an MBQC computation of \(\mathcal {C}\). This approach is similar to the stabilizer measurement-only protocol of Section 3.1 and, just like in that protocol or the Test-or-Compute or RUV protocols, the verifier will randomly alternate between tests and computation.

Before giving more details about this verification procedure, we first describe the type of graph state that is used in the protocol and the properties which allow this state to be useful for verification. McKague considers \(\left \vert {G}\right \rangle \) to be a triangular graph state, which is a type of universal cluster state. What this means is that the graph G on which the state is based on, is a triangular lattice (a planar graph with triangular faces). An example is shown in Fig. 13. For each vertex v in G we have that: Where\(N(v)\) denotes the neighbors of the vertex v. In other words, \(\left \vert {G}\right \rangle \) is stabilized by the operators \(K_{v} = X_{v} Z_{N(v)}\), for all vertices v. This is important for the testing part of the protocol as it means that measuring the observable \(S_{v}\) will always yield the outcome 1. Another important property is: where \(\tau \) is a set of 3 neighboring vertices which comprise a triangle in the graph G (and \(N(\tau )\) are the odd neighbors of those vertices³⁹). This impliesthat measuring \(T_{\tau } = X_{\tau } Z_{N(\tau )}\) produces the outcome − 1. Triangular graph states are universal for quantum computation, as explained in [21, 78], by performing local measurements (with corrections) on the vertex qubits using the observables \(\mathsf {R}(\theta ) = cos(\theta ) \textsf {X} + sin(\theta ) \textsf {Z}\), where \(\theta \in \{0, \pi /4, ..., 7\pi /4 \}\).

We now have the necessary elements to describe McKague’s protocol. The verifier considers a triangular graph state \(\left \vert {G}\right \rangle \) for the computation she wishes to verify. Let \(n = O(|\mathcal {C}|)\) denote the number of vertices in G. In the ideal case, there will be multiple groups of n provers and, in each group, every prover should have one of the qubits of this graph (entangled with its neighbors). Denote T as the number of triangles (consisting of 3 neighboring vertices) in G and \(N_{G} = 3n + T\). The protocol’s setting is shown in Fig. 14.

The verifier will choose one of the n groups of provers at random to perform the computation \(\mathcal {C}\). The computation is performed in an MBQC fashion. In other words, the verifier will pick appropriate measurement angles \(\{\theta _{v}\}_{v \in V(G)}\), for all vertices in G, as well as a partial order for the vertices. To perform the computation \(\mathcal {C}\), the verifier instructs the provers to measure the qubits of \({\left \vert {G}\right \rangle }\) with the observables \(\mathsf {R}(\theta _{v})\), defined above. The partial order establishes the temporal ordering of these measurements. Additionally, the \(\theta _{v}\) angles, for the \(\mathsf {R}(\theta _{v})\) measurements, should be updated so as to account for corrections arising from previous measurement outcomes. In other words, the angles \(\{\theta _{v}\}_{v \in V(G)}\), which we shall refer to as computation angles, are the ideal angles assuming no corrections. See Section A for more details about measurement-based quantum computations.

The remaining groups of provers are used to test that the correct graph state, \({\left \vert {G}\right \rangle }\), was prepared. This testing phase consists in the verifier randomly choosing to run one of the following sub-protocols:

Together, these three tests are effectively performing a self-test of the graph state \({\left \vert {G}\right \rangle }\) and the prover’s observables. Specifically, McKague showed the following:

Note that the verifier will ask the provers to perform the same types of measurements in both the testing phase and the computation phase of the protocol. This means that, at the level of each prover, the testing and computation phases are indistinguishable. Moreover, the triangular state \({\left \vert {G}\right \rangle }\), being a universal cluster state, will be the same for computations of the same size. Therefore, the protocol is blind in the sense that each prover, on its own, is unaware of what computation is being performed. In summary, the protocol consists of the verifier choosing to perform one of the following:

It is therefore the case that:

As with the previous approaches, the reason for the inverse polynomial gap between completeness and soundness is the use of a self-test with robustness \(\epsilon = poly(1/n)\) (and \(\epsilon \rightarrow 0\) as \(n \rightarrow \infty \)). In turn, this leads to a polynomial overhead for the protocol as a whole. Specifically, McKague showed that the total number of required provers and communication complexity, for a quantum computation \(\mathcal {C}\), is of the order \(O(|\mathcal {C}|^{22})\). Note, however, that each of the provers must only perform a single-qubit measurement. Hence, apart from the initial preparation of the graph state \({\left \vert {G}\right \rangle }\), the individual provers are not universal quantum computers, merely single-qubit measurement devices.

In Section 3.2 we reviewed a protocol by Morimae and Fitzsimons for post hoc verification of quantum computation. Of course, that protocol involved a single quantum prover and a verifier with a measurement device. In this section, we review two post hoc protocols for the multi-prover setting having a classical verifier. We start with the first post hoc protocol by Fitzsimons and Hajdušek.

There are two significant differences between this protocol and the previous entanglement-based approaches. The first is that the protocol does not use self-testing to enforce that the provers are performing the correct operations in order to implement the computation \(\mathcal {C}\). Instead, the computation is checked indirectly by using the self-testing result to estimate the ground-state energy of the k-local Hamiltonian. This then provides an answer to the considered \(\mathsf {BQP}\) computation viewed as a decision problem.⁴² The second difference is that the protocol is not blind. In all the previous approaches, the provers had to share an entangled state which was independent of the computation, up to a certain size. However, in the FH protocol, the state that the provers need to share depends on which quantum computation the verifier wishes to perform.

In terms of communication complexity, the protocol, as described, would involve only 2 rounds of interaction between the verifier and the provers. However, since the completeness-soundness gap is inverse polynomial, and therefore decreases with the size of the computation, it becomes necessary to repeat the protocol multiple times to properly differentiate between the accepting and rejecting cases. On the one hand, the local Hamiltonian itself has an inverse polynomial gap between the two cases of acceptance and rejection. As shown in [30, 68], for the Hamiltonian resulting from a quantum circuit, \(\mathcal {C}\), that gap is \(1/|\mathcal {C}|^{2}\). To boost this gap to constant, the provers must share \(O(|\mathcal {C}|^{2})\) copies of the Feynman-Kitaev state.

On the other hand, the self-testing result has an inverse polynomial robustness. This means that estimating the energy of the ground state is done with a precision which scales inverse polynomially in the number of qubits of the state. More precisely, according to Ji’s result, the scaling should be \(1/O(N^{16})\), where N is the number of qubits on which the Hamiltonian acts [81]. This means that the protocol should be repeated on the order of \(O(N^{16})\) times, in order to boost the completeness-soundness gap to constant.

This theorem is essentially a self-testing result for a tensor product of Bell states, and Pauli \(\mathsf {X}\) and \(\mathsf {Z}\) observables, achieving a constant robustness. The Pauli braiding test is used in the NV protocol in a similar fashion to Ji’s result, from the previous subsection, in order to certify that a set of provers are sharing a state that is encoded in a quantum error correcting code. Again, this relies on a bi-partition of the provers into two sets, such that, an encoded state shared across the bi-partition is equivalent to a Bell pair.

Let us first explain the general idea of the Pauli braiding test for self-testing n Bell pairs and n-qubit observables. We have a referee that is interacting with two players, labelled Alice and Bob. The test consists of three subtests which are chosen at random by the referee. The subtests are: Having observables that satisfy the linearity conditions of the test as well as the anticommutation condition implies that they are isometric to the actual \(\mathsf {X}\) and \(\mathsf {Z}\) observables acting on a maximally entangled state. This is what the Pauli braiding test checks and what is proven by the self-testing result of Natarajan and Vidick.

We can now describe the NV protocol. Similar to the FH protocol, for a quantum circuit, \(\mathcal {C}\), and an input, x, one considers the associated Feynman-Kitaev state, denoted\({\left \vert {\psi }\right \rangle }\). This is then used to construct a 2-local \(\mathsf {X}\textsf {Z}\)-Hamiltonian such that the ground state of this Hamiltonian is \({\left \vert {\psi }\right \rangle }\). As before, for some a and b, with\(b-a > 1/poly(|\mathcal {C}|)\), when \(\mathcal {C}\) accepts x we have that \({\left \langle {\psi }\right \vert } H {\left \vert {\psi }\right \rangle } < a\), otherwise \({\left \langle {\psi }\right \vert } H {\left \vert {\psi }\right \rangle } > b\). The verifier will instruct 7 provers to share a copy of \({\left \vert {\psi }\right \rangle }\) state, encoded in a 7-qubit quantum error correcting code known as Steane’s code. The provers are then asked to perform measurements so as to self-test an encoded state or perform an energy measurement on this state. The code space, for Steane’s code, is the 7-qubit subspace stabilized by all operators generated by \(\{g_{i}\}_{i = 1}^{6}\), where the generators are listed in Table 5.

The reason Natarajan and Vidick use this specific error correcting code is because it has two properties that are necessary for the application of their self-testing result. The first property is that each stabilizer generator is a tensor product of only the I, \(\mathsf {X}\) and \(\mathsf {Z}\) operators. This, of course, is true for the 5-qubit code as well. The second property is a symmetry condition: for each index \(i \in \{1, ..., 6\}\), there exists a pair of stabilizer generators, \(S_{\mathsf {X}}\) and \(S_{\mathsf {Z}}\), such that \(S_{\mathsf {X}}\) consists exclusively of I and \(\mathsf {X}\) operators and has an \(\mathsf {X}\) on position i, whereas \(S_{\mathsf {Z}}\) is identical to \(S_{\mathsf {X}}\) but with all \(\mathsf {X}\) operators replaced with \(\mathsf {Z}\). This property is not satisfied by the 5-qubit code and will allow the verifier to delegate to the provers measurements of the form \(\mathsf {X}(\mathbf {x})\) and \(\mathsf {Z}(\mathbf {z})\), where \(\mathbf {x}\) and \(\mathbf {z}\) are binary strings, as in the Pauli braiding test.

Putting everything together, the protocol works as follows. The verifier instructs the 7 provers to share an encoded instance of the Feynman-Kitaev state, \({\left \vert {\psi }\right \rangle }_{L}\), such that, for each logical qubit in \(\left \vert {\psi }_{L}\right \rangle \), each prover will hold one of 7 the constituent physical qubits. She then chooses at random to perform one of the following:

The self-testing result guarantees that if these tests succeed, the verifier obtains an estimate for the energy of the ground state. Importantly, unlike the FH protocol, her estimate has constant precision. However, the protocol, as described up to this point, will still have an inverse polynomial completeness-soundness gap given by the local Hamiltonian. Recall that this is because the Feynman-Kitaev state will have energy below a when \(\mathcal {C}\) accepts x with high probability, and energy above b otherwise, where \(b - a > 1/|\mathcal {C}|^{2}\). But one can easily boost the protocol to a constant gap between completeness and soundness by simply requiring the provers to share \(M = O(|\mathcal {C}|^{2})\) copies of the ground state. This new state, \({\left \vert {\psi }\right \rangle }^{\otimes M}\), would then be the ground state of a new Hamiltonian \(H^{\prime }\).⁴⁴ One then runs the NV protocol for this Hamiltonian. It should be mentioned that this Hamiltonian is no longer 2-local, however, all of the tests in the NV protocol apply for these general Hamiltonians as well (as long as each term is comprised of I, \(\mathsf {X}\) and \(\mathsf {Z}\) operators, which is the case for \(H^{\prime }\)). Additionally, the new Hamiltonian has a constant gap. The protocol therefore achieves a constant number of rounds of interaction with the provers (2 rounds) and we have that:

To then boost the completeness-soundness gap to \(1-\epsilon \), for some \(\epsilon > 0\), one can perform a parallel repetition of the protocol \(O(log(1/\epsilon ))\) times.

We have seen that having non-communicating provers sharing entangled states allows for verification protocols with a classical client. What all of these protocols have in common is that they all make use of self-testing results. These essentially state that if a number of non-communicating players achieve a near optimal win rate in a non-local game, the strategy they employ in the game is essentially fixed, up to a local isometry. The strategy of the players consists of their shared quantum state as well as their local observables. Hence, self-testing results provide a precise characterisation for both.

This fact is exploited by the surveyed protocols in order to achieve verifiability. Specifically, we have seen that one approach is to define a number of non-local games so that by combining the optimal strategies of these games, the provers effectively perform a universal quantum computation. This is the approach employed by the RUV protocol [18]. Alternatively, the self-testing result can be used to check only for the correct preparation of a specific resource state. This resource state is then used by the provers to perform a quantum computation. How this is done depends on the type of resource state and on how the computation is delegated to the provers. For instance, one possibility is to remotely prepare the resource state used in the VUBQC protocol and then run the verification procedure of that protocol. This is the approach used by the GKW and HPDF protocols [19, 20]. Another possibility is to prepare a cluster state shared among many provers and then have each of those provers measure their states so as to perform an MBQC computation. This approach was used by McKague in his protocol [21]. Lastly, the self-tested resource state can be the ground state of a local Hamiltonian leading to the post hoc approaches employed by the FH and NV protocols.

We noticed that, depending on the approach that is used, there will be different requirements for the quantum operations of the provers. Of course, all protocols require that collectively the provers can perform \(\mathsf {BQP}\) computations, however, individually some provers need not be universal quantum computers. Related to this is the issue of blindness. Again, based on what approach is used some protocols utilize blindness and some do not. In particular, the post hoc protocols are not blind since the computation and the input are revealed to the provers so that they can prepare the Feynman-Kitaev state.

We have also seen that the robustness of the self-testing game impacts the communication complexity of the protocol. Specifically, having robustness which is inverse polynomial in the number of qubits of the self-tested state, leads to an inverse polynomial gap between completeness and soundness. In order to make this gap constant, the communication complexity of the protocol has to be made polynomial. This means that most protocols will have a relatively large overhead, when compared to prepare-and-send or receive-and-measure protocols. Out of the surveyed protocols, the NV protocol is the only one which utilizes a self-testing result with constant robustness and therefore has a constant completeness-soundness gap. We summarize all of these facts in Table 6.⁴⁵

So far we have presented protocols for the verification of universal quantum computations, i.e. protocols in which the provers are assumed to be \(\mathsf {BQP}\) machines. In the near future, however, quantum computers might be more limited in terms of the type of computations that they can perform. Examples of this include the class of so-called instantaneous quantum computations, denoted \(\mathsf {IQP}\), boson sampling or the one-pure qubit model of quantum computation [1, 2, 84]. While not universal, these examples are still highly relevant since, assuming some plausible complexity theoretic conjectures hold, they could solve certain problems or sample from certain distributions that are intractable for classical computers. One is therefore faced with the question of how to verify the correctness of outcomes resulting from these models. In particular, when considering an interactive protocol, the prover should be restricted to the corresponding sub-universal class of problems and yet still be able to prove statements to a computationally limited verifier. We will see that many of the considered approaches are adapted versions of the VUBQC protocol from Section 2.2. It should be noted, however, that the protocols themselves are not direct applications of VUBQC. In each instance, the protocol was constructed so as to adhere to the constraints of the model.

The first sub-universal verification protocol is for the one-pure (or one-clean) qubit model. A machine of this type takes as input a state of limited purity (for instance, a system comprising of the totally mixed state and a small number of single qubit pure states), and is able to coherently apply quantum gates. The model was considered in order to reflect the state of a quantum computer with noisy storage. In [85], Kapourniotis, Kashefi and Datta introduced a verification protocol for this model by adapting VUBQC to the one-pure qubit setting. The verifier still prepares individual pure qubits, as in the original VUBQC protocol, however the prover holds a mixed state of limited purity at all times.⁴⁶ Additionally, the prover can inject or remove pure qubits from his state, during the computation, as long as it does not increase the total purity of the state. The resulting protocol has an inverse polynomial completeness-soundness gap. However, unlike the universal protocols we have reviewed, the constraints on the prover’s state do not allow for the protocol to be repeated. This means that the completeness-soundness gap cannot be boosted through repetition.

Another model, for which verification protocols have been proposed, is that of instantaneous quantum computations, or \(\mathsf {IQP}\) [2, 86]. An \(\mathsf {IQP}\) machine is one which can only perform unitary operations that are diagonal in the \(\mathsf {X}\) basis and therefore commute with each other. The name “instantaneous quantum computation” illustrates that there is no temporal structure to the quantum dynamics [2]. Additionally, the machine is restricted to measurements in the computational basis. It is important to mention that IQP does not represent a decision class, like \(\mathsf {BQP}\), but rather a sampling class. The input to a sampling problem is a specification of a certain probability distribution and the output is a sample from that distribution. The class \(\mathsf {IQP}\), therefore, contains all distributions which can be sampled efficiently (in polynomial time) by a machine operating as described above. Under plausible complexity theoretic assumptions, it was shown that this class is not contained in the set of distributions which can be efficiently sampled by a classical computer [86].

In [2], Shepherd and Bremner proposed a hypothesis test in which a classical verifier is able to check that the prover is sampling from an \(\mathsf {IQP}\) distribution. The verifier cannot, however, check that the prover sampled from the correct distributions. Nevertheless, the protocol serves as a practical tool for demonstrating a quantum computational advantage. The test itself involves an encoding, or obfuscation scheme which relies on a computational assumption (i.e. it assumes that a particular problem is intractable for IQP machines).

Another test of \(\mathsf {IQP}\) problems is provided by the Hangleiter et al approach, from Section 3.2 [30]. Recall that this was essentially the 1S-Post-hoc protocol for certifying the ground state of a local Hamiltonian. Hangleiter et al have the prover prepare multiple copies of a state which is the Feynman-Kitaev state of an \(\mathsf {IQP}\) circuit. They then use the post hoc protocol to certify that the prover prepared the correct state (measuring local terms from the Hamiltonian associated with that state) and then use one copy to sample from the output of the \(\mathsf {IQP}\) circuit. This is akin to the measurement-only approach of Section 3.1. In a subsequent paper, by Bermejo-Vega et al, they consider a subclass of sampling problems that are contained in \(\mathsf {IQP}\) and prove that this class is also hard to classically simulate (subject to standard complexity theory assumptions). The problems can be viewed as preparing a certain entangled state and then measuring all qubits in a fixed basis. The authors provide a way to certify that the state prepared is close to the ideal one, by giving an upper bound on the trace distance. Moreover, the measurements required for this state certification can be made using local stabilizer measurements, for the considered architectures and settings [5].

Recently, another scheme has been proposed, by Mills et al. [87], which again adapts the VUBQC protocol to the \(\mathsf {IQP}\) setting. This eliminates the need for computational assumptions, however it also requires the verifier to have a single qubit preparation device. In contrast to VUBQC, however, the verifier need only prepare eigenstates of the \(\mathsf {Y}\) and \(\mathsf {Z}\) operators.

Yet another scheme derived from VUBQC was introduced in [88] for a model known as the Ising spin sampler. This is based on the Ising model, which describes a lattice of interacting spins in the presence of a magnetic field [89]. The Ising spin sampler is a translation invariant Ising model in which one measures the spins thus obtaining samples from the partition function of the model. Just like with \(\mathsf {IQP}\), it was shown in [90] that, based on complexity theoretic assumptions, sampling from the partition function is intractable for classical computers.

Lastly, Disilvestro and Markham proposed a verification protocol [91] for Spekkens’ toy model [92]. This is a local hidden variable theory which is phenomenologically very similar to quantum mechanics, though it cannot produce non-local correlations. The existence of the protocol, again inspired by VUBQC, suggests that Bell non-locality is not a necessary feature for verification protocols, at least in the setting in which the verifier has a trusted quantum device.

The protocols reviewed in this paper have all been described in an ideal setting in which all quantum devices work perfectly and any deviation from the ideal behaviour is the result of malicious provers. This is not, however, the case in the real world. The primary obstacle, in the development of scalable quantum computers, is noise which affects quantum operations and quantum storage devices. As a solution to this problem, a number of fault tolerant techniques, utilizing quantum error detection and correction, have been proposed. Their purpose is to reduce the likelihood of the quantum computation being corrupted by imperfect gate operations. But while these techniques have proven successful in minimizing errors in quantum computations, it is not trivial to achieve the same effect for verification protocols. To clarify, while we have seen the use of quantum error correcting codes in verification protocols, their purpose was to either boost the completeness-soundness gap (in the case of prepare-and-send protocols), or to ensure an honest behaviour from the provers (in the case of entanglement-based post hoc protocols). The question we ask, therefore, is: how can one design a fault-tolerant verification protocol? Note that this question pertains primarily to protocols in which the verifier is not entirely classical (such as the prepare-and-send or receive-and-measure approaches) or in which one or more provers are assumed to be single-qubit devices (such as the GKW and HPDF protocols). For the remaining entanglement-based protocols, one can simply assume that the provers are performing all of their operations on top of a quantum error correcting code.

Let us consider what happens if, in the prepare-and-send and receive-and-measure protocols, the devices of the verifier and the prover are subject to noise.⁴⁷ If, for simplicity, we assume that the errors on these devices imply that each qubit will have a probability, p, of producing the same outcome as in the ideal setting, when measured, we immediately notice that the probability of n qubits producing the same outcomes scales as \(O(p^{n})\). This means that, even if the prover behaves honestly, the computation is very unlikely to result in the correct outcome [19].

Ideally, one would like the prover to perform his operations in a fault tolerant manner. In other words, the prover’s state should be encoded in a quantum error correcting code, the gates he performs should result in logical operations being applied on his state and he should, additionally, perform error-detection (syndrome) measurements and corrections. But we can see that this is problematic to achieve. Firstly, in prepare-and-send protocols, the computation state of the prover is provided by the verifier. Who should then encode this state in the error-correcting code, the verifier or the prover? It is known that in order to suppress errors in a quantum circuit, \(\mathcal {C}\), each qubit should be encoded in a logical state having \(O(polylog(|\mathcal {C}|))\)-many qubits [93]. This means that if the encoding is performed by the verifier, she must have a quantum computer whose size scales poly-logarithmically with the size of the circuit that she would like to delegate. It is preferable, however, that the verifier has a constant-size quantum computer. Conversely, even if the prover performs the encoding, there is another complication. Since the verifier needs to encrypt the states she sends to the prover, and since her operations are susceptible to noise, the errors acting on these states will have a dependency on her secret parameters. This means that when the prover performs error-detection procedures he could learn information about these secret parameters and compromise the protocol.

For receive-and-measure protocols, one encounters a different obstacle. While the verifier’s measurement device is not actively malicious, if the errors occurring in this device are correlated with the prover’s operations in preparing the state, this can compromise the correctness of the protocol.

A number of fault tolerant verification protocols have been proposed, however, they all overcome these limitations by making additional assumptions. For instance, one proposal, by Kapourniotis and Datta [88], for making VUBQC fault tolerant, uses a topological error-correcting code described in [58, 59]. The error-correcting code is specifically designed for performing fault tolerant MBQC computations, which is why it is suitable for the VUBQC protocol. In the proposed scheme, the verifier still prepares single qubit states, however there is an implicit assumption that the errors on these states are independent of the verifier’s secret parameters. The prover is then instructed to perform a blind MBQC computation in the topological code. The protocol described in [88] is used for a specific type of MBQC computation designed to demonstrate a quantum computational advantage. However, the authors argue that the techniques are general and could be applied for universal quantum computations.

A fault-tolerant version of the measurement-only protocol from Section 3.1 has also been proposed in [95]. The graph state prepared by the prover is encoded in an error-correcting code, such as the topological lattice used by the previous approaches. As in the ‘non-fault-tolerant’ version of the protocol, the prover is instructed to send many copies of this state which the verifier will test using stabilizer measurements. The verifier also uses one copy in order to perform her computation in an MBQC fashion. The protocol assumes that the errors occurring on the verifier’s measurement device are independent of the errors occurring on the prover’s devices.

More details, regarding the difficulties with achieving fault tolerance in \(\mathsf {QPIP}\) protocols, can be found in [26].

Protocols for verification will clearly be useful for benchmarking experiments implementing quantum computations. Experiments implementing quantum computations on a small number of qubits can be verified with brute force simulation on a classical computer. However, as we have pointed out that this is not scalable, in the long-term it is worthwhile to try and implement verification protocols on these devices. As a result, there have been proof of concept experiments that demonstrate the components necessary for verifiable quantum computing.

Inspired by the prepare-and-send VUBQC protocol, Barz et al implemented a four-photon linear optical experiment, where the four-qubit linear cluster state was constructed from entangled pairs of photons produced through parametric down-conversion [96]. Within this cluster state, in runs of the experiment, a trap qubit was placed in one of two possible locations, thus demonstrating some of the elements of the VUBQC protocol. However, it should be noted that the trap qubits are placed in the system through measurements on non-trap qubits within the cluster state, i.e. through measurements made on the the other three qubits. Because of this, the analysis of the VUBQC protocol cannot be directly translated over to this setting, and bespoke analysis of possible deviations is required. In addition, the presence of entanglement between the photons was demonstrated through Bell tests that are performed blindly. This work also builds on a previous experimental implementation of blind quantum computation by Barz et al. [97].

With regards to receive-and-measure protocols, and in particular the measurement-only protocol of Section 3.1, Greganti et al. implemented [98] some of the elements of these protocols with a four-photon experiment, similar to the experiment of Barz et al mentioned above [96]. This demonstration builds on previous work in the experimental characterisation of stabiliser states [99]. In this case, two four-qubit cluster states were generated: the linear cluster state and the star graph state, where in the latter case the only entanglement is between one central qubit and pairwise with every other qubit. In order to demonstrate the elements for measurement-only verification, by suitable measurements made by the client, traps can be placed in the state. Furthermore, the linear cluster state and star graph state can be used as computational resources for implementing single qubit unitaries and an entangling gate respectively.

Finally, preliminary steps have been taken towards an experimental implementation of the RUV protocol, from Section 4.1. Huang et al implemented a simplified version of this protocol using sources of pairs of entangled photons [74]. Repeated CHSH tests were performed on thousands of pairs of photons demonstrating a large violation of the CHSH inequality; a vital ingredient in the protocol of RUV. In between the many rounds of CHSH tests, state tomography, process tomography, and a computation were performed, with the latter being the factorisation of the number 15. Again, all of these elements are ingredients in the protocol, however, the entangled photons are created ’on-the-fly’. In other words, in RUV, two non-communicating provers share a large number of maximally entangled states prior to the full protocol, but in this experiment these states are generated throughout.