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

A framework for exact synthesis

Vadym Kliuchnikov, Jon Yard

Published Apr 16, 2015• 57 citations
arXivHTMLPDF

Abstract

Exact synthesis is a tool used in algorithms for approximating an arbitrary qubit unitary with a sequence of quantum gates from some finite set. These approximation algorithms find asymptotically optimal approximations in probabilistic polynomial time, in some cases even finding the optimal solution in probabilistic polynomial time given access to an oracle for factoring integers. In this paper, we present a common mathematical structure underlying all results related to the exact synthesis of qubit unitaries known to date, including Clifford+T, Clifford-cyclotomic and V-basis gate sets, as well as gates sets induced by the braiding of Fibonacci anyons in topological quantum computing. The framework presented here also provides a means to answer questions related to the exact synthesis of unitaries for wide classes of other gate sets, such as Clifford+T+V and SU(2) level k anyons.

DOI
10.48550/arxiv.1504.04350

Related papers

Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets

Simon Forest, David Gosset, Vadym Kliuchnikov +1 more

We generalize an efficient exact synthesis algorithm for single-qubit unitaries over the Clifford+T gate set which was presented by Kliuchnikov, Maslov, and Mosca [Quantum Inf. Comput. 13(7,8), 607–630 (2013)]. Their algorithm takes as input an exactly synthesizable single-qubit unitary—one which can be expressed without error as a product of Clifford and T gates—and outputs a sequence of gates which implements it. The algorithm is optimal in the sense that the length of the sequence, measured by the number of T gates, is smallest possible. In this paper, for each positive even integer n, we consider the “Clifford-cyclotomic” gate set consisting of the Clifford group plus a z-rotation by πn. We present an efficient exact synthesis algorithm which outputs a decomposition using the minimum number of πn z-rotations. For the Clifford+T case n = 4, the group of exactly synthesizable unitaries was shown to be equal to the group of unitaries with entries over the ring Z[eiπn,1/2]. We prove that this characterization holds for a handful of other small values of n but the fraction of positive even integers for which it fails to hold is 100%.

arXiv:1501.04944•Journal of Mathematical Physics•Aug 1, 2015•44 citations

A Framework for Approximating Qubit Unitaries

Vadym Kliuchnikov, Alex Bocharov, Martin Roetteler +1 more

We present an algorithm for efficiently approximating of qubit unitaries over gate sets derived from totally definite quaternion algebras. It achieves $\varepsilon$-approximations using circuits of length $O(\log(1/\varepsilon))$, which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously-known algorithms for Clifford+T [arXiv:1212.6253], V-basis [arXiv:1303.1411] and Clifford+$π/12$ [arXiv:1409.3552], running on average in time polynomial in $O(\log(1/\varepsilon))$ (conditional on a number-theoretic conjecture). Ours is the first such algorithm that works for a wide range of gate sets and provides insight into what should constitute a "good" gate set for a fault-tolerant quantum computer.

arXiv:1510.03888•Oct 13, 2015•10 citations

New methods for Quantum Compiling

Vadym Kliuchnikov

The efficiency of compiling high-level quantum algorithms into instruction sets native to quantum computers defines the moment in the future when we will be able to solve interesting and important problems on quantum computers. In my work I focus on the new methods for compiling single qubit operations that appear in many quantum algorithms into single qubit operations natively supported by several popular architectures. In addition, I study several questions related to synthesis and optimization of multiqubit operations. \n \n \nWhen studying the single qubit case, I consider two native instruction sets. The first one is Clifford+T; it is supported by conventional quantum computers implementing fault tolerance protocols based on concatenated and surface codes, and by topological quantum computers based on Ising anyons. The second instruction set is the one supported by topological quantum computers based on Fibonacci anyons. I show that in both cases one can use the number theoretic structure of the problem and methods of computational algebraic number theory to achieve improvements over the previous state of the art by factors ranging from 10 to 1000 for instances of the problem interesting in practice. This order of improvement might make certain interesting quantum computations possible several years earlier. \n \n \nThe work related to multiqubit operations is on exact synthesis and optimization of Clifford+T and Clifford circuits. I show an exact synthesis algorithm for unitaries generated by Clifford+T circuits requiring exponentially less number of gates than previous state of the art. For Clifford circuits two directions are studied: the algorithm for finding optimal circuits acting on a small number of qubits and heuristics for larger circuits optimization. The techniques developed allows one to reduce the size of encoding and decoding circuits for quantum error correcting codes by 40-50\\% and also finds their applications in randomized benchmarking protocols.

•Apr 30, 2014•3 citations

A framework for approximating qubit unitaries

Vadym Kliuchnikov

We present an algorithm for efficiently approximating of qubit unitaries over gate sets derived from totally definite quaternion algebras. It achieves ε-approximations using circuits of length O(log(1/ε)), which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously-known algorithms for Clifford+T [arXiv:1212.6253], V-basis [arXiv:1303.1411] and Clifford+π/12 [arXiv:1409.3552], running on average in time polynomial in O(log(1/ε)) (conditional on a number-theoretic conjecture). Ours is the first such algorithm that works for a wide range of gate sets and provides insight into what should constitute a "good" gate set for a fault-tolerant quantum computer. Joint work with Alex Bocharov, Martin Roetteler, Jon Yard: http://arxiv.org/abs/1510.03888

•Jan 1, 2016•13 citations

Multi-qubit circuit synthesis and Hermitian lattices

Vadym Kliuchnikov, Sebastian Schönnenbeck

We present new optimal and heuristic algorithms for exact synthesis of multi-qubit unitaries and isometries. For example, our algorithms find Clifford and T circuits for unitaries with entries in $\mathbb{Z}[i,1/\sqrt{2}]$. The optimal algorithms are the A* search instantiated with a new data structure for graph vertices and new consistent heuristic functions. We also prove that for some gate sets, best-first search synthesis relying on the same heuristic is efficient. For example, for two-qubit Clifford and T circuits, our best-first search runtime is proportional to the T-count of the unitary. Our algorithms rely on Hermite and Smith Normal Forms of matrices with entries in a ring of integers of a number field, and we leverage the theory of and algorithms for Hermitian lattices over number fields to prove efficiency. These new techniques are of independent interest for future work on multi-qubit exact circuit synthesis and related questions.

arXiv:2405.19302•May 29, 2024•0 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
Exact synthesis is a tool used in algorithms for approximating an arbitrary qubit unitary with a sequence of quantum gates from some finite set. These approximation algorithms find asymptotically optimal approximations in probabilistic polynomial time, in some cases even finding the optimal solution in probabilistic polynomial time given access to an oracle for factoring integers. In this paper, we present a common mathematical structure underlying all results related to the exact synthesis of qubit unitaries known to date, including Clifford+T, Clifford-cyclotomic and V-basis gate sets, as well as gates sets induced by the braiding of Fibonacci anyons in topological quantum computing. The framework presented here also provides a means to answer questions related to the exact synthesis of unitaries for wide classes of other gate sets, such as Clifford+T+V and SU(2) level k anyons.
We generalize an efficient exact synthesis algorithm for single-qubit unitaries over the Clifford+T gate set which was presented by Kliuchnikov, Maslov, and Mosca [Quantum Inf. Comput. 13(7,8), 607–630 (2013)]. Their algorithm takes as input an exactly synthesizable single-qubit unitary—one which can be expressed without error as a product of Clifford and T gates—and outputs a sequence of gates which implements it. The algorithm is optimal in the sense that the length of the sequence, measured by the number of T gates, is smallest possible. In this paper, for each positive even integer n, we consider the “Clifford-cyclotomic” gate set consisting of the Clifford group plus a z-rotation by πn. We present an efficient exact synthesis algorithm which outputs a decomposition using the minimum number of πn z-rotations. For the Clifford+T case n = 4, the group of exactly synthesizable unitaries was shown to be equal to the group of unitaries with entries over the ring Z[eiπn,1/2]. We prove that this characterization holds for a handful of other small values of n but the fraction of positive even integers for which it fails to hold is 100%.
We present an algorithm for efficiently approximating of qubit unitaries over gate sets derived from totally definite quaternion algebras. It achieves ε\varepsilonε-approximations using circuits of length O(log⁡(1/ε))O(\log(1/\varepsilon))O(log(1/ε)), which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously-known algorithms for Clifford+T [arXiv:1212.6253], V-basis [arXiv:1303.1411] and Clifford+π/12π/12π/12 [arXiv:1409.3552], running on average in time polynomial in O(log⁡(1/ε))O(\log(1/\varepsilon))O(log(1/ε)) (conditional on a number-theoretic conjecture). Ours is the first such algorithm that works for a wide range of gate sets and provides insight into what should constitute a "good" gate set for a fault-tolerant quantum computer.
The efficiency of compiling high-level quantum algorithms into instruction sets native to quantum computers defines the moment in the future when we will be able to solve interesting and important problems on quantum computers. In my work I focus on the new methods for compiling single qubit operations that appear in many quantum algorithms into single qubit operations natively supported by several popular architectures. In addition, I study several questions related to synthesis and optimization of multiqubit operations. \n \n \nWhen studying the single qubit case, I consider two native instruction sets. The first one is Clifford+T; it is supported by conventional quantum computers implementing fault tolerance protocols based on concatenated and surface codes, and by topological quantum computers based on Ising anyons. The second instruction set is the one supported by topological quantum computers based on Fibonacci anyons. I show that in both cases one can use the number theoretic structure of the problem and methods of computational algebraic number theory to achieve improvements over the previous state of the art by factors ranging from 10 to 1000 for instances of the problem interesting in practice. This order of improvement might make certain interesting quantum computations possible several years earlier. \n \n \nThe work related to multiqubit operations is on exact synthesis and optimization of Clifford+T and Clifford circuits. I show an exact synthesis algorithm for unitaries generated by Clifford+T circuits requiring exponentially less number of gates than previous state of the art. For Clifford circuits two directions are studied: the algorithm for finding optimal circuits acting on a small number of qubits and heuristics for larger circuits optimization. The techniques developed allows one to reduce the size of encoding and decoding circuits for quantum error correcting codes by 40-50\\% and also finds their applications in randomized benchmarking protocols.
We present an algorithm for efficiently approximating of qubit unitaries over gate sets derived from totally definite quaternion algebras. It achieves ε-approximations using circuits of length O(log(1/ε)), which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously-known algorithms for Clifford+T [arXiv:1212.6253], V-basis [arXiv:1303.1411] and Clifford+π/12 [arXiv:1409.3552], running on average in time polynomial in O(log(1/ε)) (conditional on a number-theoretic conjecture). Ours is the first such algorithm that works for a wide range of gate sets and provides insight into what should constitute a "good" gate set for a fault-tolerant quantum computer. Joint work with Alex Bocharov, Martin Roetteler, Jon Yard: http://arxiv.org/abs/1510.03888
We present new optimal and heuristic algorithms for exact synthesis of multi-qubit unitaries and isometries. For example, our algorithms find Clifford and T circuits for unitaries with entries in Z[i,1/2]\mathbb{Z}[i,1/\sqrt{2}]Z[i,1/2​]. The optimal algorithms are the A* search instantiated with a new data structure for graph vertices and new consistent heuristic functions. We also prove that for some gate sets, best-first search synthesis relying on the same heuristic is efficient. For example, for two-qubit Clifford and T circuits, our best-first search runtime is proportional to the T-count of the unitary. Our algorithms rely on Hermite and Smith Normal Forms of matrices with entries in a ring of integers of a number field, and we leverage the theory of and algorithms for Hermitian lattices over number fields to prove efficiency. These new techniques are of independent interest for future work on multi-qubit exact circuit synthesis and related questions.
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.