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

IEEE Information Theory Workshop (ITW)

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

Bhanu Pratap Yadav, Mahdi Bayanifar, Olav Tirkkonen

Published Sep 29, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.1109/itw62417.2025.11240372

Related papers

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

Priyanka Mukhopadhyay

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.

arXiv:2106.07099•Journal of Physics Communications•Nov 1, 2021•6 citations

Distance-Independent Universality of Clifford+T

Jens Palsberg, Keli Huang, Abdullah Almanei

A well-known theorem states that the Clifford+T gate set is universal for quantum computing. The theorem combines approximation using a distance measure on unitary matrices with equality up to global phase. Previous proofs combine these two notions for specific distance measures, but do not identify the properties that govern how they work together. Which properties are sufficient to state and prove the theorem? We answer this question by defining projective distance measures using four axioms. We prove that the universality theorem holds for every distance measure satisfying these axioms. Thus, our formulation of the theorem is independent of any particular choice of distance measure. We show that the Hilbert-Schmidt distance is already a projective distance measure. We also develop a general construction that transforms a large class of distance measures into projective distance measures and apply it to obtain projective versions of the operator-norm distance, the Frobenius distance, and the trace distance. Finally, we formalize the proof of the universality theorem in Lean.

quant-pharXiv:2610.03364•Oct 5, 2026•0 citations

Clifford Approximation of Unitary Matrices

Kalle Volanto, Mahdi Bayanifar, Olav Tirkkonen

Approximating a given unitary operator into a discrete set of gates is of great importance in quantum computation. This problem can be seen as a source quantization problem where the unitary operator is considered as the source. Elements of the Clifford hierarchy can be implemented fault-tolerantly using quantum gate teleportation. This motivates the development of algorithms that quantize unitary operators into Clifford hierarchy elements. In this paper, we present a fast algorithm for approximating arbitrary n-qubit unitaries with Clifford matrices. The algorithm relies on the Clifford transvection decomposition of the Clifford group. The algorithm greedily applies Clifford transvections taking the input unitary closer to the identity matrix. To make the algorithm fast, we take advantage of the Pauli basis representation for unitary matrices to parallelize matrix distance computations. The complexity of the proposed algorithm is O(n 4n). Based on simulation results, the proposed algorithm outperforms the state of the art method.

Globecom•Dec 8, 2025•0 citations

Random unitary circuits with constant spectral gap

Tim Baer, Jeongwan Haah

We prove constant lower bounds for the spectral gap of the following random walks on unitary groups $\mathsf{SU}(2^n)$ on $n$ qubits. (i) Random Pauli Rotation: choose an $n$-qubit Pauli operator $P$ and an angle $θ\in [0,2π)$, both uniformly at random, and apply $e^{\mathrm i θP}$. (ii) Brickwork Random Unitary Circuit: choose $n-1$ unitaries $U_{i}$ uniformly at random from $\mathsf{SU}(4)$ (including central phases of the parent group) independently, and apply $U_{2j-1}$ on two qubits $2j-1, 2j$ and then $U_{2j}$ on two qubits $2j, 2j+1$. Importantly, the gap bounds are independent of $n$ and apply for all finite dimensional unitary representations of $\mathsf{SU}(2^n)$ uniformly. Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary $t$-designs after $\mathcal{O}(nt)$ steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be $\mathcal{O}(2^{cn})$ for some $c < 1$. Our unconditional constant spectral gap removes this restriction. We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal $t$-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for $t=2$.

quant-pharXiv:2607.20919•Jul 24, 2026•0 citations

Improvement of the Gilbert-Varshamov Bound for Linear Codes and Quantum Codes

Chen Yuan, Ruiqi Zhu

The Gilbert--Varshamov (GV) bound is a central benchmark in coding theory, establishing existential guarantees for error-correcting codes and serving as a baseline for both Hamming and quantum fault-tolerant information processing. Despite decades of effort, improving the GV bound is notoriously difficult, and known improvements often rely on technically heavy arguments and do not extend naturally to the quantum setting due to additional self-orthogonality constraints. In this work we develop a concise probabilistic method that yields an improvement over the classical GV bound for $q$-ary linear codes. For relative distance $δ=d/n<1-1/q$, we show that an $[n,k,d]_q$ linear code exists whenever $\frac{q^{k}-1}{q-1}\;<\;\frac{c_δ\sqrt{n}\, q^{n}}{\mathrm{Vol}_q(n,d-1)}$, for positive constant $c_δ$ depending only on $δ$, where $\mathrm{Vol}_q(n,d-1)$ denotes the volume of a $q$-ary Hamming ball. We further adapt this approach to the quantum setting by analyzing symplectic self-orthogonal structures. For $δ<1-1/q^2$, we obtain an improved quantum GV bound: there exists a $q$-ary quantum code $[[n,\,n-k,\,d]]$ provided that $\frac{q^{2n-k}-1}{q-1}<\frac{c_δ\sqrt{n}\cdot q^{2n}}{\sum_{i=0}^{d-1}\binom{n}{i}(q^2-1)^i}$. In particular, our result improves the standard quantum GV bound by an $Ω(\sqrt{n})$ multiplicative factor.

arXiv:2601.18590•Jan 26, 2026•0 citations

Local and Global Risk Bounds for Quantum Entropy Estimation under Projective-Design Measurements

Xinyu Song

We establish a lower bound for estimating the von Neumann entropy from independent outcomes of any fixed rank-one POVM. A rotation-averaged van Trees argument gives a global minimax risk of at least $(d/n)\log^2\{n/(4d)\}$ when $d\ge C$ and $n\ge Cd$, without a projective-design assumption. We also characterize risk on an operator-norm ball of radius $r$ around the maximally mixed state. We allow an approximate second moment: on the trace-zero Hermitian subspace, the measurement frame may differ by $\varepsilon<1$ from the tight projective frame. A clipped estimator based on canonical dual shadows and the complete U-statistic for purity has risk at most $d^3r^2/n+d^4/n^2+d^6r^6$. Lower bounds under the same frame control yield the local minimax rate $d^3r^2/n+d^4/n^2$ when $n\ge Cd^2$ and $r$ lies in an explicit matching range. For every fixed upper bound on $\varepsilon$, approximation changes only the constants, not the powers of $d,n,r$. At the critical radius $r=n^{-1/2}$, the local risk is asymptotically negligible relative to the global risk when $n\log^2(n/d)\gg d^3$. This separation holds for projective 2-designs, including global Clifford measurements in qubit dimensions, and for their uniformly well-conditioned frame approximations. Finite-sample experiments in dimension four illustrate the critical-radius benchmark and the effect of a nonexact frame.

quant-pharXiv:2609.29485•Aug 26, 2026•0 citations
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.
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.
A well-known theorem states that the Clifford+T gate set is universal for quantum computing. The theorem combines approximation using a distance measure on unitary matrices with equality up to global phase. Previous proofs combine these two notions for specific distance measures, but do not identify the properties that govern how they work together. Which properties are sufficient to state and prove the theorem? We answer this question by defining projective distance measures using four axioms. We prove that the universality theorem holds for every distance measure satisfying these axioms. Thus, our formulation of the theorem is independent of any particular choice of distance measure. We show that the Hilbert-Schmidt distance is already a projective distance measure. We also develop a general construction that transforms a large class of distance measures into projective distance measures and apply it to obtain projective versions of the operator-norm distance, the Frobenius distance, and the trace distance. Finally, we formalize the proof of the universality theorem in Lean.
Approximating a given unitary operator into a discrete set of gates is of great importance in quantum computation. This problem can be seen as a source quantization problem where the unitary operator is considered as the source. Elements of the Clifford hierarchy can be implemented fault-tolerantly using quantum gate teleportation. This motivates the development of algorithms that quantize unitary operators into Clifford hierarchy elements. In this paper, we present a fast algorithm for approximating arbitrary n-qubit unitaries with Clifford matrices. The algorithm relies on the Clifford transvection decomposition of the Clifford group. The algorithm greedily applies Clifford transvections taking the input unitary closer to the identity matrix. To make the algorithm fast, we take advantage of the Pauli basis representation for unitary matrices to parallelize matrix distance computations. The complexity of the proposed algorithm is O(n 4n). Based on simulation results, the proposed algorithm outperforms the state of the art method.
We prove constant lower bounds for the spectral gap of the following random walks on unitary groups SU(2n)\mathsf{SU}(2^n)SU(2n) on nnn qubits. (i) Random Pauli Rotation: choose an nnn-qubit Pauli operator PPP and an angle θ∈[0,2π)θ\in [0,2π)θ∈[0,2π), both uniformly at random, and apply eiθPe^{\mathrm i θP}eiθP. (ii) Brickwork Random Unitary Circuit: choose n−1n-1n−1 unitaries UiU_{i}Ui​ uniformly at random from SU(4)\mathsf{SU}(4)SU(4) (including central phases of the parent group) independently, and apply U2j−1U_{2j-1}U2j−1​ on two qubits 2j−1,2j2j-1, 2j2j−1,2j and then U2jU_{2j}U2j​ on two qubits 2j,2j+12j, 2j+12j,2j+1. Importantly, the gap bounds are independent of nnn and apply for all finite dimensional unitary representations of SU(2n)\mathsf{SU}(2^n)SU(2n) uniformly. Our results immediately imply that the Random Pauli Rotation and Brickwork Random Unitary Circuit converge to approximate unitary ttt-designs after O(nt)\mathcal{O}(nt)O(nt) steps. As a consequence, we improve implications for the complexity growth of random unitary circuits as a function of the depth. The existing argument can be applied almost verbatim, but previously the depth had to be O(2cn)\mathcal{O}(2^{cn})O(2cn) for some c<1c < 1c<1. Our unconditional constant spectral gap removes this restriction. We prove analogous constant-gap results for orthogonal and Clifford groups; the latter is indispensable for our result on the Brickwork Random Unitary Circuit. The former implies convergence to approximate orthogonal ttt-designs. In this case, the implied mixing time with respect to a constant additive and multiplicative error is optimal (up to an absolute constant factor) for t=2t=2t=2.
The Gilbert--Varshamov (GV) bound is a central benchmark in coding theory, establishing existential guarantees for error-correcting codes and serving as a baseline for both Hamming and quantum fault-tolerant information processing. Despite decades of effort, improving the GV bound is notoriously difficult, and known improvements often rely on technically heavy arguments and do not extend naturally to the quantum setting due to additional self-orthogonality constraints. In this work we develop a concise probabilistic method that yields an improvement over the classical GV bound for qqq-ary linear codes. For relative distance δ=d/n<1−1/qδ=d/n<1-1/qδ=d/n<1−1/q, we show that an [n,k,d]q[n,k,d]_q[n,k,d]q​ linear code exists whenever qk−1q−1  <  cδn qnVolq(n,d−1)\frac{q^{k}-1}{q-1}\;<\;\frac{c_δ\sqrt{n}\, q^{n}}{\mathrm{Vol}_q(n,d-1)}q−1qk−1​<Volq​(n,d−1)cδ​n​qn​, for positive constant cδc_δcδ​ depending only on δδδ, where Volq(n,d−1)\mathrm{Vol}_q(n,d-1)Volq​(n,d−1) denotes the volume of a qqq-ary Hamming ball. We further adapt this approach to the quantum setting by analyzing symplectic self-orthogonal structures. For δ<1−1/q2δ<1-1/q^2δ<1−1/q2, we obtain an improved quantum GV bound: there exists a qqq-ary quantum code [[n, n−k, d]][[n,\,n-k,\,d]][[n,n−k,d]] provided that q2n−k−1q−1<cδn⋅q2n∑i=0d−1(ni)(q2−1)i\frac{q^{2n-k}-1}{q-1}<\frac{c_δ\sqrt{n}\cdot q^{2n}}{\sum_{i=0}^{d-1}\binom{n}{i}(q^2-1)^i}q−1q2n−k−1​<∑i=0d−1​(in​)(q2−1)icδ​n​⋅q2n​. In particular, our result improves the standard quantum GV bound by an Ω(n)Ω(\sqrt{n})Ω(n​) multiplicative factor.
We establish a lower bound for estimating the von Neumann entropy from independent outcomes of any fixed rank-one POVM. A rotation-averaged van Trees argument gives a global minimax risk of at least (d/n)log⁡2{n/(4d)}(d/n)\log^2\{n/(4d)\}(d/n)log2{n/(4d)} when d≥Cd\ge Cd≥C and n≥Cdn\ge Cdn≥Cd, without a projective-design assumption. We also characterize risk on an operator-norm ball of radius rrr around the maximally mixed state. We allow an approximate second moment: on the trace-zero Hermitian subspace, the measurement frame may differ by ε<1\varepsilon<1ε<1 from the tight projective frame. A clipped estimator based on canonical dual shadows and the complete U-statistic for purity has risk at most d3r2/n+d4/n2+d6r6d^3r^2/n+d^4/n^2+d^6r^6d3r2/n+d4/n2+d6r6. Lower bounds under the same frame control yield the local minimax rate d3r2/n+d4/n2d^3r^2/n+d^4/n^2d3r2/n+d4/n2 when n≥Cd2n\ge Cd^2n≥Cd2 and rrr lies in an explicit matching range. For every fixed upper bound on ε\varepsilonε, approximation changes only the constants, not the powers of d,n,rd,n,rd,n,r. At the critical radius r=n−1/2r=n^{-1/2}r=n−1/2, the local risk is asymptotically negligible relative to the global risk when nlog⁡2(n/d)≫d3n\log^2(n/d)\gg d^3nlog2(n/d)≫d3. This separation holds for projective 2-designs, including global Clifford measurements in qubit dimensions, and for their uniformly well-conditioned frame approximations. Finite-sample experiments in dimension four illustrate the critical-radius benchmark and the effect of a nonexact frame.