Error mitigation for universal gates on encoded qubits
Christophe Piveteau, David Sutter, et al.
QIP 2022
We propose examples of a hybrid quantum-classical simulation where a classical computer assisted by a small quantum processor can efficiently simulate a larger quantum system. First, we consider sparse quantum circuits such that each qubit participates in O(1) two-qubit gates. It is shown that any sparse circuit on n + k qubits can be simulated by sparse circuits on n qubits and a classical processing that takes time 2O(k)poly(n). Second, we study Pauli-based computation (PBC), where allowed operations are nondestructive eigenvalue measurements of n-qubit Pauli operators. The computation begins by initializing each qubit in the so-called magic state. This model is known to be equivalent to the universal quantum computer. We show that any PBC on n + k qubits can be simulated by PBCs on n qubits and a classical processing that takes time 2O(k)poly(n). Finally, we propose a purely classical algorithm that can simulate a PBC on n qubits in a time 2αnpoly(n), where α≈ 0.94. This improves upon the brute-force simulation method, which takes time 2npoly(n). Our algorithm exploits the fact that n-fold tensor products of magic states admit a low-rank decomposition into n-qubit stabilizer states.
Christophe Piveteau, David Sutter, et al.
QIP 2022
Sergey Bravyi, Giuseppe Carleo, et al.
QIP 2023
Sergey Bravyi, David Gosset
Journal of Mathematical Physics
Diego Ristè, Marcus P. Da Silva, et al.
npj Quantum Information