Jonas Haferkamp and colleagues demonstrate that even relatively shallow quantum circuits have fundamental limitations in generating truly random quantum operations. The work reveals that designs cannot be generated by any circuit ensemble with lightcones smaller than the system size for the Clifford group, orthogonal group, unitary symplectic groups and the matchgate group.
While recent advances showed sub-linear depth circuits can achieve approximate randomness, the researchers prove these constructions are not universally applicable. Their results show that logarithmic depths are sufficient for “slightly weaker forms of randomness” like additive-error state designs and anti-concentration, revealing a trade-off between circuit depth and the quality of randomness achieved.
Logarithmic Depth for Approximate Quantum Randomness
This finding challenges the long-held assumption that achieving randomness necessitates minimal circuit complexity, and suggests a more fundamental limitation on how easily random quantum operations can be created. The inability to generate these designs with limited lightcones indicates that the spatial spread of quantum information within the circuit is important for producing truly random outputs. While previous analyses of random quantum operations often mirrored classical counterparts, the emergence of randomness at logarithmic depths appears to be distinctly quantum.
Limits of Log-Depth Constructions for Orthogonal Designs
This limitation arises because the mixing time of non-universal circuits appears to be underestimated by lightcone analysis, a technique previously thought reliable for predicting circuit behavior. Researchers found that while lightcones can overestimate mixing in universal circuits, they consistently underestimate it in these non-universal scenarios, indicating a fundamental disconnect between circuit complexity and the generation of random operations. Previous methods for constructing low-depth random unitaries, often relying on analyzing the spectrum of moment operators, also apply to classical counterparts of quantum operations like reversible circuits, but logarithmic depth mixing proves uniquely quantum.
This distinction emphasises a fundamental difference in how classical and quantum systems generate randomness, with quantum systems potentially offering advantages in circuit efficiency, though with limitations, when using logarithmic depths. The researchers demonstrated that for these groups, logarithmic depths can produce designs that, while not perfectly random, are sufficiently random for certain applications.
The team’s analysis builds on a lightcone technique previously used to establish lower bounds on the depth of orthogonal designs, but extends it to a broader range of quantum groups. Detailed proofs and exact statements of the results are available in the Supplementary Information accompanying the publication.
Group Designs: Lower Bounds Across Clifford, Orthogonal, and Symplectic Groups
Specifically, the research delineates boundaries for “gluing” constructions, where local designs are combined to form global ones, and demonstrates that this approach is not universally applicable. Researchers used lightcone arguments to establish these strong lower bounds for additive-error group designs, finding that lightcones often underestimate mixing times in non-universal circuits, a contrast to their tendency to overestimate in universal circuits.
However, the work also identifies conditions where logarithmic depths are sufficient, specifically for additive-error state designs for the orthogonal and symplectic groups, and the Clifford group when limiting the design order to k < 6. “Either the class of operations is sufficiently universal to allow for a gluing construction or a linear lower bound can be proven,” the researchers write, highlighting the fundamental trade-off between circuit complexity and the quality of randomness.
Additive-Error State Designs Emerge at Logarithmic Depths
Designs for generating quantum states, even with limited circuit complexity, face fundamental restrictions across several key computing groups, including the Clifford, orthogonal and symplectic groups. While generating full quantum designs in sub-linear circuit depth proves impossible across any architecture, additive-error state designs and anti-concentration, forms of approximate randomness, can emerge at logarithmic depths in many instances.
Sub-Linear Depth Failures for Universal Circuit Architectures
These findings apply to the Clifford group, the orthogonal group, the unitary symplectic group and the matchgate group, indicating that achieving randomness with minimal circuit complexity is not universally possible. The work delineates a boundary between circuit universality and the feasibility of “gluing” together local operations to create global designs, revealing that either a sufficiently universal class of operations is needed or a linear depth requirement will emerge.
These lower bounds, particularly strong in one dimension, depend on the connectivity of qubits represented by the circuit’s “lightcone,” yet still represent non-trivial results even when considering limited connectivity. The research team also proved these linear limits extend to a broad range of circuit ensembles, including commonly used brickwork circuits, suggesting a widespread constraint on achieving randomness with shallow circuits.
Deriving these bounds for relative-error state designs implies corresponding circuit depth requirements for relative-error group designs, further solidifying the limitations of sub-linear depth approaches. While lightcone arguments often underestimate mixing time in non-universal circuits, they have been shown to overestimate it in universal circuits, suggesting that lightcone considerations can be misleading when evaluating designs. These findings contribute to a more detailed understanding of the relationship between circuit depth, connectivity and the generation of truly random quantum states.
Matchgate Group Requires Linear Depth for Additive-Error Designs
The boundaries between circuit universality and feasibility in quantum computing are becoming clearer, with new work establishing that the matchgate group, a key component in fault-tolerant quantum computation, requires linear circuit depth for certain types of designs. This delineation stems from proving strong lower bounds on circuit depth using lightcone arguments, a technique that analyzes the spread of quantum information. This finding is particularly notable as it goes beyond what can be inferred from lightcone arguments alone, indicating a more subtle relationship between circuit depth and the properties of the resulting quantum state.
Generalized random brickwork circuits further reinforce these limitations, establishing a strong Ω(n) lower bound on relative-error state designs regardless of the underlying architecture. However, the researchers also demonstrated that constructing additive-error Clifford state designs in one dimension is possible with a depth of O(log(n)), using the fact that k-copy ensembles of stabilizer states closely approximate Haar-random states with a trace distance error of O(2-n).
Anti-Concentration Achieved in Logarithmic Depth for Multiple Groups
This limitation extends beyond simple circuit size, as the work demonstrates that commonly considered circuit ensembles cannot generate designs in sub-linear depth on any circuit architecture. This suggests a complex interplay between the quantum group and the specific application when assessing the efficiency of circuit designs. The researchers prove that additive-error state designs and anti-concentration emerge at logarithmic depths in many cases.
See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.
