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:quant-ph/0612168 · Physical Review A

Distribution of interference in random quantum algorithms

Ludovic Arnaud, Daniel Braun

Published Jun 13, 2007• 11 citations
arXivHTMLPDF

Abstract

We study the amount of interference in random quantum algorithms using a recently derived quantitative measure of interference. To this end we introduce two random circuit ensembles composed of random sequences of quantum gates from a universal set, mimicking quantum algorithms in the quantum circuit representation. We show numerically that, concerning the interference distribution and the level spacing distribution, these ensembles converge to the well-known circular unitary ensemble (CUE) for general complex quantum algorithms, and to the Haar orthogonal ensemble (HOE) for real quantum algorithms. We provide exact analytical formulas for the average and typical interference in the circular ensembles, and show that for sufficiently large numbers of qubits a random quantum algorithm uses with probability close to one an amount of interference approximately equal to the dimension of the Hilbert space. As a by-product, we offer a new way of constructing approximate random unitary operators from the Haar measures of CUE or HOE in a high dimensional Hilbert space using universal sets of quantum gates.

DOI
10.1103/physreva.75.062314

Related papers

Stochastic emulation of quantum algorithms

Daniel Braun, Ronny Müller

Abstract Quantum algorithms profit from the interference of quantum states in an exponentially large Hilbert space and the fact that unitary transformations on that Hilbert space can be broken down to universal gates that act only on one or two qubits at the same time. The former aspect renders the direct classical simulation of quantum algorithms difficult. Here we introduce higher-order partial derivatives of a probability distribution of particle positions as a new object that shares these basic properties of quantum mechanical states needed for a quantum algorithm. Discretization of the positions allows one to represent the quantum mechanical state of n bit qubits by 2(n bit + 1) classical stochastic bits. Based on this, we demonstrate many-particle interference and representation of pure entangled quantum states via derivatives of probability distributions and find the universal set of stochastic maps that correspond to the quantum gates in a universal gate set. We prove that the propagation via the stochastic map built from those universal stochastic maps reproduces up to a prefactor exactly the evolution of the quantum mechanical state with the corresponding quantum algorithm, leading to an automated translation of a quantum algorithm to a stochastic classical algorithm. We implement several well-known quantum algorithms, analyse the scaling of the needed number of realizations with the number of qubits, and highlight the role of destructive interference for the cost of the emulation.

arXiv:2109.07777•New Journal of Physics•Jan 13, 2022•1 citation

Distribution of interference in the presence of decoherence

Ludovic Arnaud, Daniel Braun

We study the statistics of quantum interference for completely positive maps. We calculate analytically the mean interference and its second moment for finite-dimensional quantum systems interacting with a simple environment consisting of one or several spins (qudits). The joint propagation of the entire system is taken as unitary with an evolution operator drawn from the circular unitary ensemble (CUE). We show that the mean interference decays with a power law as function of the dimension of the Hilbert space of the environment, with a power that depends on the temperature of the environment.

arXiv:0910.1826•Physical Review A•Dec 22, 2009•0 citations

Efficiency of producing random unitary matrices with quantum circuits

Ludovic Arnaud, Daniel Braun

We study the scaling of the convergence of several statistical properties of a recently introduced random unitary circuit ensemble towards their limits given by the circular unitary ensemble. Our study includes the full distribution of the absolute square of a matrix element, moments of that distribution up to order eight, as well as correlators containing up to 16 matrix elements in a given column of the unitary matrices. Our numerical scaling analysis shows that all of these quantities can be reproduced efficiently, with a number of random gates which scales at most as ${n}_{q}{[\mathrm{ln}({n}_{q}∕ϵ)]}^{\ensuremath{\nu}}$ with the number of qubits ${n}_{q}$ for a given fixed precision $ϵ$ and $\ensuremath{\nu}>0$.

arXiv:0807.0775•Physical Review A•Dec 17, 2008•37 citations

Operator spreading in random unitary circuits with orthogonal/symplectic-invariant gate distributions

Zhiyang Tan, Piet W. Brouwer

We investigate operator spreading in random quantum circuits with gates drawn from orthogonal-invariant or symplectic-invariant ensembles, revealing several key distinctions from the well-studied unitary-invariant case. We find that the ensemble-averaged Pauli-string weights relax to a ternary-valued structure, instead of the binary structure of unitary-invariant circuits. For orthogonal- or symplectic-invariant circuits, the domain wall separating trivial and scrambled regions has a finite width even for Haar-random gates, whereas domain walls are sharp for Haar-distributed random unitary circuits. We further find a fundamental dichotomy between random circuits with two-qubit gates from the two disconnected components of the orthogonal group: While the butterfly velocity for the special orthogonal ensemble lies between zero and the Haar value, the negative-determinant sector exhibits a non-zero lower bound for any gate distribution. Moreover, for qudit size $q=2$, the butterfly velocity can exceed that of the Haar-random ensemble.

quant-pharXiv:2606.03956•Physical review. B./Physical review. B•Jun 3, 2026•0 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

Operator spreading in random unitary circuits with unitary-invariant gate distributions

Zhiyang Tan, Piet W. Brouwer

Random unitary circuits have become a model system to investigate information scrambling in quantum systems. In the literature, mostly random circuits with Haar-distributed gate operations have been considered. In this work, we investigate operator spreading in random unitary circuits in which the elementary gate operations are drawn from general unitary-invariant ensembles, which include the well-studied Haar-distributed random unitary circuits as a special case. Similar to the Haar-distributed case, the long-time behavior of operator spreading with the more general unitary-invariant gate distribution is governed by drift-diffusion equations characterized by the butterfly velocity v B and a diffusion constant D . Differences with the Haar-random case are (i) that it takes a finite time τ b until ensemble-averaged Pauli-string weights take a “binary” form, in which they depend only on whether Pauli operators inside the support of the Pauli strong are equal to the identity matrix, and (ii) that the operator spreading is characterized by a finite “domain-wall width” n DW separating regions with a random-matrix-like Pauli-string distribution. To illustrate these findings, we perform explicit calculations for random unitary circuits distributed according to the Poisson kernel, which interpolates between the trivial and Haar-distributed circuits.

arXiv:2501.04091•Physical review. B./Physical review. B•May 1, 2025•3 citations
We study the amount of interference in random quantum algorithms using a recently derived quantitative measure of interference. To this end we introduce two random circuit ensembles composed of random sequences of quantum gates from a universal set, mimicking quantum algorithms in the quantum circuit representation. We show numerically that, concerning the interference distribution and the level spacing distribution, these ensembles converge to the well-known circular unitary ensemble (CUE) for general complex quantum algorithms, and to the Haar orthogonal ensemble (HOE) for real quantum algorithms. We provide exact analytical formulas for the average and typical interference in the circular ensembles, and show that for sufficiently large numbers of qubits a random quantum algorithm uses with probability close to one an amount of interference approximately equal to the dimension of the Hilbert space. As a by-product, we offer a new way of constructing approximate random unitary operators from the Haar measures of CUE or HOE in a high dimensional Hilbert space using universal sets of quantum gates.
Abstract Quantum algorithms profit from the interference of quantum states in an exponentially large Hilbert space and the fact that unitary transformations on that Hilbert space can be broken down to universal gates that act only on one or two qubits at the same time. The former aspect renders the direct classical simulation of quantum algorithms difficult. Here we introduce higher-order partial derivatives of a probability distribution of particle positions as a new object that shares these basic properties of quantum mechanical states needed for a quantum algorithm. Discretization of the positions allows one to represent the quantum mechanical state of n bit qubits by 2(n bit + 1) classical stochastic bits. Based on this, we demonstrate many-particle interference and representation of pure entangled quantum states via derivatives of probability distributions and find the universal set of stochastic maps that correspond to the quantum gates in a universal gate set. We prove that the propagation via the stochastic map built from those universal stochastic maps reproduces up to a prefactor exactly the evolution of the quantum mechanical state with the corresponding quantum algorithm, leading to an automated translation of a quantum algorithm to a stochastic classical algorithm. We implement several well-known quantum algorithms, analyse the scaling of the needed number of realizations with the number of qubits, and highlight the role of destructive interference for the cost of the emulation.
We study the statistics of quantum interference for completely positive maps. We calculate analytically the mean interference and its second moment for finite-dimensional quantum systems interacting with a simple environment consisting of one or several spins (qudits). The joint propagation of the entire system is taken as unitary with an evolution operator drawn from the circular unitary ensemble (CUE). We show that the mean interference decays with a power law as function of the dimension of the Hilbert space of the environment, with a power that depends on the temperature of the environment.
We study the scaling of the convergence of several statistical properties of a recently introduced random unitary circuit ensemble towards their limits given by the circular unitary ensemble. Our study includes the full distribution of the absolute square of a matrix element, moments of that distribution up to order eight, as well as correlators containing up to 16 matrix elements in a given column of the unitary matrices. Our numerical scaling analysis shows that all of these quantities can be reproduced efficiently, with a number of random gates which scales at most as ${n}_{q}{[\mathrm{ln}({n}_{q}∕ϵ)]}^{\ensuremath{\nu}}$ with the number of qubits nq{n}_{q}nq​ for a given fixed precision ϵϵϵ and $\ensuremath{\nu}>0$.
We investigate operator spreading in random quantum circuits with gates drawn from orthogonal-invariant or symplectic-invariant ensembles, revealing several key distinctions from the well-studied unitary-invariant case. We find that the ensemble-averaged Pauli-string weights relax to a ternary-valued structure, instead of the binary structure of unitary-invariant circuits. For orthogonal- or symplectic-invariant circuits, the domain wall separating trivial and scrambled regions has a finite width even for Haar-random gates, whereas domain walls are sharp for Haar-distributed random unitary circuits. We further find a fundamental dichotomy between random circuits with two-qubit gates from the two disconnected components of the orthogonal group: While the butterfly velocity for the special orthogonal ensemble lies between zero and the Haar value, the negative-determinant sector exhibits a non-zero lower bound for any gate distribution. Moreover, for qudit size q=2q=2q=2, the butterfly velocity can exceed that of the Haar-random ensemble.
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.
Random unitary circuits have become a model system to investigate information scrambling in quantum systems. In the literature, mostly random circuits with Haar-distributed gate operations have been considered. In this work, we investigate operator spreading in random unitary circuits in which the elementary gate operations are drawn from general unitary-invariant ensembles, which include the well-studied Haar-distributed random unitary circuits as a special case. Similar to the Haar-distributed case, the long-time behavior of operator spreading with the more general unitary-invariant gate distribution is governed by drift-diffusion equations characterized by the butterfly velocity v B and a diffusion constant D . Differences with the Haar-random case are (i) that it takes a finite time τ b until ensemble-averaged Pauli-string weights take a “binary” form, in which they depend only on whether Pauli operators inside the support of the Pauli strong are equal to the identity matrix, and (ii) that the operator spreading is characterized by a finite “domain-wall width” n DW separating regions with a random-matrix-like Pauli-string distribution. To illustrate these findings, we perform explicit calculations for random unitary circuits distributed according to the Poisson kernel, which interpolates between the trivial and Haar-distributed circuits.