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:1303.1411 · Physical Review A

Efficient decomposition of single-qubit gates into V basis circuits

Alex Bocharov, Yuri G. Gurevich, Krysta M. Svore

Published Jul 12, 2013• 72 citations
arXivHTMLPDF

Abstract

We develop efficient algorithms for compiling single-qubit unitary gates into circuits over the universal $V$ basis. The $V$ basis is an alternative universal basis to the more commonly studied basis consisting of Hadamard and $\ensuremath{\pi}/8$ gates. We propose two classical algorithms for quantum circuit compilation: the first algorithm has expected polynomial time [in precision $\mathrm{log}(1/\ensuremath{\epsilon})$] and produces an $\ensuremath{\epsilon}$ approximation to a single-qubit unitary with a circuit depth $\ensuremath{\le}12\phantom{\rule{0.16em}{0ex}}{\mathrm{log}}_{5}(2/\ensuremath{\epsilon})$. The second algorithm performs optimized direct search and yields circuits a factor of 3 to 4 times shorter than our first algorithm, but requires time exponential in $\mathrm{log}(1/\ensuremath{\epsilon})$; however, we show that in practice the runtime is reasonable for an important range of target precisions. Decomposing into the $V$ basis may offer advantages when considering the fault-tolerant implementation of quantum circuits.

DOI
10.1103/physreva.88.012313

Related papers

Resource-Optimal Single-Qubit Quantum Circuits

Alex Bocharov, Krysta M. Svore

Determining the optimal implementation of a quantum gate is critical for designing a quantum computer. We consider the crucial task of efficiently decomposing a general single-qubit quantum gate into a sequence of fault-tolerant quantum operations. For a given single-qubit circuit, we construct an optimal gate sequence consisting of fault-tolerant Hadamard (H) and π/8 rotations (T). Our scheme is based on a novel canonical form for single-qubit quantum circuits and the corresponding rules for exactly reducing a general single-qubit circuit to our canonical form. The result is optimal in the number of T gates. We demonstrate that a precomputed epsilon net of canonical circuits in combination with our scheme lowers the depth of approximation circuits by up to 3 orders of magnitude compared to previously reported results.

arXiv:1206.3223•Physical Review Letters•Nov 8, 2012•70 citations

Synthesis of V-count-optimal quantum circuits for multiqubit unitaries

Priyanka Mukhopadhyay

In this paper we study the universal V-basis gate sets, which have also been shown to be fault tolerant. Our methods and results can be applied to arbitrary dimensional basis gates, but we explicitly state results for basis gates for SU(2) and SU(4). We also include Cliffords, as done in earlier works. We introduce generating sets in order to represent any unitary implementable by these gate sets and with these we derive a bound on the V count of arbitrary multiqubit unitaries. We analyze the channel representation of the generating set elements, with the help of which we infer that none of these basis gates can be implemented exactly with the other universal fault-tolerant gate sets like Clifford+T, Clifford+CS, Clifford+Toffoli. Also T, CS, and Toffoli cannot be exactly implemented in the V basis. In fact, basis unitaries in dimension four cannot be implemented exactly with those in dimension two. We develop V-count-optimal synthesis algorithms for both approximately and exactly implementable multiqubit unitaries. With the help of these we show that two basis unitaries in dimension four are required to implement each basis unitary in dimension two. The space and time complexities of our provable algorithms are exponential in V count. But for the special case of one-qubit unitaries we achieve a complexity that is linear in V count. Both space and time complexities of our heuristic algorithms are polynomial in V count.

Physical Review A•May 14, 2024•2 citations

Efficient Decomposition of Unitary Matrices in Quantum Circuit Compilers

Anna M. Krol, Aritra Sarkar, Imran Ashraf +2 more

Unitary decomposition is a widely used method to map quantum algorithms to an arbitrary set of quantum gates. Efficient implementation of this decomposition allows for the translation of bigger unitary gates into elementary quantum operations, which is key to executing these algorithms on existing quantum computers. The decomposition can be used as an aggressive optimization method for the whole circuit, as well as to test part of an algorithm on a quantum accelerator. For the selection and implementation of the decomposition algorithm, perfect qubits are assumed. We base our decomposition technique on Quantum Shannon Decomposition, which generates O(344n) controlled-not gates for an n-qubit input gate. In addition, we implement optimizations to take advantage of the potential underlying structure in the input or intermediate matrices, as well as to minimize the execution time of the decomposition. Comparing our implementation to Qubiter and the UniversalQCompiler (UQC), we show that our implementation generates circuits that are much shorter than those of Qubiter and not much longer than the UQC. At the same time, it is also up to 10 times as fast as Qubiter and about 500 times as fast as the UQC.

arXiv:2101.02993•Applied Sciences•Jan 12, 2022•54 citations

A Resource-Optimal Canonical Form for Single-qubit Quantum Circuits

Alex Bocharov, Krysta M. Svore

Abstract. Determining the optimal implementation of a quantum gate is critical for designing a quantum computer. We consider the crucial task of efficiently decomposing a general single-qubit quantum gate into a sequence of fault-tolerant quantum operations. For a given single-qubit circuit, we construct an optimal gate sequence consisting of fault-tolerant Hadamard (H) and π/8 rotations (T). Our scheme is based on a novel canonical form for single-qubit quantum circuits and the corresponding rules for exactly reducing a general single-qubit circuit to our canonical form. The result is optimal in the number of T gates. We demonstrate that a precomputed ɛ-net of canonical circuits in combination with our scheme lowers the depth and number of T gates of approximation circuits by up to three orders of magnitude compared to previously reported results.

•Jan 1, 2012•6 citations

Universal quantum computing with a single arbitrary gate

Zhongyi Ni, Yusheng Zhao, Jin-Guo Liu

This study presents a roadmap towards utilizing a single arbitrary gate for universal quantum computing. Since two decades ago, it has been widely accepted that almost any single arbitrary gate with qubit number $>2$ is universal. Utilizing a single arbitrary gate for compiling is beneficial for systems with limited degrees of freedom, e.g. the scattering based quantum computing schemes. However, how to efficiently compile the wanted gate with a single arbitrary gate, and finally achieve fault-tolerant quantum computing is unknown. In this work, we show almost any target gate can be compiled to precision $ε$ with a circuit depth of approximately $\log(ε^{-1})$ with an improved brute-force compiling method. Under the assumption of reasonable classical resource, we show the gate imperfection can be lowered to $10^{-3}$. By treating the imperfection as coherent error, we show that the error can be further reduced by roughly two orders of magnitude with a measurement-free quantum error correction method.

arXiv:2409.20025•Sep 30, 2024•0 citations

Exact Unitary Synthesis: Simultaneously Optimal in Size and Depth-Ancilla Tradeoff

Pei Yuan, Wei Zi, Shengyu Zhang

Unitary synthesis underlies universal quantum computation by translating unitary transformations into circuits of elementary gates. We show that for any budget $m\geq 0$ of ancilla, every $n$-qubit unitary can be exactly implemented using a quantum circuit consisting of $O(4^n)$ CNOT and single-qubit gates in $O(n+4^n/(n+m))$ layers attaining the asymptotically optimal depth--ancilla tradeoff while simultaneously achieving optimal circuit size. The key idea is to encode computational basis states as wavefunctions sharing a Gaussian envelope, converting unitary action on amplitudes into coordinate transformations that admit shallow circuit implementations. The continuous encoding is then discretized, with approximation errors removed by exact residual correction. The depth-ancilla tradeoff follows by recursively applying the quantum Shannon decomposition, synthesizing its smaller unitary factors, and reusing ancillary qubits.

quant-pharXiv:2610.07010•Oct 6, 2026•0 citations
We develop efficient algorithms for compiling single-qubit unitary gates into circuits over the universal VVV basis. The VVV basis is an alternative universal basis to the more commonly studied basis consisting of Hadamard and \ensuremathπ/8\ensuremath{\pi}/8\ensuremathπ/8 gates. We propose two classical algorithms for quantum circuit compilation: the first algorithm has expected polynomial time [in precision log(1/\ensuremathϵ)\mathrm{log}(1/\ensuremath{\epsilon})log(1/\ensuremathϵ)] and produces an \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ approximation to a single-qubit unitary with a circuit depth \ensuremath≤12log5(2/\ensuremathϵ)\ensuremath{\le}12\phantom{\rule{0.16em}{0ex}}{\mathrm{log}}_{5}(2/\ensuremath{\epsilon})\ensuremath≤12log5​(2/\ensuremathϵ). The second algorithm performs optimized direct search and yields circuits a factor of 3 to 4 times shorter than our first algorithm, but requires time exponential in log(1/\ensuremathϵ)\mathrm{log}(1/\ensuremath{\epsilon})log(1/\ensuremathϵ); however, we show that in practice the runtime is reasonable for an important range of target precisions. Decomposing into the VVV basis may offer advantages when considering the fault-tolerant implementation of quantum circuits.
Determining the optimal implementation of a quantum gate is critical for designing a quantum computer. We consider the crucial task of efficiently decomposing a general single-qubit quantum gate into a sequence of fault-tolerant quantum operations. For a given single-qubit circuit, we construct an optimal gate sequence consisting of fault-tolerant Hadamard (H) and π/8 rotations (T). Our scheme is based on a novel canonical form for single-qubit quantum circuits and the corresponding rules for exactly reducing a general single-qubit circuit to our canonical form. The result is optimal in the number of T gates. We demonstrate that a precomputed epsilon net of canonical circuits in combination with our scheme lowers the depth of approximation circuits by up to 3 orders of magnitude compared to previously reported results.
In this paper we study the universal V-basis gate sets, which have also been shown to be fault tolerant. Our methods and results can be applied to arbitrary dimensional basis gates, but we explicitly state results for basis gates for SU(2) and SU(4). We also include Cliffords, as done in earlier works. We introduce generating sets in order to represent any unitary implementable by these gate sets and with these we derive a bound on the V count of arbitrary multiqubit unitaries. We analyze the channel representation of the generating set elements, with the help of which we infer that none of these basis gates can be implemented exactly with the other universal fault-tolerant gate sets like Clifford+T, Clifford+CS, Clifford+Toffoli. Also T, CS, and Toffoli cannot be exactly implemented in the V basis. In fact, basis unitaries in dimension four cannot be implemented exactly with those in dimension two. We develop V-count-optimal synthesis algorithms for both approximately and exactly implementable multiqubit unitaries. With the help of these we show that two basis unitaries in dimension four are required to implement each basis unitary in dimension two. The space and time complexities of our provable algorithms are exponential in V count. But for the special case of one-qubit unitaries we achieve a complexity that is linear in V count. Both space and time complexities of our heuristic algorithms are polynomial in V count.
Unitary decomposition is a widely used method to map quantum algorithms to an arbitrary set of quantum gates. Efficient implementation of this decomposition allows for the translation of bigger unitary gates into elementary quantum operations, which is key to executing these algorithms on existing quantum computers. The decomposition can be used as an aggressive optimization method for the whole circuit, as well as to test part of an algorithm on a quantum accelerator. For the selection and implementation of the decomposition algorithm, perfect qubits are assumed. We base our decomposition technique on Quantum Shannon Decomposition, which generates O(344n) controlled-not gates for an n-qubit input gate. In addition, we implement optimizations to take advantage of the potential underlying structure in the input or intermediate matrices, as well as to minimize the execution time of the decomposition. Comparing our implementation to Qubiter and the UniversalQCompiler (UQC), we show that our implementation generates circuits that are much shorter than those of Qubiter and not much longer than the UQC. At the same time, it is also up to 10 times as fast as Qubiter and about 500 times as fast as the UQC.
Abstract. Determining the optimal implementation of a quantum gate is critical for designing a quantum computer. We consider the crucial task of efficiently decomposing a general single-qubit quantum gate into a sequence of fault-tolerant quantum operations. For a given single-qubit circuit, we construct an optimal gate sequence consisting of fault-tolerant Hadamard (H) and π/8 rotations (T). Our scheme is based on a novel canonical form for single-qubit quantum circuits and the corresponding rules for exactly reducing a general single-qubit circuit to our canonical form. The result is optimal in the number of T gates. We demonstrate that a precomputed ɛ-net of canonical circuits in combination with our scheme lowers the depth and number of T gates of approximation circuits by up to three orders of magnitude compared to previously reported results.
This study presents a roadmap towards utilizing a single arbitrary gate for universal quantum computing. Since two decades ago, it has been widely accepted that almost any single arbitrary gate with qubit number >2>2>2 is universal. Utilizing a single arbitrary gate for compiling is beneficial for systems with limited degrees of freedom, e.g. the scattering based quantum computing schemes. However, how to efficiently compile the wanted gate with a single arbitrary gate, and finally achieve fault-tolerant quantum computing is unknown. In this work, we show almost any target gate can be compiled to precision εεε with a circuit depth of approximately log⁡(ε−1)\log(ε^{-1})log(ε−1) with an improved brute-force compiling method. Under the assumption of reasonable classical resource, we show the gate imperfection can be lowered to 10−310^{-3}10−3. By treating the imperfection as coherent error, we show that the error can be further reduced by roughly two orders of magnitude with a measurement-free quantum error correction method.
Unitary synthesis underlies universal quantum computation by translating unitary transformations into circuits of elementary gates. We show that for any budget m≥0m\geq 0m≥0 of ancilla, every nnn-qubit unitary can be exactly implemented using a quantum circuit consisting of O(4n)O(4^n)O(4n) CNOT and single-qubit gates in O(n+4n/(n+m))O(n+4^n/(n+m))O(n+4n/(n+m)) layers attaining the asymptotically optimal depth--ancilla tradeoff while simultaneously achieving optimal circuit size. The key idea is to encode computational basis states as wavefunctions sharing a Gaussian envelope, converting unitary action on amplitudes into coordinate transformations that admit shallow circuit implementations. The continuous encoding is then discretized, with approximation errors removed by exact residual correction. The depth-ancilla tradeoff follows by recursively applying the quantum Shannon decomposition, synthesizing its smaller unitary factors, and reusing ancillary qubits.