Researchers Build Strong Quantum Designs in Logarithmic Depth

Unitaries have wide-ranging applications across physics and quantum information, extending from scrambling and black-hole dynamics to foundational primitives in quantum algorithms. Strong unitary designs capture a more demanding operational notion of approximation, requiring indistinguishability from Haar randomness even for quantum algorithms that may access a unitary not only in the forward direction, but also through its inverse, transpose, and complex conjugate. Teodor Parella-Dilmé of the The Barcelona Institute of Science and Technology and colleagues from Freie University Berlin previously left open whether strong unitary designs can be generated in logarithmic depth using only the system qubits.

Logarithmic Depth Quantum Circuit Construction via Pauli-Mixing Bounds

Scientists at Dahlem Centre for Co and The Barcelona Institute of Science and Technology have achieved a new quantum circuit construction method, reducing the required depth to generate strong unitary designs from previously unattainable levels to an optimal Θ(log n). This represents a sharp improvement over prior methods that necessitated additional qubits or incurred an extra logarithmic factor when limited to utilising only the system qubits.

This advancement addresses a longstanding open question regarding logarithmic-depth generation of strong unitary designs, initially posed by Schuster, Ma, Lombardi, Brandão, and Huang. The team achieved this through a novel approach employing a logarithmic-depth Pauli-mixing bound for the perfect-matching ensemble, a technique that randomly pairs qubits and applies independent, random two-qubit gates.

Consequently, information scrambling, as measured by out-of-time-order correlators, can occur in logarithmic time within this architecture, utilising only the system’s original qubits. Despite these results representing a step forward, scaling these parameters to realistically complex systems remains a considerable challenge, as the current construction is limited to fixed design order k and measurable-error tolerance.

Logarithmic-depth Unitary Designs via Pauli Mixing and Quantum Scrambling

Strong approximate unitary k-designs are constructed in optimal Θ(log n) all-to-all circuit depth using only the n original system qubits. This bound controls the mixed forward-reverse two-query case, which, combined with existing design and gluing results, yields strong unitary designs of arbitrary fixed order.

Quantum information scrambling describes how information initially stored in a small part of a system spreads across many degrees of freedom, becoming encoded in nonlocal correlations. The information remains globally present but becomes difficult to recover through local measurements or restricted observations. Scrambling is expected in complex many-body systems and plays a key role in the approach to thermalization in isolated quantum systems. Furthermore, it is central to black-hole dynamics, governing how rapidly information falling into a black hole is dispersed and potentially recovered, and underpinning decoupling and recovery protocols in quantum information.

Determining how quickly physical dynamics can scramble information requires a way of detecting scrambling and establishing when it is complete. In many-body systems, scrambling is closely connected to the growth of initially simple operators into increasingly nonlocal ones. Out-of-time-order correlators (OTOCs) probe this growth through the increasing failure of an initially local operator to commute with distant observables, often relying on protocols combining forward and reverse evolution.

These quantities have also been the subject of study in recent near-term quantum advantage proposals. A generic Haar unitary is exponentially costly to describe or implement, but approximate unitary designs avoid this difficulty by reproducing a finite collection of Haar moments up to a controlled error. This allows comparison of realistic circuit ensembles with Haar evolution at the level accessible to finite-moment experiments, and efficient random-circuit constructions make the corresponding Haar averages accessible without implementing a generic Haar-random unitary.

Finite-moment Haar replacement also appears in fidelity-estimation protocols, randomized benchmarking, and decoupling arguments. Guarantees are typically stated for experiments querying evolution in the forward direction only, whereas OTOC measurement may apply reverse evolution as a separate physical step. For approximate designs, a bound on the usual forward moments need not be preserved when separate queries to U† or U* reshuffle the moment indices.

A design adequate to these protocols must therefore extend the Haar replacement to a broader query model, remaining indistinguishable from Haar measure to bounded-query experiments that may separately access U, U†, U T, and U*, while interleaving these calls with arbitrary quantum operations and quantum memory. Access to one of these transformations does not generally provide access to the others in a black-box setting. Establishing this notion allows researchers to ask how quickly a circuit reaches this stronger form of Haar-like scrambling: how much depth is required before it becomes a strong design.

Schuster, Ma, Lombardi, Brandão, and Huang conjectured that both strong unitary designs and strong pseudorandom unitaries can be generated in logarithmic depth using only the physical qubits, a restriction that matters if the circuit is meant to model closed-system dynamics. Additional qubits enlarge the system’s Hilbert space and introduce resources absent from the dynamics being modelled. Logarithmic depth is the natural target because it is the earliest possible asymptotic scale in the all-to-all circuit model.

A layer of bounded-size gates can enlarge the support of a local operator by only a constant factor, so systemwide operator spreading requires depth Ω(log n). The same work established this lower bound for strong designs and gave constructions that either require additional qubits or incur an additional logarithmic factor when restricted to the system alone. Researchers resolve this question for strong unitary designs with a simple random-circuit architecture.

Each layer draws a uniformly random perfect matching of the n qubits, with n even, and applies independent Haar-random two-qubit gates to the matched pairs. Their result also implies that OTOC-growth can occur in logarithmic time, within such architecture using solely the system-qubits. The analysis rests on a uniform Pauli-mixing result for this ensemble, starting from any nonidentity Pauli operator and approaching the corresponding Haar-induced distribution in total variation after a number of layers logarithmic in the system size and in the inverse target accuracy.

This bound holds uniformly over the initial Pauli operator and throughout the stated error range. Typical-input or average-case mixing would not suffice, since the strong-design reduction requires control of the relevant two-query experiment for every initial Pauli. They obtain this worst-case estimate by reducing the evolution to a Markov chain on Pauli supports and constructing a monotone grand coupling. This uniformity controls two-query experiments containing one call from {U, UT} and one from {U*, U†}, which are not covered by ordinary unitary designs.

Combining the estimate with an independent weak design for the ordinary forward-query sector, and then applying the strong-gluing framework to reach higher orders, gives approximate strong unitary designs of every fixed order and fixed measurable-error tolerance on the original n-qubit system, with optimal all-to-all depth Θ(log n). Strong-design behaviour is therefore reached on the same asymptotic depth scale as that required for an initially local operator to acquire system-wide support.

Section II defines the strong-design model, its measurable-error criterion, and the construction framework. Section III states the formal results, while Section IV explains the proof strategy. The appendices provide the technical background and imported inputs, establish the Pauli-mixing estimate, and assemble the main constructions. Section V returns to the scope of the result and the remaining open directions. A unitary k-design is an ensemble of unitaries E that cannot be distinguished from Haar-random unitaries by any experiment making at most k queries.

The standard notion of a unitary k-design, referred to as a weak k-design, restricts the distinguisher to k forward queries to the same sampled unitary U ∼E. Strong k-designs require more, allowing a k-query experiment to have access to U, U†, U T, or U* after drawing U. Throughout, these are ordinary oracle calls, with controlled versions requiring an additional convention stated below.

The ensemble is therefore a strong k-design if every such experiment remains indistinguishable from Haar-random. Exact unitary designs, which reproduce the first k moments of the Haar measure exactly, are available only in special settings. In practice, researchers therefore work with approximate designs. The choice of approximation error is important because it determines which experiments are guaranteed to exhibit Haar-like behaviour.

The additive error represents the simplest of the three notions, controlling experiments in which all k uses of the sampled unitary occur in a single parallel call, while allowing the input state to be entangled with an arbitrary reference system. The relative error imposes the most demanding approximation guarantee, controlling any measurement outcome multiplicatively: if an event occurs with probability p for the Haar measure, then it occurs with probability at least p(1 − εr) under the approximate measure.

Researchers have constructed strong approximate unitary designs in logarithmic circuit depth using only the system qubits.

This means they created a system that mimics the behaviour of complex random unitaries, but with a defined and controllable level of approximation. The designs achieved this using a method involving pairing qubits and applying random two-qubit gates, requiring a circuit depth of Θ(log n) for a system of n qubits. The work builds on existing design techniques and focuses on controlling experiments that access a unitary and its variations, such as its inverse and transpose.