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:2508.05386

Resource-Efficient Synthesis of Sparse Quantum States

Renaud Vilmart, Sunheang Ty, Chetra Mang

Published Aug 7, 2025• 3 citations
arXivHTMLPDF

Abstract

Preparing a quantum circuit that implements a given sparse state is an important building block that is necessary for many different quantum algorithms. In the context of fault-tolerant quantum computing, the so-called non-Clifford gates are much more expensive to perform than the Clifford ones. We hence provide an algorithm for synthesizing sparse quantum states with a special care for quantum resources. The circuit depth, ancilla count, and crucially non-Clifford count of the circuit produced by the algorithm are all linear in the sparsity when access to arbitrary-angled rotations is given. When compiled down to the standard Clifford+T gate set, several constructions can be given for increasingly better T-count and depth at the expense of a larger number of ancillae. The most optimised construction for T-count reaches $\mathcal O\left(s+\log_2(1/ε)\right)$ T gates for error $ε$. The constructions are broken into two parts, one that synthesises a generalized W-state, well studied in the literature; and the second which is a classical reversible circuit implementing a permutation that maps the basis states of the W-state to those of the target sparse quantum state. We reduce this problem to the diagonalization of a binary matrix, using a specific set of elementary matrix operations corresponding to the classical reversible gates. We then solve this problem using a new version of Gauss-Jordan elimination, that minimizes the circuit complexities including circuit depth using parallel elimination steps. When the circuit is applied in one direction, we notice that all occurrences of (the expensive) Toffoli gates can all be replaced by adaptive Clifford circuits, leading to a better non-Clifford count.

DOI
10.48550/arxiv.2508.05386

Related papers

Clifford-efficient sparse state preparation for molecular wavefunctions

Yingrong Chen, Nathan A. Baker, Rushi Gong +7 more

Sparse quantum state preparation concerns an $n$-qubit target state that is a superposition of only $d \ll 2^n$ computational basis states. Existing approaches exploit this sparsity by compressing these $d$ basis states and their amplitudes onto a smaller set of qubits, called the dense register, before expanding the prepared state to the full register. Rather than relying on the permutation-based compression used in prior work, we exploit affine relationships among the binary configurations over the finite field $\operatorname{GF}(2)$ to reduce both the non-Clifford gate count and the ancillary qubit count. Invertible affine transformations over $\operatorname{GF}(2)$, comprising Gaussian elimination and all-ones-row removal, first reduce the dense register from $n$ to the rank $r$ using only Clifford gates and no ancillary qubits. An optional binary encoding stage then trades additional Toffoli gates and ancillary qubits for further compression to the minimum $\lceil\log_2 d\rceil$ dense qubits needed to represent $d$ distinct configurations. For chemically relevant wavefunctions, such as those obtained from selected configuration interaction calculations, shared electronic excitation patterns produce many of these affine relationships, enabling substantial Clifford-only compression before binary encoding. Across the molecular benchmarks, our method requires the fewest ancillary qubits among the evaluated sparse state preparation methods while maintaining comparable non-Clifford gate counts when using binary encoding.

quant-pharXiv:2608.20593•Aug 24, 2026•0 citations

Parallelizing quantum circuit synthesis

Olivia Di Matteo, Michele Mosca

Quantum circuit synthesis is the process in which an arbitrary unitary operation is decomposed into a sequence of gates from a universal set, typically one which a quantum computer can implement both efficiently and fault-tolerantly. As physical implementations of quantum computers improve, the need is growing for tools that can effectively synthesize components of the circuits and algorithms they will run. Existing algorithms for exact, multi-qubit circuit synthesis scale exponentially in the number of qubits and circuit depth, leaving synthesis intractable for circuits on more than a handful of qubits. Even modest improvements in circuit synthesis procedures may lead to significant advances, pushing forward the boundaries of not only the size of solvable circuit synthesis problems, but also in what can be realized physically as a result of having more efficient circuits. We present a method for quantum circuit synthesis using deterministic walks. Also termed pseudorandom walks, these are walks in which once a starting point is chosen, its path is completely determined. We apply our method to construct a parallel framework for circuit synthesis, and implement one such version performing optimal T -count synthesis over the Clifford+ T gate set. We use our software to present examples where parallelization offers a significant speedup on the runtime, as well as directly confirm that the 4-qubit 1-bit full adder has optimal T -count 7 and T -depth 3.

arXiv:1606.07413•Quantum Science and Technology•Mar 1, 2016•42 citations

More efficient Clifford+T synthesis for small-angle rotations and application to Trotterization

Marius Bothe, Christoph Sünderhauf, Michael J. Witham +2 more

Clifford+T synthesis of rotation gates is an important routine in fault-tolerant quantum compilation. While Clifford+T synthesis is scalable, it has a high overhead of tens of T gates per rotation in practice, translating to high resource estimates for many fault-tolerant algorithms. However, these well-known results, including those using probabilistic mixtures [Quantum 7, 1208 (2023)], are independent of the rotation angle $θ$, requiring $O(\log 1/δ)$ T gates. We show that it is possible to do much better for small angles, reducing the T cost to $\tilde{O}(θ^2/δ)$, and returning to existing $O(\log1/δ)$ results in the worst case. This is particularly important since many algorithms, such as Trotterization, are dominated by small-angle rotations. Further, we perform a detailed theoretical and numerical study of quasi-probabilities, which can further reduce the total T cost of large circuits by orders of magnitude with only a small overhead in sample complexity. We also develop a scheme based on quasi-probability mixtures of Clifford+T fallback channels. We derive new $θ$-dependent formulas that can be used for resource estimation of fault-tolerant quantum algorithms. As an application of our results, we show that the gate cost of Trotterization circuits compiled to a Clifford+T gate set is constant in the small Trotter step size limit, and can be reduced by orders of magnitude even for large step sizes. The cost of fault-tolerant Trotterization for a variety of applications should be re-examined in light of these results. Our work dispels the widely-stated claim that Clifford+T rotation synthesis has a high cost independent of $θ$, and further develops a scalable quasi-probability method for rotation synthesis. We also expect our results to bring forward useful early fault-tolerant quantum computing by reducing required magic state resources.

quant-pharXiv:2605.31544•Jun 1, 2026•11 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.

arXiv:1308.4134•Quantum Information and Computation•Nov 1, 2014•140 citations

A polynomial time and space heuristic algorithm for T-count

Michele Mosca, Priyanka Mukhopadhyay

Abstract An important part of reaping computational advantage from a quantum computer is to reduce the quantum resources needed to implement a desired quantum algorithm. Quantum algorithms that are too large to be practical on noisy intermediate scale quantum devices will require fault-tolerant error correction. This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes, in particular, those for which implementing the T gate consumes vastly more resources than the other gates in the gate set. More specifically, in this paper we consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford + T gate set. The Clifford + T gate set is a universal gate set and in this group, using state-of-the-art surface codes, the T gate is by far the most expensive component to implement fault-tolerantly. So it is important to minimize the number of T gates necessary for a fault-tolerant implementation. Our primary interest is to compute a circuit for a given n -qubit unitary U , using the minimum possible number of T gates (called the T-count of unitary U ). We consider the problem COUNT-T, the optimization version of which aims to find the T-count of U . In its decision version the goal is to decide if the T-count is at most some positive integer m . Given an oracle for COUNT-T, we can compute a T-count-optimal circuit in time polynomial in the T-count and dimension of U . We give a provable classical algorithm that solves COUNT-T (decision) in time O N 2 ( c − 1 ) ⌈ m c ⌉ p o l y ( m , N ) and space O N 2 ⌈ m c ⌉ p o l y ( m , N ) , where N = 2 n and c ⩾ 2. This gives a space-time trade-off for solving this problem with variants of meet-in-the-middle techniques. We also introduce an asymptotically faster multiplication method that shaves a factor of N 0.7457 off of the overall complexity. Lastly, beyond our improvements to the rigorous algorithm, we give a heuristic algorithm that outputs a T-count-optimal circuit and has space and time complexity poly( m , N ), under some assumptions. In our heuristic algorithm we developed a novel way of pruning the search space. While our heuristic method still scales exponentially with the number of qubits (though with a lower exponent), there is a large improvement by going from exponential to polynomial scaling with m . We implemented our heuristic algorithm with up to 4 qubit unitaries and obtained a significant improvement in time. For all benchmark and random unitaries we studied, the T-count returned by our algorithm is at most the T-count of their circuits shown in previous papers.

arXiv:2006.12440•Quantum Science and Technology•Oct 7, 2021•34 citations

Approximate synthesis of general single-qubit unitaries over the Clifford+$\sqrt{T}$ gate set

Mathias Weiden, Jae Won Kim, Justin Kalloor +2 more

For the standard Clifford+$T$ gate set, deterministic, ancilla-free synthesis now attains the minimal $T$-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The $\sqrt{T}$ gate rotates by half the angle of $T$, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+$\sqrt{T}$ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from $\varepsilon=10^{-3}$ to $10^{-8}$, the cost of Clifford+$\sqrt{T}$ circuits scales as $2.4\log_2(1/\varepsilon)$ compared to $3.0\log_2(1/\varepsilon)$ for $T$-count-optimal Clifford+$T$ circuits. Once a one-time catalyst state is amortized, the Clifford+$\sqrt{T}$ circuits are never costlier than their Clifford+$T$ counterparts.

quant-pharXiv:2609.16659•Sep 16, 2026•0 citations
Preparing a quantum circuit that implements a given sparse state is an important building block that is necessary for many different quantum algorithms. In the context of fault-tolerant quantum computing, the so-called non-Clifford gates are much more expensive to perform than the Clifford ones. We hence provide an algorithm for synthesizing sparse quantum states with a special care for quantum resources. The circuit depth, ancilla count, and crucially non-Clifford count of the circuit produced by the algorithm are all linear in the sparsity when access to arbitrary-angled rotations is given. When compiled down to the standard Clifford+T gate set, several constructions can be given for increasingly better T-count and depth at the expense of a larger number of ancillae. The most optimised construction for T-count reaches O(s+log⁡2(1/ε))\mathcal O\left(s+\log_2(1/ε)\right)O(s+log2​(1/ε)) T gates for error εεε. The constructions are broken into two parts, one that synthesises a generalized W-state, well studied in the literature; and the second which is a classical reversible circuit implementing a permutation that maps the basis states of the W-state to those of the target sparse quantum state. We reduce this problem to the diagonalization of a binary matrix, using a specific set of elementary matrix operations corresponding to the classical reversible gates. We then solve this problem using a new version of Gauss-Jordan elimination, that minimizes the circuit complexities including circuit depth using parallel elimination steps. When the circuit is applied in one direction, we notice that all occurrences of (the expensive) Toffoli gates can all be replaced by adaptive Clifford circuits, leading to a better non-Clifford count.
Sparse quantum state preparation concerns an nnn-qubit target state that is a superposition of only d≪2nd \ll 2^nd≪2n computational basis states. Existing approaches exploit this sparsity by compressing these ddd basis states and their amplitudes onto a smaller set of qubits, called the dense register, before expanding the prepared state to the full register. Rather than relying on the permutation-based compression used in prior work, we exploit affine relationships among the binary configurations over the finite field GF⁡(2)\operatorname{GF}(2)GF(2) to reduce both the non-Clifford gate count and the ancillary qubit count. Invertible affine transformations over GF⁡(2)\operatorname{GF}(2)GF(2), comprising Gaussian elimination and all-ones-row removal, first reduce the dense register from nnn to the rank rrr using only Clifford gates and no ancillary qubits. An optional binary encoding stage then trades additional Toffoli gates and ancillary qubits for further compression to the minimum ⌈log⁡2d⌉\lceil\log_2 d\rceil⌈log2​d⌉ dense qubits needed to represent ddd distinct configurations. For chemically relevant wavefunctions, such as those obtained from selected configuration interaction calculations, shared electronic excitation patterns produce many of these affine relationships, enabling substantial Clifford-only compression before binary encoding. Across the molecular benchmarks, our method requires the fewest ancillary qubits among the evaluated sparse state preparation methods while maintaining comparable non-Clifford gate counts when using binary encoding.
Quantum circuit synthesis is the process in which an arbitrary unitary operation is decomposed into a sequence of gates from a universal set, typically one which a quantum computer can implement both efficiently and fault-tolerantly. As physical implementations of quantum computers improve, the need is growing for tools that can effectively synthesize components of the circuits and algorithms they will run. Existing algorithms for exact, multi-qubit circuit synthesis scale exponentially in the number of qubits and circuit depth, leaving synthesis intractable for circuits on more than a handful of qubits. Even modest improvements in circuit synthesis procedures may lead to significant advances, pushing forward the boundaries of not only the size of solvable circuit synthesis problems, but also in what can be realized physically as a result of having more efficient circuits. We present a method for quantum circuit synthesis using deterministic walks. Also termed pseudorandom walks, these are walks in which once a starting point is chosen, its path is completely determined. We apply our method to construct a parallel framework for circuit synthesis, and implement one such version performing optimal T -count synthesis over the Clifford+ T gate set. We use our software to present examples where parallelization offers a significant speedup on the runtime, as well as directly confirm that the 4-qubit 1-bit full adder has optimal T -count 7 and T -depth 3.
Clifford+T synthesis of rotation gates is an important routine in fault-tolerant quantum compilation. While Clifford+T synthesis is scalable, it has a high overhead of tens of T gates per rotation in practice, translating to high resource estimates for many fault-tolerant algorithms. However, these well-known results, including those using probabilistic mixtures [Quantum 7, 1208 (2023)], are independent of the rotation angle θθθ, requiring O(log⁡1/δ)O(\log 1/δ)O(log1/δ) T gates. We show that it is possible to do much better for small angles, reducing the T cost to O~(θ2/δ)\tilde{O}(θ^2/δ)O~(θ2/δ), and returning to existing O(log⁡1/δ)O(\log1/δ)O(log1/δ) results in the worst case. This is particularly important since many algorithms, such as Trotterization, are dominated by small-angle rotations. Further, we perform a detailed theoretical and numerical study of quasi-probabilities, which can further reduce the total T cost of large circuits by orders of magnitude with only a small overhead in sample complexity. We also develop a scheme based on quasi-probability mixtures of Clifford+T fallback channels. We derive new θθθ-dependent formulas that can be used for resource estimation of fault-tolerant quantum algorithms. As an application of our results, we show that the gate cost of Trotterization circuits compiled to a Clifford+T gate set is constant in the small Trotter step size limit, and can be reduced by orders of magnitude even for large step sizes. The cost of fault-tolerant Trotterization for a variety of applications should be re-examined in light of these results. Our work dispels the widely-stated claim that Clifford+T rotation synthesis has a high cost independent of θθθ, and further develops a scalable quasi-probability method for rotation synthesis. We also expect our results to bring forward useful early fault-tolerant quantum computing by reducing required magic state resources.
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.
Abstract An important part of reaping computational advantage from a quantum computer is to reduce the quantum resources needed to implement a desired quantum algorithm. Quantum algorithms that are too large to be practical on noisy intermediate scale quantum devices will require fault-tolerant error correction. This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes, in particular, those for which implementing the T gate consumes vastly more resources than the other gates in the gate set. More specifically, in this paper we consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford + T gate set. The Clifford + T gate set is a universal gate set and in this group, using state-of-the-art surface codes, the T gate is by far the most expensive component to implement fault-tolerantly. So it is important to minimize the number of T gates necessary for a fault-tolerant implementation. Our primary interest is to compute a circuit for a given n -qubit unitary U , using the minimum possible number of T gates (called the T-count of unitary U ). We consider the problem COUNT-T, the optimization version of which aims to find the T-count of U . In its decision version the goal is to decide if the T-count is at most some positive integer m . Given an oracle for COUNT-T, we can compute a T-count-optimal circuit in time polynomial in the T-count and dimension of U . We give a provable classical algorithm that solves COUNT-T (decision) in time O N 2 ( c − 1 ) ⌈ m c ⌉ p o l y ( m , N ) and space O N 2 ⌈ m c ⌉ p o l y ( m , N ) , where N = 2 n and c ⩾ 2. This gives a space-time trade-off for solving this problem with variants of meet-in-the-middle techniques. We also introduce an asymptotically faster multiplication method that shaves a factor of N 0.7457 off of the overall complexity. Lastly, beyond our improvements to the rigorous algorithm, we give a heuristic algorithm that outputs a T-count-optimal circuit and has space and time complexity poly( m , N ), under some assumptions. In our heuristic algorithm we developed a novel way of pruning the search space. While our heuristic method still scales exponentially with the number of qubits (though with a lower exponent), there is a large improvement by going from exponential to polynomial scaling with m . We implemented our heuristic algorithm with up to 4 qubit unitaries and obtained a significant improvement in time. For all benchmark and random unitaries we studied, the T-count returned by our algorithm is at most the T-count of their circuits shown in previous papers.
Approximate synthesis of general single-qubit unitaries over the Clifford+T\sqrt{T}T​ gate set
For the standard Clifford+TTT gate set, deterministic, ancilla-free synthesis now attains the minimal TTT-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The T\sqrt{T}T​ gate rotates by half the angle of TTT, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+T\sqrt{T}T​ algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from ε=10−3\varepsilon=10^{-3}ε=10−3 to 10−810^{-8}10−8, the cost of Clifford+T\sqrt{T}T​ circuits scales as 2.4log⁡2(1/ε)2.4\log_2(1/\varepsilon)2.4log2​(1/ε) compared to 3.0log⁡2(1/ε)3.0\log_2(1/\varepsilon)3.0log2​(1/ε) for TTT-count-optimal Clifford+TTT circuits. Once a one-time catalyst state is amortized, the Clifford+T\sqrt{T}T​ circuits are never costlier than their Clifford+TTT counterparts.