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:2106.07099 · Journal of Physics Communications

Composability of global phase invariant distance and its application to approximation error management

Priyanka Mukhopadhyay

Published Nov 1, 2021• 6 citations
arXivHTMLPDF

Abstract

Abstract Many quantum algorithms can be written as a composition of unitaries, some of which can be exactly synthesized by a universal fault-tolerant gate set like Clifford+T, while others can be approximately synthesized. One task of a quantum compiler is to synthesize each approximately synthesizable unitary up to some approximation error, such that the error of the overall unitary remains bounded by a certain amount. In this paper we consider the case when the errors are measured in the global phase invariant distance. Apart from deriving a relation between this distance and the Frobenius norm, we show that this distance composes. If a unitary is written as a composition (product and tensor product) of other unitaries, we derive bounds on the error of the overall unitary as a function of the errors of the composed unitaries. Our bound is better than the sum-of-error bound, derived by Bernstein- Vazirani(1997), for the operator norm. This builds the intuition that working with the global phase invariant distance might give us a lower resource count while synthesizing quantum circuits. Next we consider the following problem. Suppose we are given a decomposition of a unitary, that is, the unitary is expressed as a composition of other unitaries. We want to distribute the errors in each component such that the resource-count (specifically T-count) is optimized. We consider the specific case when the unitary can be decomposed such that the R z (θ) gates are the only approximately synthesizable component. We prove analytically that for both the operator norm and global phase invariant distance, the error should be distributed equally among these components (given some approximations). The optimal number of T-gates obtained by using the global phase invariant distance is less than what is obtained using the operator norm. Furthermore, we show that in case of approximate Quantum Fourier Transform, the error obtained by pruning rotation gates is less when measured in this distance, rather than the operator norm.

DOI
10.1088/2399-6528/ac3a43

Related papers

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•29 citations

CS-count-optimal quantum circuits for arbitrary multi-qubit unitaries

Priyanka Mukhopadhyay

Abstract In quantum computing there are quite a few universal gate sets, each having their own characteristics. In this paper we study the Clifford+CS universal fault-tolerant gate set. The CS gate is used is many applications and this gate set is an important alternative to Clifford+T. We introduce a generating set in order to represent any unitary implementable by this gate set and with this we derive a bound on the CS-count of arbitrary multi-qubit unitaries. Analysing the channel representation of the generating set elements, we infer $${\mathcal {J}}_n^{CS}\subset {\mathcal {J}}_n^T$$ J n CS ⊂ J n T , where $${\mathcal {J}}_n^{CS}$$ J n CS and $${\mathcal {J}}_n^T$$ J n T are the set of unitaries exactly implementable by the Clifford+CS and Clifford+T gate sets, respectively. We develop CS-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries. With the help of these we derive a CS-count-optimal circuit for Toffoli, implying $${\mathcal {J}}_n^{Tof}={\mathcal {J}}_n^{CS}$$ J n Tof = J n CS , where $${\mathcal {J}}_n^{Tof}$$ J n Tof is the set of unitaries exactly implementable by the Clifford+Toffoli gate set. Such conclusions can have an important impact on resource estimates of quantum algorithms.

Scientific Reports•Jun 17, 2024•2 citations

High-Precision Multi-Qubit Clifford+T Synthesis by Unitary Diagonalization

Mathias Weiden, Justin Kalloor, John David Kubiatowicz +2 more

Resource-efficient and high-precision approximate synthesis of quantum circuits expressed in the Clifford+T gate set is vital for Fault-Tolerant quantum computing.Efficient optimal methods are known for single-qubit R Z unitaries, otherwise the problem is generally intractable.Search-based methods, like simulated annealing, empirically generate low resource cost approximate implementations of general multi-qubit unitaries so long as low precision (Hilbert-Schmidt distances of ε ≥ 10 -2 ) can be tolerated.These algorithms build up circuits that directly invert target unitaries.We instead leverage search-based methods to first approximately diagonalize a unitary, then perform the inversion analytically.This lets difficult continuous rotations be bypassed and handled in a postprocessing step.Our approach improves both the implementation precision and run time of synthesis algorithms by orders of magnitude when evaluated on unitaries from real quantum algorithms.On benchmarks previously synthesizable only with analytical techniques like the Quantum Shannon Decomposition, diagonalization uses an average of 95% fewer non-Clifford gates.

arXiv:2409.00433•Electronic Proceedings in Theoretical Computer Science•Aug 19, 2025•1 citation

Efficient Approximation of Diagonal Unitaries over the Clifford+T Basis

Welch, Jonathan, Alex Bocharov, Krysta M. Svore

We present an algorithm for the approximate decomposition of diagonal operators, focusing specifically on decompositions over the Clifford+$T$ basis, that minimize the number of phase-rotation gates in the synthesized approximation circuit. The equivalent $T$-count of the synthesized circuit is bounded by $k \, C_0 \log_2(1/\varepsilon) + E(n,k)$, where $k$ is the number of distinct phases in the diagonal $n$-qubit unitary, $\varepsilon$ is the desired precision, $C_0$ is a quality factor of the implementation method ($1

arXiv:1412.5608•Dec 17, 2014•1 citation

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

Bounds in the Projective Unitary Group with Respect to Global Phase Invariant Distance

Bhanu Pratap Yadav, Mahdi Bayanifar, Olav Tirkkonen

We consider a global phase-invariant distance in the projective unitary group ${\mathcal{P}}{{\mathcal{U}}_n},$ relevant for universal quantum computing. We obtain the volume and measure of small metric ball in ${\mathcal{P}}{{\mathcal{U}}_n}$ and derive the Gilbert-Varshamov and Hamming bounds in ${\mathcal{P}}{{\mathcal{U}}_n}$. In addition, we provide upper and lower bounds for the kissing radius of the codebooks in ${\mathcal{P}}{{\mathcal{U}}_n}$ as a function of the minimum distance. Using the lower bound of the kissing radius, we find a tight Hamming bound. Also, we establish bounds on the distortion-rate function for quantizing a source uniformly distributed over ${\mathcal{P}}{{\mathcal{U}}_n}$. As example codebooks in ${\mathcal{P}}{{\mathcal{U}}_n}$ we consider the projective, Pauli and Clifford groups, as well as the projective group of diagonal gates in the Clifford hierarchy, and find their minimum distances. Finally, we verify the analytical results by simulation.

IEEE Information Theory Workshop (ITW)•Sep 29, 2025•0 citations
Abstract Many quantum algorithms can be written as a composition of unitaries, some of which can be exactly synthesized by a universal fault-tolerant gate set like Clifford+T, while others can be approximately synthesized. One task of a quantum compiler is to synthesize each approximately synthesizable unitary up to some approximation error, such that the error of the overall unitary remains bounded by a certain amount. In this paper we consider the case when the errors are measured in the global phase invariant distance. Apart from deriving a relation between this distance and the Frobenius norm, we show that this distance composes. If a unitary is written as a composition (product and tensor product) of other unitaries, we derive bounds on the error of the overall unitary as a function of the errors of the composed unitaries. Our bound is better than the sum-of-error bound, derived by Bernstein- Vazirani(1997), for the operator norm. This builds the intuition that working with the global phase invariant distance might give us a lower resource count while synthesizing quantum circuits. Next we consider the following problem. Suppose we are given a decomposition of a unitary, that is, the unitary is expressed as a composition of other unitaries. We want to distribute the errors in each component such that the resource-count (specifically T-count) is optimized. We consider the specific case when the unitary can be decomposed such that the R z (θ) gates are the only approximately synthesizable component. We prove analytically that for both the operator norm and global phase invariant distance, the error should be distributed equally among these components (given some approximations). The optimal number of T-gates obtained by using the global phase invariant distance is less than what is obtained using the operator norm. Furthermore, we show that in case of approximate Quantum Fourier Transform, the error obtained by pruning rotation gates is less when measured in this distance, rather than the operator norm.
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.
Abstract In quantum computing there are quite a few universal gate sets, each having their own characteristics. In this paper we study the Clifford+CS universal fault-tolerant gate set. The CS gate is used is many applications and this gate set is an important alternative to Clifford+T. We introduce a generating set in order to represent any unitary implementable by this gate set and with this we derive a bound on the CS-count of arbitrary multi-qubit unitaries. Analysing the channel representation of the generating set elements, we infer JnCS⊂JnT{\mathcal {J}}_n^{CS}\subset {\mathcal {J}}_n^TJnCS​⊂JnT​ J n CS ⊂ J n T , where JnCS{\mathcal {J}}_n^{CS}JnCS​ J n CS and JnT{\mathcal {J}}_n^TJnT​ J n T are the set of unitaries exactly implementable by the Clifford+CS and Clifford+T gate sets, respectively. We develop CS-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries. With the help of these we derive a CS-count-optimal circuit for Toffoli, implying JnTof=JnCS{\mathcal {J}}_n^{Tof}={\mathcal {J}}_n^{CS}JnTof​=JnCS​ J n Tof = J n CS , where JnTof{\mathcal {J}}_n^{Tof}JnTof​ J n Tof is the set of unitaries exactly implementable by the Clifford+Toffoli gate set. Such conclusions can have an important impact on resource estimates of quantum algorithms.
Resource-efficient and high-precision approximate synthesis of quantum circuits expressed in the Clifford+T gate set is vital for Fault-Tolerant quantum computing.Efficient optimal methods are known for single-qubit R Z unitaries, otherwise the problem is generally intractable.Search-based methods, like simulated annealing, empirically generate low resource cost approximate implementations of general multi-qubit unitaries so long as low precision (Hilbert-Schmidt distances of ε ≥ 10 -2 ) can be tolerated.These algorithms build up circuits that directly invert target unitaries.We instead leverage search-based methods to first approximately diagonalize a unitary, then perform the inversion analytically.This lets difficult continuous rotations be bypassed and handled in a postprocessing step.Our approach improves both the implementation precision and run time of synthesis algorithms by orders of magnitude when evaluated on unitaries from real quantum algorithms.On benchmarks previously synthesizable only with analytical techniques like the Quantum Shannon Decomposition, diagonalization uses an average of 95% fewer non-Clifford gates.
We present an algorithm for the approximate decomposition of diagonal operators, focusing specifically on decompositions over the Clifford+TTT basis, that minimize the number of phase-rotation gates in the synthesized approximation circuit. The equivalent TTT-count of the synthesized circuit is bounded by k C0log⁡2(1/ε)+E(n,k)k \, C_0 \log_2(1/\varepsilon) + E(n,k)kC0​log2​(1/ε)+E(n,k), where kkk is the number of distinct phases in the diagonal nnn-qubit unitary, ε\varepsilonε is the desired precision, C0C_0C0​ is a quality factor of the implementation method ($1
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.
We consider a global phase-invariant distance in the projective unitary group PUn,{\mathcal{P}}{{\mathcal{U}}_n},PUn​, relevant for universal quantum computing. We obtain the volume and measure of small metric ball in PUn{\mathcal{P}}{{\mathcal{U}}_n}PUn​ and derive the Gilbert-Varshamov and Hamming bounds in PUn{\mathcal{P}}{{\mathcal{U}}_n}PUn​. In addition, we provide upper and lower bounds for the kissing radius of the codebooks in PUn{\mathcal{P}}{{\mathcal{U}}_n}PUn​ as a function of the minimum distance. Using the lower bound of the kissing radius, we find a tight Hamming bound. Also, we establish bounds on the distortion-rate function for quantizing a source uniformly distributed over PUn{\mathcal{P}}{{\mathcal{U}}_n}PUn​. As example codebooks in PUn{\mathcal{P}}{{\mathcal{U}}_n}PUn​ we consider the projective, Pauli and Clifford groups, as well as the projective group of diagonal gates in the Clifford hierarchy, and find their minimum distances. Finally, we verify the analytical results by simulation.