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

Parameters of pseudorandom quantum circuits

Yaakov S. Weinstein, Winton Brown, Lorenza Viola

Published Nov 21, 2008• 32 citations
arXivHTMLPDF

Abstract

Pseudorandom circuits generate quantum states and unitary operators which are approximately distributed according to the unitarily invariant Haar measure. We explore how several design parameters affect the efficiency of pseudorandom circuits, with the goal of identifying relevant tradeoffs and optimizing convergence. The parameters we explore include the choice of single- and two-qubit gates, the topology of the underlying physical qubit architecture, the probabilistic application of two-qubit gates, as well as circuit size, initialization, and the effect of control constraints. Building on the equivalence between pseudorandom circuits and approximate $t$-designs, a Markov matrix approach is employed to analyze asymptotic convergence properties of pseudorandom second-order moments to a 2-design. Quantitative results on the convergence rate as a function of the circuit size are presented for qubit topologies with a sufficient degree of symmetry. Our results may be useful towards optimizing the efficiency of random state and operator generation.

DOI
10.1103/physreva.78.052332

Related papers

Quantum pseudorandomness from cluster-state quantum computation

Winton Brown, Yaakov S. Weinstein, Lorenza Viola

We show how to efficiently generate pseudorandom states suitable for quantum information processing via cluster-state quantum computation. By reformulating pseudorandom algorithms in the cluster-state picture, we identify a strategy for optimizing pseudorandom circuits by properly choosing single-qubit rotations. A Markov chain analysis provides the tool for analyzing convergence rates to the Haar measure and finding the optimal single-qubit gate distribution. Our results may be viewed as an alternative construction of approximate unitary $2$-designs.

arXiv:0802.2675•Physical Review A•Apr 30, 2008•23 citations

Convergence conditions for random quantum circuits

Joseph Emerson, Etera R. Livine, Seth Lloyd

Efficient methods for generating pseudorandomly distributed unitary operators are needed for the practical application of Haar-distributed random operators in quantum communication and noise estimation protocols. We develop a theoretical framework for analyzing pseudorandom ensembles generated through a random circuit composition. We prove that the measure over random circuits converges exponentially (with increasing circuit length) to the uniform (Haar) measure on the unitary group, though the rate for uniform convergence must decrease exponentially with the number of qubits. We describe how the rate of convergence for test functions associated with specific randomization tasks leads to weaker convergence conditions that may allow efficient random circuit constructions.

arXiv:quant-ph/0503210•Physical Review A•Dec 2, 2005•94 citations

Convergence efficiency of quantum gates and circuits

Linghang Kong, Zimu Li, Zi-Wen Liu

We consider quantum circuit models where the gates are drawn from arbitrary gate ensembles given by probabilistic distributions over certain gate sets and circuit architectures, which we call stochastic quantum circuits. Of main interest in this work is the speed of convergence of stochastic circuits with different gate ensembles and circuit architectures to unitary t-designs. A key motivation for this theory is the varying preference for different gates and circuit architectures in different practical scenarios. In particular, it provides a versatile framework for devising efficient circuits for implementing $t$-designs and relevant applications including random circuit and scrambling experiments, as well as benchmarking the performance of gates and circuit architectures. We examine various important settings in depth. A key aspect of our study is an "ironed gadget" model, which allows us to systematically evaluate and compare the convergence efficiency of entangling gates and circuit architectures. Particularly notable results include i) gadgets of two-qubit gates with KAK coefficients $\left(\fracπ{4}-\frac{1}{8}\arccos(\frac{1}{5}),\fracπ{8},\frac{1}{8}\arccos(\frac{1}{5})\right)$ (which we call $χ$ gates) directly form exact 2- and 3-designs; ii) the iSWAP gate family achieves the best efficiency for convergence to 2-designs under mild conjectures with numerical evidence, even outperforming the Haar-random gate, for generic many-body circuits; iii) iSWAP + complete graph achieve the best efficiency for convergence to 2-designs among all graph circuits. A variety of numerical results are provided to complement our analysis. We also derive robustness guarantees for our analysis against gate perturbations. Additionally, we provide cursory analysis on gates with higher locality and found that the Margolus gate outperforms various other well-known gates.

arXiv:2411.04898•Nov 7, 2024•0 citations

Pseudorandom circuits from Clifford-plus- T gates

Yaakov S. Weinstein

We explore the implementation of pseudorandom single-qubit rotations and multiqubit pseudorandom circuits constructed only from Clifford gates and the $T$ gate, a phase rotation of $\ensuremath{\pi}/4$. Such a gate set would be appropriate for computations performed in a fault tolerant setting. For single-qubit rotations the distribution of parameters found for unitaries constructed from Clifford plus $T$ quickly approaches that of random rotations and requires significantly fewer gates than the construction of arbitrary single-qubit rotations. For Clifford-plus-$T$ pseudorandom circuits we find an exponential convergence to a random matrix element distribution and a Gaussian convergence to the higher-order moments of the matrix element distribution. In addition, the nearest-neighbor eigenangle statistics distribution almost immediately converges to that of random unitary matrices. All of these convergence rates are found to be insensitive to the number of qubits.

arXiv:1309.3943•Physical Review A•Dec 2, 2013•4 citations

Quantum State Designs from Minimally Random Quantum Circuits

Jonathon Riddell, Katja Klobas, Bruno Bertini

Random many-body states and matrices are both a useful tool to model certain physical systems and an important asset for quantum computation. Realizing them, however, generally requires an exponential (in system size) amount of resources. Recent research has presented a way out by showing that one can generate random states and matrices, or more precisely a controlled approximation of them, by applying a quantum circuit built in terms of few-body unitary gates. Most of this research has been focussed on the case of quantum circuits composed by fully random unitary gates. Here we consider what happens for circuits that, instead, involve a minimal degree of randomness. Specifically, we concentrate on two different settings: (a) brickwork quantum circuits with a single one-qudit random matrix at a boundary; (b) brickwork quantum circuits with fixed interactions but random one-qudit gates everywhere. We show that, for any given initial state, (a) and (b) produce a distribution of states approaching the Haar distribution in the limit of large circuit depth. More precisely, we show that the moments of the distribution produced by our circuits can approximate the ones of the Haar distribution in a depth proportional to the system size. Interestingly we find that in both Cases (a) and (b) the relaxation to the Haar distribution occurs in two steps—this is in contrast with what happens in fully random circuits. Moreover, we show that choosing appropriately the fixed interactions, for example taking the local gate to be a dual-unitary gate with high enough entangling power, minimally random circuits produce a Haar random distribution more rapidly than fully random circuits. In particular, dual-unitary circuits with maximal entangling power—i.e. perfect tensors—appear to provide the optimal quantum state design preparation for any design number. Our results also suggest that the minimally random settings (a) and (b) give an optimal framework to prepare unitary designs, i.e., random unitary matrices.

arXiv:2503.05698•PRX Quantum•Jun 8, 2026•0 citations

Pseudo-randomness and Learning in Quantum Computation

Richard A. Low

This thesis discusses the young fields of quantum pseudo-randomness and quantum learning algorithms. We present techniques for derandomising algorithms to decrease randomness resource requirements and improve efficiency. One key object in doing this is a k-design, which is a distribution on the unitary group whose kth moments match those of the unitarily invariant Haar measure. We show that for a natural model of a random quantum circuit, the distribution of random circuits quickly converges to a 2-design. We then present an efficient unitary k-design construction for any k, provided the number of qubits n satisfies k = O(n/log n). In doing this, we provide an efficient construction of a quantum tensor product expander, which is a generalisation of a quantum expander which in turn generalises classical expanders. We then discuss applications of k-designs. We show that they can be used to improve the efficiency of many existing algorithms and protocols and also find new applications to derandomising large deviation bounds. In particular, we show that many large deviation bound results for Haar random unitaries carry over to k-designs for k = poly(n). In the second part of the thesis, we present some learning and testing algorithms for the Clifford group. We find an optimal algorithm for identifying an unknown Clifford operation. We also give an algorithm to test if an unknown operation is close to a Clifford or far from every Clifford.

arXiv:1006.5227•Jun 27, 2010•34 citations
Pseudorandom circuits generate quantum states and unitary operators which are approximately distributed according to the unitarily invariant Haar measure. We explore how several design parameters affect the efficiency of pseudorandom circuits, with the goal of identifying relevant tradeoffs and optimizing convergence. The parameters we explore include the choice of single- and two-qubit gates, the topology of the underlying physical qubit architecture, the probabilistic application of two-qubit gates, as well as circuit size, initialization, and the effect of control constraints. Building on the equivalence between pseudorandom circuits and approximate ttt-designs, a Markov matrix approach is employed to analyze asymptotic convergence properties of pseudorandom second-order moments to a 2-design. Quantitative results on the convergence rate as a function of the circuit size are presented for qubit topologies with a sufficient degree of symmetry. Our results may be useful towards optimizing the efficiency of random state and operator generation.
We show how to efficiently generate pseudorandom states suitable for quantum information processing via cluster-state quantum computation. By reformulating pseudorandom algorithms in the cluster-state picture, we identify a strategy for optimizing pseudorandom circuits by properly choosing single-qubit rotations. A Markov chain analysis provides the tool for analyzing convergence rates to the Haar measure and finding the optimal single-qubit gate distribution. Our results may be viewed as an alternative construction of approximate unitary 222-designs.
Efficient methods for generating pseudorandomly distributed unitary operators are needed for the practical application of Haar-distributed random operators in quantum communication and noise estimation protocols. We develop a theoretical framework for analyzing pseudorandom ensembles generated through a random circuit composition. We prove that the measure over random circuits converges exponentially (with increasing circuit length) to the uniform (Haar) measure on the unitary group, though the rate for uniform convergence must decrease exponentially with the number of qubits. We describe how the rate of convergence for test functions associated with specific randomization tasks leads to weaker convergence conditions that may allow efficient random circuit constructions.
We consider quantum circuit models where the gates are drawn from arbitrary gate ensembles given by probabilistic distributions over certain gate sets and circuit architectures, which we call stochastic quantum circuits. Of main interest in this work is the speed of convergence of stochastic circuits with different gate ensembles and circuit architectures to unitary t-designs. A key motivation for this theory is the varying preference for different gates and circuit architectures in different practical scenarios. In particular, it provides a versatile framework for devising efficient circuits for implementing ttt-designs and relevant applications including random circuit and scrambling experiments, as well as benchmarking the performance of gates and circuit architectures. We examine various important settings in depth. A key aspect of our study is an "ironed gadget" model, which allows us to systematically evaluate and compare the convergence efficiency of entangling gates and circuit architectures. Particularly notable results include i) gadgets of two-qubit gates with KAK coefficients (π4−18arccos⁡(15),π8,18arccos⁡(15))\left(\fracπ{4}-\frac{1}{8}\arccos(\frac{1}{5}),\fracπ{8},\frac{1}{8}\arccos(\frac{1}{5})\right)(4π​−81​arccos(51​),8π​,81​arccos(51​)) (which we call χχχ gates) directly form exact 2- and 3-designs; ii) the iSWAP gate family achieves the best efficiency for convergence to 2-designs under mild conjectures with numerical evidence, even outperforming the Haar-random gate, for generic many-body circuits; iii) iSWAP + complete graph achieve the best efficiency for convergence to 2-designs among all graph circuits. A variety of numerical results are provided to complement our analysis. We also derive robustness guarantees for our analysis against gate perturbations. Additionally, we provide cursory analysis on gates with higher locality and found that the Margolus gate outperforms various other well-known gates.
We explore the implementation of pseudorandom single-qubit rotations and multiqubit pseudorandom circuits constructed only from Clifford gates and the TTT gate, a phase rotation of $\ensuremath{\pi}/4$. Such a gate set would be appropriate for computations performed in a fault tolerant setting. For single-qubit rotations the distribution of parameters found for unitaries constructed from Clifford plus TTT quickly approaches that of random rotations and requires significantly fewer gates than the construction of arbitrary single-qubit rotations. For Clifford-plus-TTT pseudorandom circuits we find an exponential convergence to a random matrix element distribution and a Gaussian convergence to the higher-order moments of the matrix element distribution. In addition, the nearest-neighbor eigenangle statistics distribution almost immediately converges to that of random unitary matrices. All of these convergence rates are found to be insensitive to the number of qubits.
Random many-body states and matrices are both a useful tool to model certain physical systems and an important asset for quantum computation. Realizing them, however, generally requires an exponential (in system size) amount of resources. Recent research has presented a way out by showing that one can generate random states and matrices, or more precisely a controlled approximation of them, by applying a quantum circuit built in terms of few-body unitary gates. Most of this research has been focussed on the case of quantum circuits composed by fully random unitary gates. Here we consider what happens for circuits that, instead, involve a minimal degree of randomness. Specifically, we concentrate on two different settings: (a) brickwork quantum circuits with a single one-qudit random matrix at a boundary; (b) brickwork quantum circuits with fixed interactions but random one-qudit gates everywhere. We show that, for any given initial state, (a) and (b) produce a distribution of states approaching the Haar distribution in the limit of large circuit depth. More precisely, we show that the moments of the distribution produced by our circuits can approximate the ones of the Haar distribution in a depth proportional to the system size. Interestingly we find that in both Cases (a) and (b) the relaxation to the Haar distribution occurs in two steps—this is in contrast with what happens in fully random circuits. Moreover, we show that choosing appropriately the fixed interactions, for example taking the local gate to be a dual-unitary gate with high enough entangling power, minimally random circuits produce a Haar random distribution more rapidly than fully random circuits. In particular, dual-unitary circuits with maximal entangling power—i.e. perfect tensors—appear to provide the optimal quantum state design preparation for any design number. Our results also suggest that the minimally random settings (a) and (b) give an optimal framework to prepare unitary designs, i.e., random unitary matrices.
This thesis discusses the young fields of quantum pseudo-randomness and quantum learning algorithms. We present techniques for derandomising algorithms to decrease randomness resource requirements and improve efficiency. One key object in doing this is a k-design, which is a distribution on the unitary group whose kth moments match those of the unitarily invariant Haar measure. We show that for a natural model of a random quantum circuit, the distribution of random circuits quickly converges to a 2-design. We then present an efficient unitary k-design construction for any k, provided the number of qubits n satisfies k = O(n/log n). In doing this, we provide an efficient construction of a quantum tensor product expander, which is a generalisation of a quantum expander which in turn generalises classical expanders. We then discuss applications of k-designs. We show that they can be used to improve the efficiency of many existing algorithms and protocols and also find new applications to derandomising large deviation bounds. In particular, we show that many large deviation bound results for Haar random unitaries carry over to k-designs for k = poly(n). In the second part of the thesis, we present some learning and testing algorithms for the Clifford group. We find an optimal algorithm for identifying an unknown Clifford operation. We also give an algorithm to test if an unknown operation is close to a Clifford or far from every Clifford.