Clifford Code for Quantum Authentication

The Clifford Authentication Scheme was introduced in the paper Interactive Proofs For Quantum Computations by Aharanov et al..

Outline

The Clifford code encodes a $m$-qubit message by appending an auxiliary register with $d$ qubits in $|0\rangle$. It then applies a random Clifford operator on all Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle m+d} qubits. By measuring only the auxiliary register, the authenticator decides, whether to accept the received state or whether to abort.

Notations

• ${\mathcal {S}}$: suppliant (sender)
• ${\mathcal {A}}$: authenticator (prover)
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho} : $m$-qubit state to be transmitted
• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d\in \mathbb {N} } : security parameter defining the number of qubits in the auxiliary register
• Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n=m+d} : total number of qubits used
• $\{C_{k}\}$: set of Clifford operations on $n$ qubits labelled by key Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle k\in {\mathcal {K}}}

Properties

• The Clifford code is quantum authentication scheme with security Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 2^{-d}}

Protocol Description

• Encoding: ${\mathcal {E}}_{k}:\rho \mapsto C_{k}\left(\rho \otimes |0\rangle \langle 0|^{\otimes d}\right)C_{k}^{\dagger }$

1. ${\mathcal {S}}$ appends an auxiliary register of $d$ qubits in state $|0\rangle \langle 0|$ to the quantum message $\rho$, which results in $\rho \otimes |0\rangle \langle 0|^{\otimes d}$.
2. ${\mathcal {S}}$ then applies $C_{k}$ for a uniformly random $k\in {\mathcal {K}}$ on the total state.
3. ${\mathcal {S}}$ sends the result to ${\mathcal {A}}$.

• Decoding: Mathematically, the decoding process is described by
  $${\mathcal {D}}_{k}:\rho ^{\prime }\mapsto \mathrm {tr} _{0}\left({\mathcal {P}}_{\mathrm {acc} }C_{k}^{\dagger }(\rho ^{\prime })C_{k}{\mathcal {P}}_{\mathrm {acc} }^{\dagger }\right)\otimes |\mathrm {ACC} \rangle \langle \mathrm {ACC} |+\mathrm {tr} \left({\mathcal {P}}_{\mathrm {rej} }C_{k}^{\dagger }(\rho ^{\prime })C_{k}{\mathcal {P}}_{\mathrm {rej} }^{\dagger }\right)\Omega \otimes |\mathrm {REJ} \rangle \langle \mathrm {REJ} |$$
  In the above, $\mathrm {tr} _{0}$ is the trace over the auxiliary register only, and $\mathrm {tr}$ is the trace over the quantum message system and the auxiliary system. Furthermore, ${\mathcal {P}}_{\mathrm {acc} }=\mathbb {1} ^{\otimes n}\otimes |0\rangle \langle 0|^{\otimes d}$ and ${\mathcal {P}}_{\mathrm {rej} }=\mathbb {1} ^{\otimes (n+d)}-{\mathcal {P}}_{\mathrm {acc} }$ are projective measurement operators.

1. ${\mathcal {A}}$ applies the inverse Clifford $C_{k}^{\dagger }$ to the received state, which is denoted by $\rho ^{\prime }$.
2. ${\mathcal {A}}$ measures the auxiliary register in the computational basis.
   a. If all $d$ auxiliary qubits are 0, the state is accepted and an additional flag qubit in state $|\mathrm {ACC} \rangle \langle \mathrm {ACC} |$ is appended.
   b. Otherwise, the remaining system is traced out and replaced with a fixed $m$-qubit state Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle \Omega } and an additional flag qubit in state Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |\mathrm {REJ} \rangle \langle \mathrm {REJ} |} is appended.

References

1. Aharanov et al. (2008).
2. Broadbent and Wainewright (2016).

contributed by Shraddha Singh and Isabel Nha Minh Le