Shallow Circuits Fail to Realise Approximate Designs for Quantum Groups

Maxwell West of Los Alamos National Laboratory and colleagues have shown that constructing approximate designs, key for quantum computation and benchmarking, is fundamentally limited for specific quantum groups. A loophole allowing faster, sublinear circuit depths using additional unitaries beyond these groups does not exist. The team has confirmed a fundamental limit to the efficiency of constructing specific quantum computations. Building circuits utilising operations from the matchgate, orthogonal, symplectic, and Clifford groups requires more steps than previously anticipated, even when incorporating additional computational tools.

This finding impacts standard methods for verifying and testing quantum computers that rely on these particular groups of operations, necessitating substantial computational resources. An ‘approximate design’ is like a complete set of tools; the more complex the task, the more tools, and therefore steps, are needed. The team now considers whether these limitations fundamentally constrain the scalability of certain quantum algorithms and benchmarking procedures.

Invariant states reveal limitations in quantum circuit complexity

The team employed a technique centred on identifying ‘invariant states’ within the defining representations of quantum groups like the matchgate and Clifford groups; these states remain unchanged under specific transformations. This approach isn’t about directly examining circuits, but rather about exploiting inherent symmetries within the groups themselves to create a sensitive ‘probe’ for circuit depth. By analysing how a shallow-depth circuit perturbs these invariant states, researchers could determine if the circuit’s structure fundamentally limited its ability to approximate a broader range of quantum operations; a disturbance indicates a lack of sufficient complexity.

Researchers investigated the construction of approximate unitary designs, focusing on ensembles of unitaries that can efficiently represent quantum operations. The team deliberately moved beyond restricting ensembles to unitaries solely from subgroups like the matchgate, orthogonal, and Clifford groups, exploring the use of ‘ambient’ unitaries acting on additional qubits. This approach was chosen to address a loophole in prior work and determine if shallow-depth circuits could genuinely form designs, even with expanded possibilities beyond the target group.

Optimal shallow circuit depth for restricted quantum groups is fundamentally limited

Scientists and the Quantum Science Centre have demonstrated that existing linear-depth design constructions, achieving a circuit depth of O(log k log log nk/ε), are demonstrably optimal; previous research suggested potential improvements to this depth. This finding resolves a long-standing question regarding the possibility of constructing approximate designs with sublinear circuit depth for the matchgate, orthogonal, symplectic, and Clifford groups, a feat now proven impossible even when utilising additional ‘ambient’ unitaries. The team’s work establishes a fundamental limitation, revealing an exponential separation between the complexity of creating designs from these restricted groups and the full unitary group, impacting quantum tomography and benchmarking protocols. The researchers and the Quantum Science Centre confirmed that no ensemble of shallow unitaries, even those incorporating additional ‘ambient’ unitaries not strictly within the matchgate, orthogonal, symplectic, or Clifford groups, can create approximate designs; this extends previous findings demonstrating the impossibility of sublinear-depth designs using only unitaries from these restricted groups. The team demonstrated this limitation by considering a ‘typical’ unitary from an ensemble and showing it either approximately stabilises an invariant state, allowing for distinction from the target group’s Haar measure, or fails to approximate the target Haar measure sufficiently well.

The research demonstrated that constructions achieving a circuit depth of O(log k log log nk/ε) are optimal for creating approximate designs using the matchgate, orthogonal, symplectic, and Clifford groups. This means that shallow-depth circuits cannot form these designs, even when utilising additional unitaries beyond these groups. The findings explain why quantum tomography and benchmarking schemes relying on these groups require greater circuit depth than those using the full unitary group. Researchers confirmed this limitation by analysing how well typical unitaries from these ensembles approximate the desired mathematical properties.