REVIEW 9 cited by
Random unitaries in extremely low depth
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Random unitaries in extremely low depth
read the original abstract
We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over $n$ qubits in $\log n$ depth. In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in $\text{poly}(\log n)$ depth, and in all-to-all-connected circuits in $\text{poly}(\log \log n)$ depth. In all three cases, the $n$ dependence is optimal and improves exponentially over known results. These shallow quantum circuits have low complexity and create only short-range entanglement, yet are indistinguishable from unitaries with exponential complexity. Our construction glues local random unitaries on $\log n$-sized or $\text{poly}(\log n)$-sized patches of qubits to form a global random unitary on all $n$ qubits. In the case of designs, the local unitaries are drawn from existing constructions of approximate unitary $k$-designs, and hence also inherit an optimal scaling in $k$. In the case of PRUs, the local unitaries are drawn from existing PRU constructions. Applications of our results include proving that classical shadows with 1D log-depth Clifford circuits are as powerful as those with deep circuits, demonstrating superpolynomial quantum advantage in learning low-complexity physical systems, and establishing quantum hardness for recognizing phases of matter with topological order.
Forward citations
Cited by 9 Pith papers
-
Sample Optimal and Memory Efficient Quantum State Tomography
A sample-optimal quantum state tomography algorithm that is memory-efficient by using unitary Schur sampling with streaming access to samples.
-
General framework for anticoncentration and linear cross-entropy benchmarking in photonic quantum advantage experiments
A representation-theoretic framework computes LXEB scores and proves anticoncentration for Fock-state Boson Sampling in the saturated regime using irrep decompositions of bosonic spaces.
-
Unitary Designs from Two Chaotic Hamiltonians and a Random Pauli Operation
Unitary designs emerge from the temporal ensemble of two chaotic Hamiltonian evolutions separated by a random Pauli operation, based on the universal Pauli spectrum.
-
Entanglement Asymmetry in Random Quantum Automata
In random quantum automaton ensembles, the subsystem symmetrization scale depends on the initial state's participation entropy, and the onset of U(1) entanglement asymmetry coincides with the onset of subsystem coherence.
-
Self-Attention for Quantum Entanglement Prediction
MLP and self-attention models predict bipartite second Rényi entropy from randomized projective measurements more accurately and sample-efficiently than classical-shadow formulas on 2- and 4-qubit Haar states.
-
Non-Clifford Cost of Random Unitaries
Rigorous bounds establish that t = Theta(k^2) non-Clifford gates are necessary and sufficient for frame-potential approximation to unitary k-designs while t = Theta(nk) suffices for relative-error k-designs.
-
Efficient witnessing and testing of magic in mixed quantum states
Efficient witnesses and testing algorithms based on stabilizer Rényi entropy certify and quantify magic in mixed states, with experimental demonstration on IonQ hardware showing robustness under strong noise.
-
Fermionic Averaged Circuit Eigenvalue Sampling
FACES is a new protocol for simultaneous self-consistent learning of averaged error rates across many FLO gates with rigorously shown efficient sampling complexity via Kravchuk transformations.
-
Quantum Convolutional Neural Networks are Effectively Classically Simulable
QCNNs are classically simulable via Pauli shadows on low-bodyness subspaces of locally-easy datasets, with explicit simulation demonstrated up to 1024 qubits for phases of matter classification.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.