A new arXiv preprint reports a mathematical and computational analysis of when random all-to-all quantum circuits can be properly learned from black-box unitary queries. The task assumes that the circuit’s layout and gate family are known, and asks whether a matching circuit can be reconstructed while approximating the queried operation. Its model places the main transition at a depth that grows roughly as log₂ n + log₂ log₂ n, where n is the qubit count, under a stated concentration assumption.
The study tracks “lightcones”: the sets of qubits that can influence a chosen gate or input. As those sets spread through the circuit, they eventually cover the system. In the paper’s notation, the predicted full-coverage depth is d* = log₂ n + log₂ log₂ n − log₂ S₀ + O(1), with the stochastic and mean-evolved hitting times differing by no more than 2 under the same assumption.
How the circuit is learned
The proposed method searches for pivot gates that can be isolated through the circuit’s lightcones. It tests trial inverse gates with tomography, which reconstructs information about a quantum operation, and then factors gates from the front or back of the circuit. Proper learning means recovering the same graph and gate family while approximating the original unitary.
For a positive even lightcone below full coverage, the probability of having no edge crossings is at most 1/(n−1). Those crossings provide the local structure the inversion method uses to identify pivot gates. The paper also derives formulas for the expected number and variance of crossings in its random-pairing model.
The detailed analysis is limited to two-local circuits, meaning circuits built from two-qubit gates, and assumes an even number of qubits. For two-qubit partitions, the overlap probability for two consecutive random partitions approaches 1 − e⁻¹ᐟ², or about 0.393, as the system grows. Repeated same-qubit sequences are treated as composite gates when possible.
The simulations tracked the prediction
The study combined analytical approximations with direct numerical simulation. One recurrence comparison started with a lightcone size S₀ = 1 and used 100 trials across qubit counts increasing in powers of two. In a separate learning experiment, each qubit-count and depth setting used 1000 sampled all-to-all circuit layouts.
The simulated transition shifted approximately linearly with log₂ n, with the reported data always within 1 depth unit of the model line. Full iterative learning appeared to offer at most a constant offset over forward-only learning.
A bound with conditions
For a two-local circuit of depth D that meets the theorem’s requirements, the forward proper-learning protocol has a query bound of O(|G|nD/[L(D)² ε⁴]). The expression depends on the gate count, qubit count, depth, lightcone size and target accuracy. The bound requires good forward lightcones, signal propagation, a suitably spaced gate set and appropriate handling of circuit factors.
Those qualifications are central. The main stochastic lightcone result is conditional on an assumed approximation between the random process and its mean-evolved version, while the paper says its concentration arguments do not by themselves guarantee small fluctuations across every qubit in a full circuit. The rigorous query guarantee is for forward learning and requires precise control of the other input qubit.
A result confined to one model
The evidence is theoretical and computational: it concerns black-box query access, known circuit structure and simulated random all-to-all circuits. The result therefore describes learnability in that model, rather than demonstrating that a physical quantum device can be learned at the predicted depth.
Taken together, the paper presents logarithmic depth as a conditional threshold for a specific two-qubit circuit ensemble. Its detailed lightcone analysis does not establish a general result for higher-locality circuits, and the numerical tests used sampled layouts at each parameter setting rather than replacing the underlying assumptions with a general proof.
Paper data and sources
Original title: Proper Learning of Shallow All-to-All Quantum Circuits
Authors: Steven Kordonowy, Jacob Watkins
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text