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• 15 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•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•41 citations

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•20 citations

Complex Quantum Dynamics Versus Classical Simulability of Noisy Random Circuits

Anjali Waghmare, Sergii Strelchuk, Sathyawageeswar Subramanian

Claims of quantum advantage rest on the classical hardness of simulating quantum circuits. Magic, operator scrambling, anticoncentration, and non-Gaussianity for fermionic circuits are standard diagnostics of complex quantum dynamics. For pure states, some of these have been rigorously connected to classical simulability. Whether these diagnostics reliably track the limits of efficient classical simulation under noise remains unclear. Here, we show that in noisy Clifford+$T$ and nearest-neighbour matchgate+SWAP circuits, dynamical diagnostics and classical simulability can separate in both directions. In particular, the diagnostics can remain nontrivial after classical simulation becomes efficient, or become trivial before known efficient classical algorithms apply. We trace this mismatch to the different statistical properties they probe: magic and scrambling depend on fourth-order statistics of the Pauli spectrum, whereas the simulation algorithms depend primarily on second-order moments, which local noise suppresses at different rates. Thus, dynamical diagnostics measured on a noisy quantum device do not by themselves constitute evidence for classical hardness.

quant-pharXiv:2609.39734•Oct 1, 2026•0 citations

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates

Jon Nelson, Joel Rajakumar, Dominik Hangleiter +1 more

We construct a polynomial-time classical algorithm that samples from the output distribution of noisy geometrically local Clifford circuits with any product-state input and single-qubit measurements in any basis. Our results apply to circuits with nearest-neighbor gates on an \(O(1)\text{-D}\) architecture with depolarizing noise after each gate. Importantly, we assume that the circuit does not contain qubit resets or mid-circuit measurements. This class of circuits includes Clifford-magic circuits and Conjugated-Clifford circuits, which are important candidates for demonstrating quantum advantage using non-universal gates. Additionally, our results can be extended to the case of IQP circuits augmented with CNOT gates, which is another class of non-universal circuits that are relevant to current experiments. Importantly, these results do not require randomness assumptions over the circuit families considered (such as anticoncentration properties) and instead hold for every circuit in each class as long as the depth is above a constant threshold. This allows us to rule out the possibility of fault-tolerance in these circuit models. As a key technical step, we prove that interspersed noise causes a decay of long-range entanglement at depths beyond a critical threshold. To prove our results, we merge techniques from percolation theory and Pauli path analysis.

arXiv:2411.02535•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2026•19 citations

Towards verifiable quantum advantage with random circuits: Observables that survive concentration

Antonio A. Mele, Francesco A. Mele, Jarrod R. McClean +1 more

Demonstrating quantum advantage on current quantum hardware is a central goal of quantum computing, and random quantum circuits underpin many leading proposals. Yet sampling-based demonstrations are often difficult to verify, while observable-based approaches face a different challenge: concentration can suppress differences between circuit instances. Recent experiments have put forward the estimation of out-of-time-order correlators (OTOCs) in random circuits as a promising task for verifiable quantum advantage, yet whether their circuit-to-circuit fluctuations survive concentration as system size grows has remained open. Here we show that they do. For broad classes of local random circuits in any fixed spatial dimension, we prove inverse-polynomial fluctuations of fixed-order OTOCs at system-scale depths. In one-dimensional Haar-random brickwork circuits, we further show that macroscopically many gates contribute to these fluctuations, yet in each layer they remain confined to a sublinear-width region. As a byproduct, we develop a classical algorithm exhibiting the first rigorous improvement over brute-force classical simulation of OTOCs in 1D. Although classical hardness remains open, our results rule out strong concentration as an obstruction to OTOC-based proposals for verifiable quantum advantage.

quant-pharXiv:2609.37890•Sep 30, 2026•1 citation
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.
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.
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.
Claims of quantum advantage rest on the classical hardness of simulating quantum circuits. Magic, operator scrambling, anticoncentration, and non-Gaussianity for fermionic circuits are standard diagnostics of complex quantum dynamics. For pure states, some of these have been rigorously connected to classical simulability. Whether these diagnostics reliably track the limits of efficient classical simulation under noise remains unclear. Here, we show that in noisy Clifford+TTT and nearest-neighbour matchgate+SWAP circuits, dynamical diagnostics and classical simulability can separate in both directions. In particular, the diagnostics can remain nontrivial after classical simulation becomes efficient, or become trivial before known efficient classical algorithms apply. We trace this mismatch to the different statistical properties they probe: magic and scrambling depend on fourth-order statistics of the Pauli spectrum, whereas the simulation algorithms depend primarily on second-order moments, which local noise suppresses at different rates. Thus, dynamical diagnostics measured on a noisy quantum device do not by themselves constitute evidence for classical hardness.
We construct a polynomial-time classical algorithm that samples from the output distribution of noisy geometrically local Clifford circuits with any product-state input and single-qubit measurements in any basis. Our results apply to circuits with nearest-neighbor gates on an O(1)-DO(1)\text{-D}O(1)-D architecture with depolarizing noise after each gate. Importantly, we assume that the circuit does not contain qubit resets or mid-circuit measurements. This class of circuits includes Clifford-magic circuits and Conjugated-Clifford circuits, which are important candidates for demonstrating quantum advantage using non-universal gates. Additionally, our results can be extended to the case of IQP circuits augmented with CNOT gates, which is another class of non-universal circuits that are relevant to current experiments. Importantly, these results do not require randomness assumptions over the circuit families considered (such as anticoncentration properties) and instead hold for every circuit in each class as long as the depth is above a constant threshold. This allows us to rule out the possibility of fault-tolerance in these circuit models. As a key technical step, we prove that interspersed noise causes a decay of long-range entanglement at depths beyond a critical threshold. To prove our results, we merge techniques from percolation theory and Pauli path analysis.
Demonstrating quantum advantage on current quantum hardware is a central goal of quantum computing, and random quantum circuits underpin many leading proposals. Yet sampling-based demonstrations are often difficult to verify, while observable-based approaches face a different challenge: concentration can suppress differences between circuit instances. Recent experiments have put forward the estimation of out-of-time-order correlators (OTOCs) in random circuits as a promising task for verifiable quantum advantage, yet whether their circuit-to-circuit fluctuations survive concentration as system size grows has remained open. Here we show that they do. For broad classes of local random circuits in any fixed spatial dimension, we prove inverse-polynomial fluctuations of fixed-order OTOCs at system-scale depths. In one-dimensional Haar-random brickwork circuits, we further show that macroscopically many gates contribute to these fluctuations, yet in each layer they remain confined to a sublinear-width region. As a byproduct, we develop a classical algorithm exhibiting the first rigorous improvement over brute-force classical simulation of OTOCs in 1D. Although classical hardness remains open, our results rule out strong concentration as an obstruction to OTOC-based proposals for verifiable quantum advantage.