Quantum pseudorandom error-correcting code (QPRC) [1]

Description

Keyed code whose encoding is computationally indistinguishable from a channel drawn once from an ideal distribution [1]. The key-averaged recovery under a given noise channel is negligibly close to the identity in diamond distance. QPRCs are quantum analogues of classical pseudorandom error-correcting codes [2], whose codewords are computationally indistinguishable from uniformly random strings.

Public-key QPRCs for the completely depolarizing channel are obtained from a QECC and a classical pseudorandom error-correcting code [1]. A random Pauli one-time pad is applied to the QECC codeword, and the pad bits, encoded in the classical code, are appended.

Pseudorandom isometric codes (PRICs) are secret-key QPRCs whose encoding is computationally indistinguishable from a Haar-random isometry [1]. The PRIC construction of Ref. [1] maps \(|x\rangle\) to \(2^{-\ell/2}\sum_{y\in\{0,1\}^{\ell}}(-1)^{f(x\|y)}|\pi(x\|y\|0^r)\rangle|g(x\|y)\rangle\) for a pseudorandom function \(f\), a pseudorandom permutation \(\pi\), and a pseudorandom functional code \(g\). The latter is a pseudorandom function whose key holder recovers the input after a constant fraction of the output bits are flipped. The encoder then applies the graph-state unitary of a random bipartite graph and a random Pauli. The PRIC codespace thus lies in a keyed CWS code.