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

Wiley eBooks

Covering of SU (2) and Quantum Lattices

Steven B. Damelin

Published Jan 6, 2024• 0 citations
Publisher

Abstract

A central question in quantum computing is how elements of SU (2) the collection of 2 × 2 unitary matrices with determinant can be approximated by a small set of “generators”. A classical bit is the basic unit of information used in classical computing, which has the states 1 or 0. Quantum computing extends this concept using the notion of quantum bits. For the construction of quantum computers, a finite base set of quantum gates must be chosen so that they generate SU (2). In this chapter, the goal is to construct a universal gate set T * in SU (2) that efficiently approximates all of PSU (2) (the equivalence classes of SU (2) under multiplication by -1) using a natural and simple notion of distance. Covering exponents constructed are used to measure the efficiency of a gate set in approximating every element of SU (2).

DOI
10.1002/9781394196814.ch20

Related papers

On a Problem of Construction of Efficient Universal Sets of Quantum Gates: A preliminary report

Qingzhong Liang, Steven B. Damelin

A 1-qubit gate is defined as an element of the unitary group $U(2)$, the group of complex valued matrices whose conjugate transposes equal their inverses. In quantum computing, it is important to be able to find good approximations of 1-qubit gates by using a dense group generated by a universal subset of the projective special unitary group $G=PSU(2)$. Here, $PSU(2)$ is the group formed by taking all elements of $U(2)$ with determinant 1 and taking the quotient of this subgroup by the group $\{I,-I\}$ where $I$ is the identity matrix. In this http URL [1], Sarnak recently studied this problem motivated by developing a continued fraction type algorithm for this problem. The continued fraction algorithm is the fastest known algorithm to approximate real numbers by the dense subset of rational numbers. In this report, we study the efficiency of the approximation of $G$ by using a dense group generated by a universal subset of $G$. The measure of the efficiency $K(g)$ of an arbitrary universal subset $g$ is defined in [1] and satisfies $K(g)\geqslant 1$. $g$ is more efficient when $K(g)$ is closer to $1$. We address some open problems posed by Sarnak in [1]. This report forms the basis of the shorter preprint [LD].

•Jun 18, 2015•0 citations

Efficient quantum approximation : examining the efficiency of select universal gate sets in approximating 1-qubit quantum gates.

Brent A Mode

Quantum computation is of current ubiquitous interest in physics, computer science, and the public interest. In the not-so-distant future, quantum computers will be relatively common pieces of research equipment. Eventually, one can expect an actively quantum computer to be a common feature of life. In this work, I study the approximation efficiency of several common universal quantum gate sets at short sequence lengths using an implementation of the Solovay-Kitaev algorithm. I begin by developing from almost nothing the relevant formal mathematics to rigorously describe what one means by the terms universal gate set and covering efficiency. I then describe some interesting results on the asymptotic covering properties of certain classes of universal gate sets and discuss the theorem which the Solovay-Kitaev algorithm is based on. Moving from mathematical introduction to experimental method, I then describe how sets will be compared. I use the commonly studied sets H+T, Pauli+V, V, and Clifford+T to determine which is the most efficient at approximating randomly generated unitaries. By doing so, we get an understanding of how well each set would perform in the context of a general quantum computer processor. This was accomplished by using the same implementation of the Solovay-Kitaev algorithm throughout, with roughly equal-sized preprocessed libraries formed from each gate set, over approximations for 10,000 randomly generated unitary matrices at algorithm depth n=5. Ultimately, the Pauli+V and V sets were the most efficient and had similar performance qualities. On average the Pauli+V set produced approximations of length 15,491 and accuracy 0.0002686. The V basis produced approximations of average sequence length 16,403 and accuracy 0.0001465. This performance is about equal given this particular implementation of the Solovay-Kitaev algorithm. We conclude that this result is somewhat surprising as the general behavior and efficiency of these particular choices of gate set are expected to be similar. It is possible though that the asymptotic efficiencies of these gate sets vary by a relatively wide margin and this has effected the experiment. It is also possible that some aspect of a naive implementation of the Solovay-Kitaev algorithm resulted in the Hadamard gate based sets performing more poorly than the V basis sets overall. Due to constraints on computational power, this result could also be limited to this particular accuracy regime and could even out as tolerance 𝜀 is taken to be arbitrarily small. Further possibilities of this result as well as further work are then discussed.

•Jan 1, 2018•1 citation

On Golden Gates and Discrepancy

Steven B. Damelin, Qiwei Liang, B. A. W. Mode

A 1-qubit gate is defined as an element of the unitary group $U(2)$. The problem of finding good approximations of arbitrary 1-qubit gates is identical to that of finding a dense group generated by a universal subset of $PSU(2)$ to approximate an arbitrary element of $U(2)$. Notably, this problem has been recently studied by Sarnak in [8]. We will work with a universal gate set $T$, a subset of $SU(2)$ such that the group generated by the elements of $T$ is dense in $SU(2)$. For an arbitrary $\varepsilon > 0$, we define $t_{\varepsilon}$ as the minimum reduced word length such that every point of $SU(2)$ lies within a ball of radius $\varepsilon$ centered at the points in the dense subgroup generated by $T$. We define a measure of efficiency on $T$, denoted $K(T)$, construct a $t_{\varepsilon}'$ such that most points in $PSU(2)$ have optimally efficient approximation and we conjecture that $\varepsilon \leq f(t_{\varepsilon})5^{-t_{\varepsilon}/4}$ for a function $f:(0,\infty)\to (1,\infty)$ satisfying: \begin{equation*} \lim_{ t_{\varepsilon} \to \infty} log(f(t_{\varepsilon}))/t_{\varepsilon} \end{equation*} exists with value $0$. Our conjecture can be formulated to mean the following: Let $\nu(5^{t_{\varepsilon}})$ denote the set of integer solutions of the quadratic form: $x_1^2+x_2^2+x_3^2+x_4^2=5^{t_{\varepsilon}}$. Let $M\equiv M_{S^3}(\mathcal{N})$ denote the covering radius of the points $\mathcal{N}=\nu(5^{t_{\varepsilon}})\cup\nu(5^{t_{\varepsilon}-1})$ on the sphere $S^{3}$ in $\mathbb{R}^{4}$. Then $M \sim f(\log N)N^{-1/4}$. Here $N\equiv N(\varepsilon)=6\cdot5^{t_{\varepsilon}}-2$. This is a weaker conjecture than that proposed in [2], namely: $M\geq N^{{-1/4}+o(1)}$. We prove that this conjecture implies that $K(T)=\dfrac{4}{3}$. This answers a question of Sarnak in [8].

•Jun 18, 2015•0 citations

Computation

Jochen Rau

This chapter introduces the basic building blocks of quantum computing and a variety of specific algorithms. It begins with a brief review of classical computing and discusses how its key elements – bits, gates, circuits – carry over to the quantum realm. It highlights crucial differences to the classical case, such as the impossibility of copying a qubit. The quantum circuit model is shown to be universal, and a peculiar variant of quantum computing, based on measurements only, is illustrated. That a quantum computer can perform some calculations more efficiently than a classical computer, at least in principle, is exemplified with the Deutsch-Jozsa algorithm. Other examples covered in this chapter are the variational quantum eigensolver, which can be applied to the study of molecules and classical optimization problems; quantum simulation; and entanglement-assisted metrology.

Oxford University Press eBooks•May 27, 2021•0 citations

Quantum computation

This chapter introduces the basic principles of quantum computation. We shall adhere to the quantum circuit model of computation, with which it is easy to work and which is close to physical implementations. We shall not discuss the more abstract quantum Turing machine model, which, however, has been shown to be equivalent to the circuit model. The elementary unit of quantum information and the basic building block of quantum computation is the qubit, a two-level quantum system that can be prepared, manipulated and measured in a controlled way. A quantum computer can be seen as a collection of n qubits and therefore its wave function resides in a 2 n -dimensional complex Hilbert space. As far as coupling to the environment may be neglected, its evolution in time is unitary and governed by the Schrödinger equation. A quantum computation is composed of three basic steps: preparation of the input state, implementation of the desired unitary transformation acting on this state and measurement of the output state. The output of the measurement process is inherently probabilistic and the probabilities of the different possible outputs are set by the basic postulates of quantum mechanics. Therefore, in a quantum algorithm we must, in general, repeat several times the algorithm to obtain the correct solution of our problem with probability as close to one as desired. In this sense, quantum algorithms are analogous to classical probabilistic algorithms. However, the superposition principle and quantum entanglement open up new possibilities for computation. Quantum computers are potentially more powerful than classical (deterministic or probabilistic) computers due to quantum interference and entanglement. We show that, analogously to classical computation, there exists a small set of gates that are universal, that is, any unitary transformation can be decomposed into a sequence of these gates. We then discuss the implementation of the basic Boolean functions and arithmetic operations on a quantum computer.

WORLD SCIENTIFIC eBooks•Dec 1, 2018•0 citations

Introduction to Quantum Computing

Walid E. Gomaa

This presentation provides a comprehensive overview of the foundational principles of quantum computation. It begins by contrasting classical and quantum information, highlighting how quantum bits (qubits) leverage superposition, entanglement, and interference to process information in ways that surpass classical limits. The document explains the four postulates of quantum mechanics: state space (qubits as unit vectors in a Hilbert space), time evolution (via unitary operators), measurement (probabilistic collapse of the state), and composite systems (tensor products of subsystems). Key concepts such as the Bloch sphere representation, quantum gates (e.g., Hadamard, CNOT, Pauli gates), and quantum circuits are discussed, illustrating how quantum operations manipulate qubit states. The presentation also covers quantum evolution, the gate model for computation, and the universality of certain gate sets, emphasizing the potential for quantum parallelism and the transformative impact of quantum computing on fields like cryptography and optimization.

•Nov 11, 2025•0 citations
A central question in quantum computing is how elements of SU (2) the collection of 2 × 2 unitary matrices with determinant can be approximated by a small set of “generators”. A classical bit is the basic unit of information used in classical computing, which has the states 1 or 0. Quantum computing extends this concept using the notion of quantum bits. For the construction of quantum computers, a finite base set of quantum gates must be chosen so that they generate SU (2). In this chapter, the goal is to construct a universal gate set T * in SU (2) that efficiently approximates all of PSU (2) (the equivalence classes of SU (2) under multiplication by -1) using a natural and simple notion of distance. Covering exponents constructed are used to measure the efficiency of a gate set in approximating every element of SU (2).
A 1-qubit gate is defined as an element of the unitary group U(2)U(2)U(2), the group of complex valued matrices whose conjugate transposes equal their inverses. In quantum computing, it is important to be able to find good approximations of 1-qubit gates by using a dense group generated by a universal subset of the projective special unitary group G=PSU(2)G=PSU(2)G=PSU(2). Here, PSU(2)PSU(2)PSU(2) is the group formed by taking all elements of U(2)U(2)U(2) with determinant 1 and taking the quotient of this subgroup by the group {I,−I}\{I,-I\}{I,−I} where III is the identity matrix. In this http URL [1], Sarnak recently studied this problem motivated by developing a continued fraction type algorithm for this problem. The continued fraction algorithm is the fastest known algorithm to approximate real numbers by the dense subset of rational numbers. In this report, we study the efficiency of the approximation of GGG by using a dense group generated by a universal subset of GGG. The measure of the efficiency K(g)K(g)K(g) of an arbitrary universal subset ggg is defined in [1] and satisfies K(g)⩾1K(g)\geqslant 1K(g)⩾1. ggg is more efficient when K(g)K(g)K(g) is closer to 111. We address some open problems posed by Sarnak in [1]. This report forms the basis of the shorter preprint [LD].
Quantum computation is of current ubiquitous interest in physics, computer science, and the public interest. In the not-so-distant future, quantum computers will be relatively common pieces of research equipment. Eventually, one can expect an actively quantum computer to be a common feature of life. In this work, I study the approximation efficiency of several common universal quantum gate sets at short sequence lengths using an implementation of the Solovay-Kitaev algorithm. I begin by developing from almost nothing the relevant formal mathematics to rigorously describe what one means by the terms universal gate set and covering efficiency. I then describe some interesting results on the asymptotic covering properties of certain classes of universal gate sets and discuss the theorem which the Solovay-Kitaev algorithm is based on. Moving from mathematical introduction to experimental method, I then describe how sets will be compared. I use the commonly studied sets H+T, Pauli+V, V, and Clifford+T to determine which is the most efficient at approximating randomly generated unitaries. By doing so, we get an understanding of how well each set would perform in the context of a general quantum computer processor. This was accomplished by using the same implementation of the Solovay-Kitaev algorithm throughout, with roughly equal-sized preprocessed libraries formed from each gate set, over approximations for 10,000 randomly generated unitary matrices at algorithm depth n=5. Ultimately, the Pauli+V and V sets were the most efficient and had similar performance qualities. On average the Pauli+V set produced approximations of length 15,491 and accuracy 0.0002686. The V basis produced approximations of average sequence length 16,403 and accuracy 0.0001465. This performance is about equal given this particular implementation of the Solovay-Kitaev algorithm. We conclude that this result is somewhat surprising as the general behavior and efficiency of these particular choices of gate set are expected to be similar. It is possible though that the asymptotic efficiencies of these gate sets vary by a relatively wide margin and this has effected the experiment. It is also possible that some aspect of a naive implementation of the Solovay-Kitaev algorithm resulted in the Hadamard gate based sets performing more poorly than the V basis sets overall. Due to constraints on computational power, this result could also be limited to this particular accuracy regime and could even out as tolerance 𝜀 is taken to be arbitrarily small. Further possibilities of this result as well as further work are then discussed.
A 1-qubit gate is defined as an element of the unitary group U(2)U(2)U(2). The problem of finding good approximations of arbitrary 1-qubit gates is identical to that of finding a dense group generated by a universal subset of PSU(2)PSU(2)PSU(2) to approximate an arbitrary element of U(2)U(2)U(2). Notably, this problem has been recently studied by Sarnak in [8]. We will work with a universal gate set TTT, a subset of SU(2)SU(2)SU(2) such that the group generated by the elements of TTT is dense in SU(2)SU(2)SU(2). For an arbitrary ε>0\varepsilon > 0ε>0, we define tεt_{\varepsilon}tε​ as the minimum reduced word length such that every point of SU(2)SU(2)SU(2) lies within a ball of radius ε\varepsilonε centered at the points in the dense subgroup generated by TTT. We define a measure of efficiency on TTT, denoted K(T)K(T)K(T), construct a tε′t_{\varepsilon}'tε′​ such that most points in PSU(2)PSU(2)PSU(2) have optimally efficient approximation and we conjecture that ε≤f(tε)5−tε/4\varepsilon \leq f(t_{\varepsilon})5^{-t_{\varepsilon}/4}ε≤f(tε​)5−tε​/4 for a function f:(0,∞)→(1,∞)f:(0,\infty)\to (1,\infty)f:(0,∞)→(1,∞) satisfying: \begin{equation*} \lim_{ t_{\varepsilon} \to \infty} log(f(t_{\varepsilon}))/t_{\varepsilon} \end{equation*} exists with value 000. Our conjecture can be formulated to mean the following: Let ν(5tε)\nu(5^{t_{\varepsilon}})ν(5tε​) denote the set of integer solutions of the quadratic form: x12+x22+x32+x42=5tεx_1^2+x_2^2+x_3^2+x_4^2=5^{t_{\varepsilon}}x12​+x22​+x32​+x42​=5tε​. Let M≡MS3(N)M\equiv M_{S^3}(\mathcal{N})M≡MS3​(N) denote the covering radius of the points N=ν(5tε)∪ν(5tε−1)\mathcal{N}=\nu(5^{t_{\varepsilon}})\cup\nu(5^{t_{\varepsilon}-1})N=ν(5tε​)∪ν(5tε​−1) on the sphere S3S^{3}S3 in R4\mathbb{R}^{4}R4. Then M∼f(log⁡N)N−1/4M \sim f(\log N)N^{-1/4}M∼f(logN)N−1/4. Here N≡N(ε)=6⋅5tε−2N\equiv N(\varepsilon)=6\cdot5^{t_{\varepsilon}}-2N≡N(ε)=6⋅5tε​−2. This is a weaker conjecture than that proposed in [2], namely: M≥N−1/4+o(1)M\geq N^{{-1/4}+o(1)}M≥N−1/4+o(1). We prove that this conjecture implies that K(T)=43K(T)=\dfrac{4}{3}K(T)=34​. This answers a question of Sarnak in [8].
This chapter introduces the basic building blocks of quantum computing and a variety of specific algorithms. It begins with a brief review of classical computing and discusses how its key elements – bits, gates, circuits – carry over to the quantum realm. It highlights crucial differences to the classical case, such as the impossibility of copying a qubit. The quantum circuit model is shown to be universal, and a peculiar variant of quantum computing, based on measurements only, is illustrated. That a quantum computer can perform some calculations more efficiently than a classical computer, at least in principle, is exemplified with the Deutsch-Jozsa algorithm. Other examples covered in this chapter are the variational quantum eigensolver, which can be applied to the study of molecules and classical optimization problems; quantum simulation; and entanglement-assisted metrology.
This chapter introduces the basic principles of quantum computation. We shall adhere to the quantum circuit model of computation, with which it is easy to work and which is close to physical implementations. We shall not discuss the more abstract quantum Turing machine model, which, however, has been shown to be equivalent to the circuit model. The elementary unit of quantum information and the basic building block of quantum computation is the qubit, a two-level quantum system that can be prepared, manipulated and measured in a controlled way. A quantum computer can be seen as a collection of n qubits and therefore its wave function resides in a 2 n -dimensional complex Hilbert space. As far as coupling to the environment may be neglected, its evolution in time is unitary and governed by the Schrödinger equation. A quantum computation is composed of three basic steps: preparation of the input state, implementation of the desired unitary transformation acting on this state and measurement of the output state. The output of the measurement process is inherently probabilistic and the probabilities of the different possible outputs are set by the basic postulates of quantum mechanics. Therefore, in a quantum algorithm we must, in general, repeat several times the algorithm to obtain the correct solution of our problem with probability as close to one as desired. In this sense, quantum algorithms are analogous to classical probabilistic algorithms. However, the superposition principle and quantum entanglement open up new possibilities for computation. Quantum computers are potentially more powerful than classical (deterministic or probabilistic) computers due to quantum interference and entanglement. We show that, analogously to classical computation, there exists a small set of gates that are universal, that is, any unitary transformation can be decomposed into a sequence of these gates. We then discuss the implementation of the basic Boolean functions and arithmetic operations on a quantum computer.
This presentation provides a comprehensive overview of the foundational principles of quantum computation. It begins by contrasting classical and quantum information, highlighting how quantum bits (qubits) leverage superposition, entanglement, and interference to process information in ways that surpass classical limits. The document explains the four postulates of quantum mechanics: state space (qubits as unit vectors in a Hilbert space), time evolution (via unitary operators), measurement (probabilistic collapse of the state), and composite systems (tensor products of subsystems). Key concepts such as the Bloch sphere representation, quantum gates (e.g., Hadamard, CNOT, Pauli gates), and quantum circuits are discussed, illustrating how quantum operations manipulate qubit states. The presentation also covers quantum evolution, the gate model for computation, and the universality of certain gate sets, emphasizing the potential for quantum parallelism and the transformative impact of quantum computing on fields like cryptography and optimization.