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

Principle of majorization: Application to random quantum circuits

Raúl O. Vallejos, Fernando de Melo, Gabriel G. Carlo

Published Jul 7, 2021• 13 citations
arXivHTMLPDF

Abstract

We test the principle of majorization J. I. Latorre and M. A. Mart\'{\i}n-Delgado, Phys. Rev. A 66, 022305 (2002). in random circuits. Three classes of circuits were considered: (i) universal, (ii) classically simulatable, and (iii) neither universal nor classically simulatable. The studied families are: {cnot, H, T}, {cnot, H, not}, {cnot, H, S} (Clifford), matchgates, and IQP (instantaneous quantum polynomial-time). We verified that all the families of circuits satisfy on average the principle of decreasing majorization. In most cases the asymptotic state (number of gates $\ensuremath{\rightarrow}\ensuremath{\infty}$) behaves like a random vector. However, clear differences appear in the fluctuations of the Lorenz curves associated with asymptotic states. The fluctuations of the Lorenz curves discriminate between universal and nonuniversal classes of random quantum circuits, and they also detect the complexity of some nonuniversal but not classically efficiently simulatable quantum random circuits. We conclude that majorization can be used as an indicator of complexity of quantum dynamics, as an alternative to, e.g., entanglement spectrum and out-of-time-order correlators.

DOI
10.1103/physreva.104.012602

Related papers

Optimal Complexity of Parameterized Quantum Circuits

Guilherme Ilário Correr, Pedro C. Azado, Diogo O. Soares-Pinto +1 more

Parameterized quantum circuits are central to the development of variational quantum algorithms in the NISQ era. A key feature of these circuits is their ability to generate an expressive set of quantum states, enabling the approximation of solutions to diverse problems. The expressibility of such circuits can be assessed by analyzing the ensemble of states produced when their parameters are randomly sampled, a property closely tied to quantum complexity. In this work, we compare different classes of parameterized quantum circuits with a prototypical family of universal random circuits to investigate how rapidly they approach the asymptotic complexity defined by the Haar measure. We find that parameterized circuits exhibit faster convergence in terms of the number of gates required, as quantified through expressibility and majorization-based complexity measures. Moreover, the topology of qubit connections proves crucial, significantly affecting entanglement generation and, consequently, complexity growth. The majorization criterion emerges as a valuable complementary tool, offering distinct insights into the behavior of random state generation in the considered circuit families.

arXiv:2405.19537•Entropy•Jan 8, 2026•1 citation

Unified framework for efficiently computable quantum circuits

Igor Ermakov, Oleg Valentinovich Lychkovskiy, Tim Byrnes

Quantum circuits consisting of Clifford and matchgates are two classes of circuits that are known to be efficiently simulatable on a classical computer. We introduce a unified framework that shows in a transparent way the special structure that allows these circuits to be efficiently simulatable. The approach involves analyzing the transformation of operators in the Heisenberg picture, and viewing this as a spread within a network of basis operators. The operator amplitudes are found to follow a single variable Porter-Thomas distribution for random universal quantum circuits. The number of operators with amplitude above a threshold value is shown to have a characteristic form involving an initial exponential growth, saturation, then exponential decay in the presence of decoherence. We show the number of significant operators can be used to estimate the complexity of a numerical algorithm where errors can be consistently controlled as a function of the complexity of the simulation.

arXiv:2401.08187•EPJ Quantum Technology•Aug 14, 2026•3 citations

Transitions in Entanglement Complexity in Random Circuits

Sarah True, Alioscia Hamma

Entanglement is the defining characteristic of quantum mechanics. Bipartite entanglement is characterized by the von Neumann entropy. Entanglement is not just described by a number, however; it is also characterized by its level of complexity. The complexity of entanglement is at the root of the onset of quantum chaos, universal distribution of entanglement spectrum statistics, hardness of a disentangling algorithm and of the quantum machine learning of an unknown random circuit, and universal temporal entanglement fluctuations. In this paper, we numerically show how a crossover from a simple pattern of entanglement to a universal, complex pattern can be driven by doping a random Clifford circuit with T gates. This work shows that quantum complexity and complex entanglement stem from the conjunction of entanglement and non-stabilizer resources, also known as magic.

arXiv:2202.02648•Quantum•Sep 22, 2022•36 citations

Efficient Classical Simulation of Random Shallow 2D Quantum Circuits

John C. Napp, Rolando L. La Placa, Alexander M. Dalzell +2 more

A central question of quantum computing is determining the source of the advantage of quantum computation over classical computation.Even though simulating quantum dynamics on a classical computer is thought to require exponential overhead in the worst case, efficient simulations are known to exist in several special cases.It was widely assumed that these easy-to-simulate cases as well as any yetundiscovered ones could be avoided by choosing a quantum circuit at random.We prove that this intuition is false by showing that certain families of constant-depth, 2D random circuits can be approximately simulated on a classical computer in time only linear in the number of qubits and gates, even though the same families are capable of universal quantum computation and are hard to exactly simulate in the worst case (under standard hardness assumptions).While our proof applies to specific random circuit families, we demonstrate numerically that typical instances of more general families of sufficiently shallow constantdepth 2D random circuits are also efficiently simulable.We propose two classical simulation algorithms.One is based on first simulating spatially local regions which are then "stitched" together via recovery maps.The other reduces the 2D simulation problem to a problem of simulating a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements.Similar processes have recently been the subject of an intensive research focus, which has observed that the dynamics generally undergo a phase transition from a low-entanglement (and efficient-to-simulate) regime to a highentanglement (and inefficient-to-simulate) regime as measurement strength is varied.Via a mapping from random quantum circuits to classical statistical mechanical models, we give analytical evidence that a similar computational phase transition occurs for both of our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied and, additionally, that the effective 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime.Implementing the latter algorithm for the depth-3 "brickwork" architecture, for which exact simulation is hard, we find that a laptop could simulate typical instances on a 409 × 409 grid with a total variation distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms.Numerical results support our analytic evidence that the algorithm is asymptotically efficient.

arXiv:2001.00021•Physical Review X•Apr 27, 2022•140 citations

Polynomial Resource Classification of Quantum Circuit Familes via Classical Shadows

Andrew Maciejunes, Ross Gore, Sachin Shetty +1 more

We compare four polynomial-resource measurement strategies, (I) $Z$-basis-only, (II) nearest-neighbor $ZZ$ (NN), (III) multi-basis ($Z$, $X$, $Y$), and (IV) classical shadows, for classifying three quantum circuit families: IQP, Clifford, and Clifford$+T$. We find $Z$-only measurements outperform multi-basis and classical shadows across all qubit counts and all four classifiers evaluated, and the $O(\nqubits)$-feature NN strategy matches $Z$-only to within $0.02$ in Random Forest accuracy. The best result is a Random Forest accuracy of $0.91$ at 4--5 qubits under $Z$-only ($0.89$ for NN, $0.85$ for multi-basis, $0.67$ for shadows). All four strategies collapse to near-chance accuracy ($\approx 0.33$) above approximately 12 qubits under the quadratic shot budget $\shots = 16\nqubits^2$. These findings indicate that the discriminative signal between these circuit families is concentrated in local, nearest-neighbor $Z$-basis correlations, consistent with the diagonal gate structure of IQP circuits, and that additional Pauli correlator types or long-range correlations carry no compensating discriminative power for this task. We provide a formal theoretical framework showing that circuits with high diagonal fraction in a given basis concentrate their correlator structure in that basis, and that any deviation from the dominant basis incurs a provably higher estimator variance. These results establish that a quadratic shot budget is insufficient for reliable classification above approximately 12 qubits, but do not rule out the existence of a subquadratic or otherwise more efficient polynomial-resource strategy; whether any polynomial measurement protocol can classify these families at large qubit counts remains an open question.

quant-pharXiv:2604.25708•Apr 29, 2026•0 citations

Entanglement spectrum of matchgate circuits with universal and non-universal resources

Andrew M. Projansky, Joshuah T. Heath, James Daniel Whitfield

The entanglement level statistics of a quantum state have recently been proposed to be a signature of universality in the underlying quantum circuit. This is a consequence of level repulsion in the entanglement spectra being tied to the integrability of entanglement generated. However, such studies of the level-spacing statistics in the entanglement spectrum have thus far been limited to the output states of Clifford and Haar random circuits on product state inputs. In this work, we provide the first example of a circuit which is composed of a simulable gate set, yet has a Wigner-Dyson distributed entanglement level spectrum without any perturbing universal element. We first show that, for matchgate circuits acting on random product states, Wigner-Dyson statistics emerge by virtue of a single SWAP gate, in direct analog to previous studies on Clifford circuits. We then examine the entanglement spectrum of matchgate circuits with varied input states, and find a sharp jump in the complexity of entanglement as we go from two- to three-qubit entangled inputs. Studying Clifford and matchgate hybrid circuits, we find examples of classically simulable circuits whose output states exhibit Wigner-Dyson entanglement level statistics in the absence of universal quantum gate elements. Our study thus provides strong evidence that entanglement spectrum is not strongly connected to notions of simulability in any given quantum circuit.

arXiv:2312.08447•Quantum•Aug 7, 2024•3 citations
We test the principle of majorization J. I. Latorre and M. A. Mart'{\i}n-Delgado, Phys. Rev. A 66, 022305 (2002). in random circuits. Three classes of circuits were considered: (i) universal, (ii) classically simulatable, and (iii) neither universal nor classically simulatable. The studied families are: {cnot, H, T}, {cnot, H, not}, {cnot, H, S} (Clifford), matchgates, and IQP (instantaneous quantum polynomial-time). We verified that all the families of circuits satisfy on average the principle of decreasing majorization. In most cases the asymptotic state (number of gates \ensuremath→\ensuremath∞\ensuremath{\rightarrow}\ensuremath{\infty}\ensuremath→\ensuremath∞) behaves like a random vector. However, clear differences appear in the fluctuations of the Lorenz curves associated with asymptotic states. The fluctuations of the Lorenz curves discriminate between universal and nonuniversal classes of random quantum circuits, and they also detect the complexity of some nonuniversal but not classically efficiently simulatable quantum random circuits. We conclude that majorization can be used as an indicator of complexity of quantum dynamics, as an alternative to, e.g., entanglement spectrum and out-of-time-order correlators.
Parameterized quantum circuits are central to the development of variational quantum algorithms in the NISQ era. A key feature of these circuits is their ability to generate an expressive set of quantum states, enabling the approximation of solutions to diverse problems. The expressibility of such circuits can be assessed by analyzing the ensemble of states produced when their parameters are randomly sampled, a property closely tied to quantum complexity. In this work, we compare different classes of parameterized quantum circuits with a prototypical family of universal random circuits to investigate how rapidly they approach the asymptotic complexity defined by the Haar measure. We find that parameterized circuits exhibit faster convergence in terms of the number of gates required, as quantified through expressibility and majorization-based complexity measures. Moreover, the topology of qubit connections proves crucial, significantly affecting entanglement generation and, consequently, complexity growth. The majorization criterion emerges as a valuable complementary tool, offering distinct insights into the behavior of random state generation in the considered circuit families.
Quantum circuits consisting of Clifford and matchgates are two classes of circuits that are known to be efficiently simulatable on a classical computer. We introduce a unified framework that shows in a transparent way the special structure that allows these circuits to be efficiently simulatable. The approach involves analyzing the transformation of operators in the Heisenberg picture, and viewing this as a spread within a network of basis operators. The operator amplitudes are found to follow a single variable Porter-Thomas distribution for random universal quantum circuits. The number of operators with amplitude above a threshold value is shown to have a characteristic form involving an initial exponential growth, saturation, then exponential decay in the presence of decoherence. We show the number of significant operators can be used to estimate the complexity of a numerical algorithm where errors can be consistently controlled as a function of the complexity of the simulation.
Entanglement is the defining characteristic of quantum mechanics. Bipartite entanglement is characterized by the von Neumann entropy. Entanglement is not just described by a number, however; it is also characterized by its level of complexity. The complexity of entanglement is at the root of the onset of quantum chaos, universal distribution of entanglement spectrum statistics, hardness of a disentangling algorithm and of the quantum machine learning of an unknown random circuit, and universal temporal entanglement fluctuations. In this paper, we numerically show how a crossover from a simple pattern of entanglement to a universal, complex pattern can be driven by doping a random Clifford circuit with T gates. This work shows that quantum complexity and complex entanglement stem from the conjunction of entanglement and non-stabilizer resources, also known as magic.
A central question of quantum computing is determining the source of the advantage of quantum computation over classical computation.Even though simulating quantum dynamics on a classical computer is thought to require exponential overhead in the worst case, efficient simulations are known to exist in several special cases.It was widely assumed that these easy-to-simulate cases as well as any yetundiscovered ones could be avoided by choosing a quantum circuit at random.We prove that this intuition is false by showing that certain families of constant-depth, 2D random circuits can be approximately simulated on a classical computer in time only linear in the number of qubits and gates, even though the same families are capable of universal quantum computation and are hard to exactly simulate in the worst case (under standard hardness assumptions).While our proof applies to specific random circuit families, we demonstrate numerically that typical instances of more general families of sufficiently shallow constantdepth 2D random circuits are also efficiently simulable.We propose two classical simulation algorithms.One is based on first simulating spatially local regions which are then "stitched" together via recovery maps.The other reduces the 2D simulation problem to a problem of simulating a form of 1D dynamics consisting of alternating rounds of random local unitaries and weak measurements.Similar processes have recently been the subject of an intensive research focus, which has observed that the dynamics generally undergo a phase transition from a low-entanglement (and efficient-to-simulate) regime to a highentanglement (and inefficient-to-simulate) regime as measurement strength is varied.Via a mapping from random quantum circuits to classical statistical mechanical models, we give analytical evidence that a similar computational phase transition occurs for both of our algorithms as parameters of the circuit architecture like the local Hilbert space dimension and circuit depth are varied and, additionally, that the effective 1D dynamics corresponding to sufficiently shallow random quantum circuits falls within the efficient-to-simulate regime.Implementing the latter algorithm for the depth-3 "brickwork" architecture, for which exact simulation is hard, we find that a laptop could simulate typical instances on a 409 × 409 grid with a total variation distance error less than 0.01 in approximately one minute per sample, a task intractable for previously known circuit simulation algorithms.Numerical results support our analytic evidence that the algorithm is asymptotically efficient.
We compare four polynomial-resource measurement strategies, (I) ZZZ-basis-only, (II) nearest-neighbor ZZZZZZ (NN), (III) multi-basis (ZZZ, XXX, YYY), and (IV) classical shadows, for classifying three quantum circuit families: IQP, Clifford, and Clifford+T+T+T. We find ZZZ-only measurements outperform multi-basis and classical shadows across all qubit counts and all four classifiers evaluated, and the $O(\nqubits)$-feature NN strategy matches ZZZ-only to within 0.020.020.02 in Random Forest accuracy. The best result is a Random Forest accuracy of 0.910.910.91 at 4--5 qubits under ZZZ-only (0.890.890.89 for NN, 0.850.850.85 for multi-basis, 0.670.670.67 for shadows). All four strategies collapse to near-chance accuracy (≈0.33\approx 0.33≈0.33) above approximately 12 qubits under the quadratic shot budget $\shots = 16\nqubits^2$. These findings indicate that the discriminative signal between these circuit families is concentrated in local, nearest-neighbor ZZZ-basis correlations, consistent with the diagonal gate structure of IQP circuits, and that additional Pauli correlator types or long-range correlations carry no compensating discriminative power for this task. We provide a formal theoretical framework showing that circuits with high diagonal fraction in a given basis concentrate their correlator structure in that basis, and that any deviation from the dominant basis incurs a provably higher estimator variance. These results establish that a quadratic shot budget is insufficient for reliable classification above approximately 12 qubits, but do not rule out the existence of a subquadratic or otherwise more efficient polynomial-resource strategy; whether any polynomial measurement protocol can classify these families at large qubit counts remains an open question.
The entanglement level statistics of a quantum state have recently been proposed to be a signature of universality in the underlying quantum circuit. This is a consequence of level repulsion in the entanglement spectra being tied to the integrability of entanglement generated. However, such studies of the level-spacing statistics in the entanglement spectrum have thus far been limited to the output states of Clifford and Haar random circuits on product state inputs. In this work, we provide the first example of a circuit which is composed of a simulable gate set, yet has a Wigner-Dyson distributed entanglement level spectrum without any perturbing universal element. We first show that, for matchgate circuits acting on random product states, Wigner-Dyson statistics emerge by virtue of a single SWAP gate, in direct analog to previous studies on Clifford circuits. We then examine the entanglement spectrum of matchgate circuits with varied input states, and find a sharp jump in the complexity of entanglement as we go from two- to three-qubit entangled inputs. Studying Clifford and matchgate hybrid circuits, we find examples of classically simulable circuits whose output states exhibit Wigner-Dyson entanglement level statistics in the absence of universal quantum gate elements. Our study thus provides strong evidence that entanglement spectrum is not strongly connected to notions of simulability in any given quantum circuit.