The quantum prover interactive proof system (QPIP system) presented in Anne Broadbent (2015) - How to Verify a Quantum Computation is an interactive proof system for BQP (promise) problems, where the (honest) prover is a polynomial-time quantum computer, and the verifier is almost-classical. It is designed for verification of those computations that fall outside of NP and hence cannot efficiently be verified classically.

Key features: verification, almost-classical client, interaction

Presentation at QCrypt 2016:

Definition

There are two parties involved, who can communicate over a quantum channel (and also a classical channel):

The verifier (\(V\)): a probabilistic, polynomial-time computer that is 'almost-classical': it only needs to be able to generate (and immediately send, without storing) single-qubit states in the set

\(\{|0\rangle, |1\rangle, |+\rangle, |-\rangle, P|+\rangle, P|-\rangle, T|+\rangle, T|-\rangle, PT|+\rangle, PT|-\rangle\}\)

The prover (\(P\)): in the honest scenario, the prover only needs to be polynomial-time (quantum). No constraints are put on the malicious prover.

Given a quantum circuit \(C\) (known to both \(P\) and \(V\)), \(P\) needs to convince \(V\) that \(C\) is in the canonical BQP-complete set Q-CIRCUIT [ABE10]: a circuit \(C\) is a yes-instance for Q-CIRCUIT if the zero-amplitude of some designated qubit (usually the last) in \(C|0\rangle^{\otimes n}\) is at least 2/3. It is a no-instance if that amplitude is smaller than 1/3. Other circuits are not considered (Q-CIRCUIT is a promise problem).

The protocol is run by having \(V\) randomly select one of three possible runs: a computation run, an X-test, or a Z-test. In all runs, \(P\) applies the circuit according to the specifications below. In a computation run, \(V\) supplies 'real' gadgets, but in the test runs \(V\) sabotages the procedure so that the prover actually only applies the identity circuit.

Key generation	As in quantum one-time pad.
Input	In computation / X-test: \(V\) encrypts \(\|0\rangle^{\otimes n}\). In Z-test: \(V\) encrypts \(\|+\rangle^{\otimes n}\).
Output	\(P\) measure the designated output qubit, and sends the result to \(V\), which \(V\) decrypts. In the computation run, \(V\) accepts iff the output is 0. In the X-test, \(V\) accepts iff the output is 0 and all checks during the computation passed. In the Z-test, \(V\) disregards the measurement and accepts iff all checks during the computation passed.

'Delegated computation' (with interaction)

Quantum gadgets (and classical communication) are needed for P, T and H gates.

For this task, there are three possible runs which each happen with equal probability. In the computation run, V supplies the 'right' gadgets for the prover to perform the circuit, but in the test runs, V sabotages the procedure so that all gates become identity.

	Computation run	X-test	Z-test
Paulis	V updates classical keys (see Pauli-Clifford commutation rules)	V does nothing	V does nothing
CNOT	P applies CNOT, V updates keys.	P applies CNOT, V updates keys. CNOT does not affect \(\|0\rangle\|0\rangle\)	P applies CNOT, V updates keys. CNOT does not affect \(\|+\rangle\|+\rangle\)
T	\(V\) chooses randomly from \(\{T\|+\rangle, T\|-\rangle, PT\|+\rangle, PT\|-\rangle\}\) and sends this as a gadget to \(P\). \(P\) entangles the gadget with the data, measures, and sends the classical bit back. \(V\) decides whether a P-correction is needed (and instructs \(P\) to do this), and updates the key.	Same, but \(V\) chooses randomly from \(\{\|0\rangle, \|1\rangle\}\). \(V\) also checks that the measurement bit sent by \(P\) is consistent with the key.	Same, but \(V\) chooses randomly from \(\{\|+\rangle, \|-\rangle, P\|+\rangle, P\|-\rangle\}\).
P	Apply protocol for T twice.	Apply protocol for T twice.	Apply protocol for T twice.
H	Apply HPHPHPH (= H), by having \(P\) apply the H gates directly to the data (\(V\) updates the keys).	Apply HHHH (= I), by having \(P\) apply the H gates directly to the data (\(V\) updates the keys). In between there are fake executions for phase gates (as in computation runs). Note that the H gates mess up the data in this test; this is restored by applying an even number of H gates. The first and third P-gate should apply the protocol for the P-gate in the Z-test.	Apply HHHH (= I), by having \(P\) apply the H gates directly to the data (\(V\) updates the keys). In between there are fake executions for phase gates (as in computation runs). The first and third P-gate should apply the protocol for the P-gate in the X-test.

If \(P\) deviates from this protocol, his attacks are either benign (i.e. do not affect the zero-amplitude in the measured qubits), in which case the computation run will accept with probability at most that of the computation run (1/3 if it is a no-instance), or they are non-benign, in which case a test run will reject with high probability.

Soundness and completeness

Security does not apply in this case, as there is no secret input from the client (the input to the circuit is the all-zero state). Otherwise, properties from the quantum one-time pad are inherited. The properties that need to be proven for this protocol are soundness and completeness:

Soundness: if the given circuit \(C\) is not in Q-CIRCUIT, then no prover \(P\) is able to convince the verifier to accept with probability more than 1/3.
Completeness: if the given circuit \(C\) is in Q-CIRCUIT, then there exists a prover \(P\) that can convinve the verifier to accept with probability at least 2/3.

One could relax the soundness requirement to computational soundness (see open questions below): the prover can also get the verifier to accept by breaking the computational assumption. This would lead to a quantum interactive argument [BCC88].

Completeness Proof

If P acts honestly, the output of the computation run is a measurement of the designated output qubit of C applied to the all-zero state. V accepts with probability 2/3 if and only if the zero-amplitude was at least 2/3. In the test runs, V always accepts an honest P. Thus the total probability of accepting is at least 2/3.

Soundness Proof

The soundness proof consists of several steps:

Section 7.1 - redefine protocol into an entangled form: V does not send gadgets and classical instruction bits, but only halves of EPR pairs and random bits. This way, V can decide which type of run to execute after all of the interaction with P. From P’s point of view, the two are indistinguishable. This does not alter the completeness proof.
Section 7.2 - redefine protocol to delegate measurement to V: In the original protocol, P performs measurements and sends the result back to V. Now, redefine the protocol so that P sends qubits back to V, who measures them instead. This way, the actions of the prover are unitary.
Section 7.2 - simplifying the attack of the prover: With the above adaptations, we can see any attack of the prover as first executing the honest protocol (unitaries), and then performing an arbitrary quantum operation (which possibly starts by inverting part/all of the honest protocol). This general attack is then broken up into its operator-sum representation, and we focus on a single Kraus term of the sum.
Section 7.3 - benign vs non-benign attacks: a Pauli operator on \(m\) qubits is called benign if it does not influence the zero-amplitude in any of the measured qubits (on those qubits, it should only doI or Z). All other Paulis are called non-benign.
Section 7.4 - if the attack is non-benign: test run will reject. View the Kraus term as a sum of Pauli operators. Lemma 2 states: the probability of at least one of the test runs rejecting is directly related to the weight of the non-benign Pauli terms in that sum.
Section 7.5 - if the attack is benign: computation run accepts with probability at most that of the honest case. As a result, a no-instance is accepted with probability at most 1/3 (by the promise). The proof is first given for a circuit with a single input qubit and only one T gate (using Pauli twirls, it is shown that benign attacks do not influence the measurement outcomes). Then, the same proof idea is generalized for multiple qubits and T gates, but this proof is only more complicated in terms of the notation.
Section 7.6 - putting things together: Both benign and non-benign attacks (i.e. trying to convince V to accept a no-instance) have probability of success smaller than the acceptance probability of a yes-instance (the gap is constant, at least 1/9). The result follows by amplification.

Efficiency

This scheme focuses mostly on restricting the required quantum power of the client/verifier, and not on the efficiency in terms of number of (qu)bits or

The key generation is a strictly classical procedure that requires a source of true randomness (to sample \(2n\) classical bits). Encryption requires the generation of \(|0\rangle, |1\rangle, |+\rangle\) and \(|-\rangle\) states. Decryption is again classical. The verifier needs to generate single-qubit states for some gates: 1 for a T-gate, 2 for a P-gate, and 4 for an H-gate. At every gate, the verifier needs to do some classical key-updates (simple arithmetic modulo 2). The prover needs to do a linear amount of work in the size of the circuit.

Communication is needed for T, P and H gates (not for Pauli or CNOT). There is an entanglement-based version of the protocol (for this, the verifier needs more quantum power), which reduces this communication to one round (verifier sends qubits to prover, prover sends output back).

Open questions

Is it possible to verify the computation using a completely classical client and a single polynomial-time prover? (This would not necessarily imply that BQP = NP, since still interaction is allowed.) One possible way to achieve this is to relax the soundness assumption to computational soundness. (If that is allowed, then we could also eliminate the interaction using classical homomorphic encryption.)