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

Random Quantum Circuits and Pseudo-Random Unitary Operators

Joseph Emerson, Etera R. Livine, Seth Lloyd

Published Mar 28, 2005• 4 citations
OpenAlex

Abstract

Efficient methods for generating pseudo-randomly 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 pseudo-random 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 and describe how the rate of convergence may be calculated for specific applications.

Related papers

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

Pseudo-Random Operators: Theory and Applications

Joseph Emerson

Pseudo‐random operators consist of sets of operators that exhibit important statistical features of uniformly distributed operators although their parametrization and generation requires exponentially fewer resources. Pseudo‐random operators can be applied for quantum communication tasks such as data‐hiding and super‐dense coding of quantum states, and enable efficient stochastic methods for noise estimation on prototype quantum processors. This paper summarizes published work by Emerson et al. [Science 302:2098 (2003)] demonstrating a random circuit method for the implementation of pseudo‐random unitary operators on a quantum processor and some more recent related results.

AIP conference proceedings•Jan 1, 2004•3 citations

Random Processes over the Unitary Group

Emilio Onorati

According to one of the fundamental axioms of quantum mechanics, unitary operators rule the evolution of any quantum system; it is thus of prominent importance to investigate the corresponding group and discover its properties. Random processes over the unitary group have indeed a wide range of applications in the context of quantum information; in particular, they are involved in the construction of peculiar distributions called unitary designs which mimic the uniform Haar measure by matching its moments and are thus deeply connected to the description of phenomena such as quantum tomography, equilibration, thermalization, encryption and scrambling. Previous approaches have shown that unitary designs are efficiently approximated by random quantum circuits with local unitary operators. Moreover, these circuits are used to characterize the precision of experimental implementations of unitary gates via randomized benchmarking protocols and to rapidly decouple a system from the environment. The main novel contribution of this work is to extend these mixing properties to a continuous-time framework, namely, Brownian motion over the unitary group induced by stochastic local Hamiltonians. In order to achieve these new results, on the one hand we move to a representation theoretic formulation and make use of its tools to establish the gap of local generators linked to the moments of the distribution induced by the diffusion process; from this we then derive an expression for the length of time it takes to ensure convergence toward the moments of the Haar measure. On the other hand we project the stochastic evolution onto a random walk on Pauli matrices and tie this description to the analogous one for random quantum circuits to achieve decoupling in a run time scaling almost linearly with respect to the system size. In addition to providing a unifying framework for random processes over the unitary group, we hence aim at presenting new mathematical results and techniques for quantum information. We furthermore discuss applications to black holes dynamics in the perspective of the information paradox. As an additional novel result not related to Brownian motion, we propose a randomized benchmarking protocol exploiting the symmetry of the gate whose accuracy has to be estimated, in order to overcome current shortcomings afflicting the known schemes. We again rely on representation theory to reduce the computational effort and the amount of employed quantum resources.

•Jan 1, 2019•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

Random quantum circuits are approximate unitary t -designs in depth O(nt5+o(1))

Jonas Haferkamp

The applications of random quantum circuits range from quantum computing and quantum many-body systems to the physics of black holes. Many of these applications are related to the generation of quantum pseudorandomness: Random quantum circuits are known to approximate unitary t -designs. Unitary t -designs are probability distributions that mimic Haar randomness up to t th moments. In a seminal paper, Brandão, Harrow and Horodecki prove that random quantum circuits on qubits in a brickwork architecture of depth O(nt10.5) are approximate unitary t -designs. In this work, we revisit this argument, which lower bounds the spectral gap of moment operators for local random quantum circuits by Ω(n−1t−9.5) . We improve this lower bound to Ω(n−1t−4−o(1)) , where the o(1) term goes to 0 as t→∞ . A direct consequence of this scaling is that random quantum circuits generate approximate unitary t -designs in depth O(nt5+o(1)) . Our techniques involve Gao's quantum union bound and the unreasonable effectiveness of the Clifford group. As an auxiliary result, we prove fast convergence to the Haar measure for random Clifford unitaries interleaved with Haar random single qubit unitaries.

arXiv:2203.16571•Quantum•Sep 8, 2022•81 citations

Pseudo-Random Unitary Operators for Quantum Information Processing

Joseph Emerson, Yaakov S. Weinstein, Marcos Saraceno +2 more

In close analogy to the fundamental role of random numbers in classical information theory, random operators are a basic component of quantum information theory. Unfortunately, the implementation of random unitary operators on a quantum processor is exponentially hard. Here we introduce a method for generating pseudo-random unitary operators that can reproduce those statistical properties of random unitary operators most relevant to quantum information tasks. This method requires exponentially fewer resources, and hence enables the practical application of random unitary operators in quantum communication and information processing protocols. Using a nuclear magnetic resonance quantum processor, we were able to realize pseudorandom unitary operators that reproduce the expected random distribution of matrix elements.

arXiv:quant-ph/0410087•Science•Dec 18, 2003•234 citations
Efficient methods for generating pseudo-randomly 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 pseudo-random 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 and describe how the rate of convergence may be calculated for specific applications.
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.
Pseudo‐random operators consist of sets of operators that exhibit important statistical features of uniformly distributed operators although their parametrization and generation requires exponentially fewer resources. Pseudo‐random operators can be applied for quantum communication tasks such as data‐hiding and super‐dense coding of quantum states, and enable efficient stochastic methods for noise estimation on prototype quantum processors. This paper summarizes published work by Emerson et al. [Science 302:2098 (2003)] demonstrating a random circuit method for the implementation of pseudo‐random unitary operators on a quantum processor and some more recent related results.
According to one of the fundamental axioms of quantum mechanics, unitary operators rule the evolution of any quantum system; it is thus of prominent importance to investigate the corresponding group and discover its properties. Random processes over the unitary group have indeed a wide range of applications in the context of quantum information; in particular, they are involved in the construction of peculiar distributions called unitary designs which mimic the uniform Haar measure by matching its moments and are thus deeply connected to the description of phenomena such as quantum tomography, equilibration, thermalization, encryption and scrambling. Previous approaches have shown that unitary designs are efficiently approximated by random quantum circuits with local unitary operators. Moreover, these circuits are used to characterize the precision of experimental implementations of unitary gates via randomized benchmarking protocols and to rapidly decouple a system from the environment. The main novel contribution of this work is to extend these mixing properties to a continuous-time framework, namely, Brownian motion over the unitary group induced by stochastic local Hamiltonians. In order to achieve these new results, on the one hand we move to a representation theoretic formulation and make use of its tools to establish the gap of local generators linked to the moments of the distribution induced by the diffusion process; from this we then derive an expression for the length of time it takes to ensure convergence toward the moments of the Haar measure. On the other hand we project the stochastic evolution onto a random walk on Pauli matrices and tie this description to the analogous one for random quantum circuits to achieve decoupling in a run time scaling almost linearly with respect to the system size. In addition to providing a unifying framework for random processes over the unitary group, we hence aim at presenting new mathematical results and techniques for quantum information. We furthermore discuss applications to black holes dynamics in the perspective of the information paradox. As an additional novel result not related to Brownian motion, we propose a randomized benchmarking protocol exploiting the symmetry of the gate whose accuracy has to be estimated, in order to overcome current shortcomings afflicting the known schemes. We again rely on representation theory to reduce the computational effort and the amount of employed quantum resources.
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.
The applications of random quantum circuits range from quantum computing and quantum many-body systems to the physics of black holes. Many of these applications are related to the generation of quantum pseudorandomness: Random quantum circuits are known to approximate unitary t -designs. Unitary t -designs are probability distributions that mimic Haar randomness up to t th moments. In a seminal paper, Brandão, Harrow and Horodecki prove that random quantum circuits on qubits in a brickwork architecture of depth O(nt10.5) are approximate unitary t -designs. In this work, we revisit this argument, which lower bounds the spectral gap of moment operators for local random quantum circuits by Ω(n−1t−9.5) . We improve this lower bound to Ω(n−1t−4−o(1)) , where the o(1) term goes to 0 as t→∞ . A direct consequence of this scaling is that random quantum circuits generate approximate unitary t -designs in depth O(nt5+o(1)) . Our techniques involve Gao's quantum union bound and the unreasonable effectiveness of the Clifford group. As an auxiliary result, we prove fast convergence to the Haar measure for random Clifford unitaries interleaved with Haar random single qubit unitaries.
In close analogy to the fundamental role of random numbers in classical information theory, random operators are a basic component of quantum information theory. Unfortunately, the implementation of random unitary operators on a quantum processor is exponentially hard. Here we introduce a method for generating pseudo-random unitary operators that can reproduce those statistical properties of random unitary operators most relevant to quantum information tasks. This method requires exponentially fewer resources, and hence enables the practical application of random unitary operators in quantum communication and information processing protocols. Using a nuclear magnetic resonance quantum processor, we were able to realize pseudorandom unitary operators that reproduce the expected random distribution of matrix elements.