| |
Key type |
Most important features / context / techniques |
| Quantum one-time pad (QOTP) [MTdW00] | symmetric |
information-theoretic, simple |
| Secure Assisted Quantum Computation [Chi05] |
symmetric |
information-theoretic, simple, delegated computation |
| Clifford scheme (CL) [BJ15] |
public |
homomorphic for Cliffords, based on QOTP |
| EPR [BJ15] | public |
homomorphic, based on CL |
| AUX [BJ15] | symmetric |
homomorphic, based on CL |
| TP [DSS16] |
public |
homomorphic, based on CL |
| Trap code [BGS12] | symmetric |
authentication, Pauli twirl |
| Clifford code [ABE10] |
symmetric |
authentication |
| (Signed) polynomial code [BOCG+06] | ... |
... |
| Blind Quantum Computation [AS03] |
... |
... |
| Universal Blind Quantum Computation [BFK08] |
symmetric |
measurement-based framework, introduction of brickwork states |
| Unconditionally Verifiable Blind Quantum Computation [FK12] |
... |
... |
| Extending the Delegated Verifiable Blind Quantum Computation Functionality [KW16] |
... |
... |
| Publicly Verifiable Blind Quantum Computation [Hon16] |
... |
... |
| Actively Secure Two-Party Evaluation of any Quantum Operation [DNS12] |
... |
... |
| Blind Multiparty Quantum Computing [KP16] |
... |
... |
| Interactive Proofs for Quantum Computations [ABE10] |
... |
... |
| A Classical Leash for a Quantum System [RUV12] |
... |
QPIP, two non-communicating servers, classical client |
| How to Verify a Quantum Computation [Bro15] | symmetric | QPIP, information-theoretic (perfect) |
| Time (for \(n\) qubits) |
Quantum power |
Key size (for \(n\) qubits, security parameter \(\kappa\)) |
|
| Quantum one-time pad (QOTP) [MTdW00] | sample \(2n\) classical bits |
none |
\(2n\) classical bits |
| Secure Assisted Quantum Computation [Chi05] |
sample \(2n\) classical bits |
none |
\(2n\) classical bits |
| Clifford scheme (CL) [BJ15] | polynomial in \(\kappa\) (classical FHE) |
none |
polynomial in \(\kappa\) (classical FHE key) |
| polynomial in \(\kappa\) (classical FHE) | none |
polynomial in \(\kappa\) (classical FHE key) |
|
| AUX [BJ15] | polynomial in \(\kappa\) (classical FHE), plus ~\(O(n^{2^L})\) time to generate the gadgets (where \(L\) is the number of layers of T gates) |
generate single-qubit states of the form \(Z^bP^a|+\rangle\). |
polynomial in \(\kappa\) (classical FHE key), plus ~\(O(n^{2^L})\) gadgets (where \(L\) is the number of layers of T gates) |
| TP [DSS16] | polynomial in \(\kappa\) and the number of \(T\) gates to be evaluated (classical FHE, and gadget generation) |
If unaided by server: generate random Bell pairs, and SWAP If aided by (untrusted) server: Pauli and SWAP gates. |
polynomial in \(\kappa\) (classical FHE key) and number of \(T\) gates (gadgets, which are themselves polynomial in \(\kappa\) in size) |
| Trap code [BGS12] |
linear in \(nm\) (for [[m,1,d]] QECC) |
none |
\(O(m \log m)\) for the permutation, plus \(6nm\) classical bits |
| Clifford code |
linear in \(n\) and \(m\) (for \(m\) check bits) |
none |
\(n + m\)-qubit Clifford (classical description), where\(d\) is related to security parameter |
| ... |
... |
... |
... |
| Blind Quantum Computation [AS03] | ... |
... |
... |
| Universal Blind Quantum Computation [BFK08] | linear in \(n\) and number of gates to be performed | generate states of the form \(Z^aP^bT^c|+\rangle\) |
linear in \(n\) and number of gates to be performed (size of brickwork state), classical bytes |
| Unconditionally Verifiable Blind Quantum Computation [FK12] | ... |
... |
... |
| How to Verify a Quantum Computation [Bro15] | linear in number of gates to be executed, and sample \(2n\) classical bits |
generation of random single-qubit states of the form \(X^aZ^bP^cT^dH^e|0\rangle\) |
\(2n\) classical bits (as in QOTP) |
| Time (for \(n\) qubits) |
Quantum power |
Size of cyphertext (for \(n\) qubits, security parameter \(\kappa\)) |
|
| Quantum one-time pad (QOTP) [MTdW00] | linear in \(n\) |
Pauli gates |
\(n\) qubits |
| Secure Assisted Quantum Computation [Chi05] |
linear in \(n\) |
Pauli gates |
\(n\) qubits |
| Clifford scheme (CL) [BJ15] | linear in \(n\) |
Pauli gates |
\(n\) qubits + poly\((\kappa) \cdot n\) classical bits |
| linear in \(n\) |
Pauli gates |
\(n\) qubits + poly\((\kappa) \cdot n\) classical bits | |
| AUX [BJ15] | linear in \(n\) |
Pauli gates |
\(n\) qubits (the classical encryptions are part of the evaluation key) |
| TP [DSS16] | linear in \(n\) |
Pauli gates | \(n\) qubits + poly\((\kappa) \cdot n\) classical bits |
| Trap code [BGS12] | polynomial in \(n\) (or linear?) |
Pauli gates, SWAP gates, plus whatever is needed for applying an [[m,1,d]] error-correcting quantum code (Clifford gates?) |
\(3nm\) |
| Clifford code [ABE10] |
polynomial in \(n+m\) (\(m\) is number of check qubits) |
multi-qubit Clifford gates |
\(n+m\) |
| ... |
... |
... |
... |
| Blind Quantum Computation [AS03] | ... |
... |
... |
| Universal Blind Quantum Computation [BFK08] |
polynomial in \(n\) |
classical input: none quantum input: gates of the form \(Z^aP^bT^c\), and Paulis |
\(n\) qubits |
| Unconditionally Verifiable Blind Quantum Computation [FK12] | ... |
... |
... |
| How to Verify a Quantum Computation [Bro15] | linear in \(n\) |
Pauli gates |
\(n\) qubits |
| Types of gates that can be evaluated |
Time (for \(g\) gates, \(t\) T gates) | Quantum power from server |
Quantum power from client |
|
| Quantum one-time pad (QOTP) [MTdW00] |
N/A (technically, Paulis) |
N/A (linear in \(g\)) |
N/A (Pauli gates) |
N/A (none) |
| Secure Assisted Quantum Computation [Chi05] |
all |
linear in \(g\) |
universal |
Paulis (decrypt/encrypt in between), SWAP, generate \(|0\rangle\) state for every T gate |
| Clifford scheme (CL) [BJ15] | Cliffords |
linear in \(g\), polynomial in \(\kappa\) (apply gates directly, and updates keys using classical-FHE evaluation) |
Clifford gates |
none (homomorphic) |
| Cliffords + constant number of T-gates |
linear in \(g\), polynomial in \(\kappa\) (for T gates: apply gate directly, generate an EPR pair and teleport into it) |
universal |
none (homomorphic) |
|
| AUX [BJ15] | Cliffords + constant number of T-gates |
linear in \(g\), exponential in \(L\) (T gate depth) |
universal |
none (homomorphic) |
| TP [DSS16] | Cliffords + poly\((\kappa)\) T-gates |
linear in \(g\), plus \(t \cdot\) poly\((\kappa)\) (for T gates: apply gate directly, measure the gadget) |
universal | none (homomorphic) |
| Trap code [BGS12] | all |
linear in \(g\) |
universal |
Generate encodings of \(P|+\rangle, |+\rangle\) and \((H \otimes I)|\Phi^+\rangle\). This can be done in advance; then only classical power is required. |
| Clifford code [ABE10] | N/A |
N/A | N/A | N/A |
| ... |
... |
... |
... |
... |
| Blind Quantum Computation [AS03] | ... |
... |
... |
... |
| Universal Blind Quantum Computation [BFK08] | all |
linear in \(g\) |
measurements in various angles along the XY plane |
none (only classical) |
| Unconditionally Verifiable Blind Quantum Computation [FK12] | ... |
... |
... |
... |
| How to Verify a Quantum Computation [Bro15] | all |
linear in \(g\) (note: \(P\) is treated as \(T^2\), and \(H\) as \(HPHPHPH\)) |
Clifford gates, computational measurements |
none (unless preparation for gates is performed online) |
| Time (for \(n\) qubits) |
Quantum power |
|
| Quantum one-time pad (QOTP) [MTdW00] | linear in \(n\) |
Pauli gates |
| Secure Assisted Quantum Computation [Chi05] |
linear in \(n\) |
Pauli gates |
| Clifford scheme (CL) [BJ15] | linear in \(n\), polynomial in \(\kappa\) |
Pauli gates |
| linear in \(n\), polynomial in \(\kappa\), quadratic in number of T gates |
Pauli gates, H, HP, computational measurement |
|
| AUX [BJ15] | linear in \(n\), polynomial in \(\kappa\) |
Pauli gates |
| TP [DSS16] | linear in \(n\), polynomial in \(\kappa\) | Pauli gates |
| Trap code [BGS12] | \(n\) times poly\(m\) |
Pauli gates, SWAP, plus decoding the QECC |
| Clifford code [ABE10] | polynomial in \(nm\) |
Clifford gates |
| ... |
... |
... |
| Blind Quantum Computation [AS03] | ... |
... |
| Universal Blind Quantum Computation [BFK08] | linear in \(n\) |
classical output: none quantum output: gates of the form \(Z^aP^bT^c\), and Paulis |
| Unconditionally Verifiable Blind Quantum Computation [FK12] | ... |
... |
| How to Verify a Quantum Computation [Bro15] | constant (only one output bit) |
none (output is classical) |
| Type of security |
Privacy (data) |
Authentication (data) |
Non-malleability (data) |
Blindness (computation) |
Verifiability (computation) |
Circuit privacy (computation) |
|
| Quantum one-time pad (QOTP) [MTdW00] | Information theoretic |
yes (perfect) |
no |
no |
N/A |
N/A |
N/A |
| Secure Assisted Quantum Computation [Chi05] |
Information theoretic |
yes (perfect) |
no |
no |
no |
no |
no |
| Clifford scheme (CL) [BJ15] | Computational, for example LWE (based on classical FHE) | yes |
no |
no |
? (is universal circuit for only Cliffords just for Cliffords?) |
no |
yes (see TP) |
| EPR [BJ15] | Computational (see CL) |
yes |
no |
no |
yes, using universal circuit |
no |
... |
| AUX [BJ15] | Computational (see CL) |
yes |
no |
no |
yes, using universal circuit |
no |
probably in the same way as CL? |
| TP [DSS16] | Computational (see CL) |
yes |
no |
no |
yes, using universal circuit |
no |
yes, if classical FHE scheme has it (with upper bound to number of T gates known) |
| Trap code [BGS12] | Information theoretic |
yes (perfect) |
yes |
? |
no |
yes |
no |
| Clifford code [ABE10] | Information theoretic |
... |
yes (?) |
yes |
N/A |
N/A |
N/A |
| ... |
... |
... |
... |
... |
... |
... |
... |
| Blind Quantum Computation [AS03] | ... |
... |
... |
... |
... |
... |
... |
| Universal Blind Quantum Computation [BFK08] | information theoretic |
yes (perfect) |
yes, at expense of doubling input size. [FK12]: proof does not hold for general adversary |
... |
yes |
no |
no |
| Unconditionally Verifiable Blind Quantum Computation [FK12] | ... |
... |
... |
... |
... |
... |
... |
| How to Verify a Quantum Computation [Bro15] | Information theoretic |
N/A |
N/A |
N/A |
no |
yes |
N/A |
| Interaction before the computation |
Interaction during the computation and/or verification |
Interaction after the computation |
|
| Quantum one-time pad (QOTP) [MTdW00] | N/A |
N/A (technically, could be homomorphic for Paulis) |
N/A |
| Secure Assisted Quantum Computation [Chi05] |
none |
quantum (both directions), after every gate |
none |
| Clifford scheme (CL) [BJ15] | quantum (client to server) |
none (homomorphic) |
quantum (server to client) |
| EPR [BJ15] | quantum (client to server) |
none (homomorphic) |
quantum (server to client) |
| AUX [BJ15] | quantum (client to server) |
none (homomorphic) |
quantum (server to client) |
| TP [DSS16] |
quantum (client to server) if limiting client quantum power: extra round (quantum, server to client) to help build gadgets |
none (homomorphic) |
quantum (server to client) |
| Trap code [BGS12] | quantum (client to server) |
classical for every Pauli, CNOT quantum (client to server) for every P, H, T (can be adapted to only classical communication, and only for T gates) |
quantum (server to client) |
| Clifford code [ABE10] | N/A |
N/A |
N/A |
| ... |
... |
... |
... |
| Blind Quantum Computation [AS03] | ... |
... |
... |
| Universal Blind Quantum Computation [BFK08] | quantum (client sends partial brickwork state to server) |
classical (both directions), after every `layer' of measurements |
quantum (server to client) |
| Unconditionally Verifiable Blind Quantum Computation [FK12] | ... |
... |
... |
| How to Verify a Quantum Computation [Bro15] |
quantum (client to server) |
classical (both directions), after every gate if client is generating gadgets on the fly: also quantum (client to server) |
classical (server to client) |
encoding, detection, correction, which gates are transversal, ...
How does the encoding scale with multiple parties? Can verification stuff still be done?