Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2009.08840 · Quantum

Lightweight Detection of a Small Number of Large Errors in a Quantum Circuit

Noah Linden, Ronald de Wolf

Published Apr 20, 2021• 4 citations
arXivHTMLPDF

Abstract

Suppose we want to implement a unitary U , for instance a circuit for some quantum algorithm. Suppose our actual implementation is a unitary U~ , which we can only apply as a black-box. In general it is an exponentially-hard task to decide whether U~ equals the intended U , or is significantly different in a worst-case norm. In this paper we consider two special cases where relatively efficient and lightweight procedures exist for this task.First, we give an efficient procedure under the assumption that U and U~ (both of which we can now apply as a black-box) are either equal, or differ significantly in only one k -qubit gate, where k=O(1) (the k qubits need not be contiguous). Second, we give an even more lightweight procedure under the assumption that U and U~ are Clifford circuits which are either equal, or different in arbitrary ways (the specification of U is now classically given while U~ can still only be applied as a black-box). Both procedures only need to run U~ a constant number of times to detect a constant error in a worst-case norm. We note that the Clifford result also follows from earlier work of Flammia and Liu, and da Silva, Landon-Cardinal, and Poulin.In the Clifford case, our error-detection procedure also allows us efficiently to learn (and hence correct) U~ if we have a small list of possible errors that could have happened to U ; for example if we know that only O(1) of the gates of U~ are wrong, this list will be polynomially small and we can test each possible erroneous version of U for equality with U~ .

DOI
10.22331/q-2021-04-20-436

Related papers

An algorithm for the T-count

David Gosset, Vadym Kliuchnikov, Michele Mosca +1 more

We consider quantum circuits composed of Clifford and T gates. In this context the T gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an n-qubit unitary U we are interested in computing a circuit that implements it using the minimum possible number of T gates (called the T-count of U). A related task is to decide if the T-count of U is less than or equal to m; we consider this problem as a function of N=2^n and m. We provide a classical algorithm which solves it using time and space both upper bounded as O(N^m poly(m,N)). We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 T gates. This implies that the known 7 T gate circuits for these gates are T-optimal. We also provide a simple expression for the T-count of single-qubit unitaries.

arXiv:1308.4134•Aug 19, 2013•32 citations

An algorithm for the T-countAn algorithm for the T-count

David Gosset, Vadym Kliuchnikov, Michele Mosca +1 more

We consider quantum circuits composed of Clifford and $T$ gates. In this context the $T$ gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an $n$-qubit unitary $U$ we are interested in computing a circuit that implements it using the minimum possible number of $T$ gates (called the $T$-count of $U$). A related task is to decide if the $T$-count of $U$ is less than or equal to $m$; we consider this problem as a function of $N=2^n$ and $m$. We provide a classical algorithm which solves it using time and space both upper bounded as $\mathcal{O}(N^m \text{poly}(m,N))$. We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 $T$ gates. This implies that the known 7 $T$ gate circuits for these gates are $T$-optimal. We also provide a simple expression for the $T$-count of single-qubit unitaries.

Quantum Information and Computation•Nov 1, 2014•65 citations

Fast Estimation of Outcome Probabilities for Quantum Circuits

Hakop Pashayan, Oliver Reardon-Smith, Kamil Korzekwa +1 more

We present two classical algorithms for the simulation of universal quantum circuits on n qubits constructed from c instances of Clifford gates and t arbitrary-angle Z-rotation gates such as T gates.Our algorithms complement each other by performing best in different parameter regimes.The ESTIMATE algorithm produces an additive precision estimate of the Born-rule probability of a chosen measurement outcome with the only source of run-time inefficiency being a linear dependence on the stabilizer extent (with scaling approximately equal to 1.17 t for T gates).Our algorithm is state of the art for this task: as an example, in approximately 13 h (on a standard desktop computer), we estimate the Born-rule probability to within an additive error of 0.03, for a 50-qubit, 60 non-Clifford gate quantum circuit with more than 2000 Clifford gates.Our second algorithm, COMPUTE, calculates the probability of a chosen measurement outcome to machine precision with run time O 2 t-r t , where r is an efficiently computable, circuit-specific quantity.With high probability, r is very close to min {t, n -w} for random circuits with many Clifford gates, where w is the number of measured qubits.COMPUTE can be effective in surprisingly challenging parameter regimes, e.g., we can randomly sample Clifford+T circuits with n = 55, w = 5, c = 10 5 , and t = 80 T gates, and then compute the Born-rule probability with a run time consistently less than 10 min using a single core of a standard desktop computer.We provide a C+Python implementation of our algorithms and benchmark them using random circuits, the hidden-shift algorithm, and the quantum approximate optimization algorithm.

arXiv:2101.12223•PRX Quantum•Jun 23, 2022•32 citations

Trapdoored Clifford Operators and Applications

Minki Hhan, Hojune Lee

Random Clifford operators have numerous applications in quantum computing, including randomized benchmarking, classical shadows, and quantum authentication. However, sampling and implementing uniformly random $n$-qubit Clifford incur near-quadratic complexity due to the size of Clifford group. We introduce a cryptographic way to overcome these barriers: trapdoored Clifford operator distributions whose samples are computationally indistinguishable from uniformly random Cliffords, yet implementing them can be much faster given the trapdoor. We construct a distribution of trapdoored Clifford operators whose elements can be sampled and implemented in near-linear time under a variant of the learning parity with noise assumption. Our constructions allow fast tableau action on Pauli labels for classical simulation, and also can be optimized to admit polylogarithmic-depth implementation. Along the way, we construct trapdoored matrices over finite fields that support efficient multiplication by both a matrix and its inverse, resolving an open question left by Vaikuntanathan and Zamir [SODA'26]. We use these constructions to obtain faster protocols based on random Cliffords. We also explore their applications to the worst-case to average-case reductions for matrix and Clifford problems including the iterated matrix multiplication and Clifford circuit synthesis. In particular, we show the hardness of batching Clifford circuits: synthesizing circuits that apply the same Clifford to multiple registers is at least as hard as worst-case matrix multiplication, even when synthesis succeeds on a small constant fraction of random Cliffords. This extends to approximate implementations by general quantum circuits.

quant-pharXiv:2610.01848•Oct 2, 2026•0 citations

Single-shot error mitigation by coherent Pauli checks

E. van den Berg, Sergey B. Bravyi, Jay Gambetta +3 more

Generating samples from the output distribution of a quantum circuit is a ubiquitous task used as a building block of many quantum algorithms. Here we show how to accomplish this task on a noisy quantum processor lacking full-blown error correction for a special class of quantum circuits dominated by Clifford gates. Our approach is based on Coherent Pauli Checks (CPCs) that detect errors in a Clifford circuit by verifying commutation rules between random Pauli-type check operators and the considered circuit. Our main contributions are as follows. First, we derive a simple formula for the probability that a Clifford circuit protected by CPCs contains a logical error. In the limit of a large number of checks, the logical error probability is shown to approach the value ${\approx}7εn/5$, where $n$ is the number of qubits and $ε$ is the depolarizing error rate. Our formula agrees nearly perfectly with the numerical simulation results. Second, we show that CPCs are well-suited for quantum processors with a limited qubit connectivity. For example, the difference between all-to-all and linear qubit connectivity is only a 3X increase in the number of CNOT gates required to implement CPCs. Third, we describe simplified one-sided CPCs which are well-suited for mitigating measurement errors in the single-shot settings. Finally, we report an experimental demonstration of CPCs with up to 10 logical qubits and more than 100 logical CNOT gates. Our experimental results show that CPCs provide a marked improvement in the logical error probability for the considered task of sampling the output distribution of quantum circuits.

arXiv:2212.03937•Dec 7, 2022•2 citations

Quantum Circuit for General Unitary: Improved T-count via Block Flattening and Dilation

Pei Yuan, Shengyu Zhang, Wei Zi

Synthesizing arbitrary $n$-qubit unitaries using as few non-Clifford gates as possible is a central problem in fault-tolerant quantum compilation. We present a Clifford+$T$ quantum circuit construction that approximately implements any classically specified unitary to within error $ε$ and achieves a worst-case $T$-count with leading exponential scaling of $2^{5n/4}$ whenever $\log(1/ε)=\operatorname{poly}(n)$. This improves upon the best previous $2^{4n/3}$ scaling. The key innovation lies in treating the target unitary as a single block-encoded object rather than a long product of simpler operations. A technique of block flattening controls the normalization while preserving an efficient implementation of the block encoding; subsequently, quantum singular value transformation maps its common singular value to one, thereby recovering the target unitary.

quant-pharXiv:2608.17846•Aug 19, 2026•0 citations
Suppose we want to implement a unitary U , for instance a circuit for some quantum algorithm. Suppose our actual implementation is a unitary U~ , which we can only apply as a black-box. In general it is an exponentially-hard task to decide whether U~ equals the intended U , or is significantly different in a worst-case norm. In this paper we consider two special cases where relatively efficient and lightweight procedures exist for this task.First, we give an efficient procedure under the assumption that U and U~ (both of which we can now apply as a black-box) are either equal, or differ significantly in only one k -qubit gate, where k=O(1) (the k qubits need not be contiguous). Second, we give an even more lightweight procedure under the assumption that U and U~ are Clifford circuits which are either equal, or different in arbitrary ways (the specification of U is now classically given while U~ can still only be applied as a black-box). Both procedures only need to run U~ a constant number of times to detect a constant error in a worst-case norm. We note that the Clifford result also follows from earlier work of Flammia and Liu, and da Silva, Landon-Cardinal, and Poulin.In the Clifford case, our error-detection procedure also allows us efficiently to learn (and hence correct) U~ if we have a small list of possible errors that could have happened to U ; for example if we know that only O(1) of the gates of U~ are wrong, this list will be polynomially small and we can test each possible erroneous version of U for equality with U~ .
We consider quantum circuits composed of Clifford and T gates. In this context the T gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an n-qubit unitary U we are interested in computing a circuit that implements it using the minimum possible number of T gates (called the T-count of U). A related task is to decide if the T-count of U is less than or equal to m; we consider this problem as a function of N=2^n and m. We provide a classical algorithm which solves it using time and space both upper bounded as O(N^m poly(m,N)). We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 T gates. This implies that the known 7 T gate circuits for these gates are T-optimal. We also provide a simple expression for the T-count of single-qubit unitaries.
We consider quantum circuits composed of Clifford and TTT gates. In this context the TTT gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an nnn-qubit unitary UUU we are interested in computing a circuit that implements it using the minimum possible number of TTT gates (called the TTT-count of UUU). A related task is to decide if the TTT-count of UUU is less than or equal to mmm; we consider this problem as a function of N=2nN=2^nN=2n and mmm. We provide a classical algorithm which solves it using time and space both upper bounded as O(Nmpoly(m,N))\mathcal{O}(N^m \text{poly}(m,N))O(Nmpoly(m,N)). We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 TTT gates. This implies that the known 7 TTT gate circuits for these gates are TTT-optimal. We also provide a simple expression for the TTT-count of single-qubit unitaries.
We present two classical algorithms for the simulation of universal quantum circuits on n qubits constructed from c instances of Clifford gates and t arbitrary-angle Z-rotation gates such as T gates.Our algorithms complement each other by performing best in different parameter regimes.The ESTIMATE algorithm produces an additive precision estimate of the Born-rule probability of a chosen measurement outcome with the only source of run-time inefficiency being a linear dependence on the stabilizer extent (with scaling approximately equal to 1.17 t for T gates).Our algorithm is state of the art for this task: as an example, in approximately 13 h (on a standard desktop computer), we estimate the Born-rule probability to within an additive error of 0.03, for a 50-qubit, 60 non-Clifford gate quantum circuit with more than 2000 Clifford gates.Our second algorithm, COMPUTE, calculates the probability of a chosen measurement outcome to machine precision with run time O 2 t-r t , where r is an efficiently computable, circuit-specific quantity.With high probability, r is very close to min {t, n -w} for random circuits with many Clifford gates, where w is the number of measured qubits.COMPUTE can be effective in surprisingly challenging parameter regimes, e.g., we can randomly sample Clifford+T circuits with n = 55, w = 5, c = 10 5 , and t = 80 T gates, and then compute the Born-rule probability with a run time consistently less than 10 min using a single core of a standard desktop computer.We provide a C+Python implementation of our algorithms and benchmark them using random circuits, the hidden-shift algorithm, and the quantum approximate optimization algorithm.
Random Clifford operators have numerous applications in quantum computing, including randomized benchmarking, classical shadows, and quantum authentication. However, sampling and implementing uniformly random nnn-qubit Clifford incur near-quadratic complexity due to the size of Clifford group. We introduce a cryptographic way to overcome these barriers: trapdoored Clifford operator distributions whose samples are computationally indistinguishable from uniformly random Cliffords, yet implementing them can be much faster given the trapdoor. We construct a distribution of trapdoored Clifford operators whose elements can be sampled and implemented in near-linear time under a variant of the learning parity with noise assumption. Our constructions allow fast tableau action on Pauli labels for classical simulation, and also can be optimized to admit polylogarithmic-depth implementation. Along the way, we construct trapdoored matrices over finite fields that support efficient multiplication by both a matrix and its inverse, resolving an open question left by Vaikuntanathan and Zamir [SODA'26]. We use these constructions to obtain faster protocols based on random Cliffords. We also explore their applications to the worst-case to average-case reductions for matrix and Clifford problems including the iterated matrix multiplication and Clifford circuit synthesis. In particular, we show the hardness of batching Clifford circuits: synthesizing circuits that apply the same Clifford to multiple registers is at least as hard as worst-case matrix multiplication, even when synthesis succeeds on a small constant fraction of random Cliffords. This extends to approximate implementations by general quantum circuits.
Generating samples from the output distribution of a quantum circuit is a ubiquitous task used as a building block of many quantum algorithms. Here we show how to accomplish this task on a noisy quantum processor lacking full-blown error correction for a special class of quantum circuits dominated by Clifford gates. Our approach is based on Coherent Pauli Checks (CPCs) that detect errors in a Clifford circuit by verifying commutation rules between random Pauli-type check operators and the considered circuit. Our main contributions are as follows. First, we derive a simple formula for the probability that a Clifford circuit protected by CPCs contains a logical error. In the limit of a large number of checks, the logical error probability is shown to approach the value ≈7εn/5{\approx}7εn/5≈7εn/5, where nnn is the number of qubits and εεε is the depolarizing error rate. Our formula agrees nearly perfectly with the numerical simulation results. Second, we show that CPCs are well-suited for quantum processors with a limited qubit connectivity. For example, the difference between all-to-all and linear qubit connectivity is only a 3X increase in the number of CNOT gates required to implement CPCs. Third, we describe simplified one-sided CPCs which are well-suited for mitigating measurement errors in the single-shot settings. Finally, we report an experimental demonstration of CPCs with up to 10 logical qubits and more than 100 logical CNOT gates. Our experimental results show that CPCs provide a marked improvement in the logical error probability for the considered task of sampling the output distribution of quantum circuits.
Synthesizing arbitrary nnn-qubit unitaries using as few non-Clifford gates as possible is a central problem in fault-tolerant quantum compilation. We present a Clifford+TTT quantum circuit construction that approximately implements any classically specified unitary to within error εεε and achieves a worst-case TTT-count with leading exponential scaling of 25n/42^{5n/4}25n/4 whenever log⁡(1/ε)=poly⁡(n)\log(1/ε)=\operatorname{poly}(n)log(1/ε)=poly(n). This improves upon the best previous 24n/32^{4n/3}24n/3 scaling. The key innovation lies in treating the target unitary as a single block-encoded object rather than a long product of simpler operations. A technique of block flattening controls the normalization while preserving an efficient implementation of the block encoding; subsequently, quantum singular value transformation maps its common singular value to one, thereby recovering the target unitary.