Shallow Quantum Circuits Lost One Route to Advantage

A new classical algorithm removes one proposed foothold for shallow-circuit quantum advantage. For any chosen output string from a constant-depth quantum circuit, it estimates that string's probability to additive error in time polynomial in the number of qubits and inverse precision. The circuit may use arbitrary connectivity, as long as its gates have bounded fan-in and its depth stays fixed.^[1]

That is a sharper result than it first sounds. Shallow circuits matter because they fit coherence-limited hardware and appear in proposals for separating quantum and classical computation. Earlier classical algorithms for the same arbitrary-connectivity probability-estimation task took quasipolynomial time, scaling as n to the order of log n. The new theorem reduces that dependence to polynomial time.^[1]

The task starts with a circuit U, an n-bit target string x and an error tolerance epsilon. The algorithm returns an estimate of the probability that measuring U applied to the all-zero input produces x, within additive error epsilon. It is deterministic and does not require the circuit to live on a two-dimensional grid or any other geometry.^[1]

The proof exploits the bounded light cones created by constant depth and bounded gate size. It identifies output bits that are not strongly concentrated on the target string, handles concentrated regions with a cluster-expansion method, and uses inclusion-exclusion to control the influence of the remaining bits. Only small connecting regions need to be evaluated for the requested additive accuracy.^[1]

The boundary is crucial: estimating one selected probability is weaker than sampling from the circuit. Separate additive estimates for many strings need not add to one and need not approximate the true distribution in total-variation distance. The theorem also does not construct an approximation to the full output state.^[1]

The method also estimates the magnitude of product-operator expectation values in polynomial time. It does not recover the sign of a general real expectation value or the phase of a complex one, so those more general estimation problems remain open.^[1]

For advantage claims, the practical lesson is to name the task precisely. A shallow device may still target sampling problems, relational problems or other outputs beyond this estimator's reach. But claiming an advantage from the difficulty of additively estimating a single chosen output probability no longer fits this circuit class under the theorem's assumptions.^[1]

This is a theoretical preprint, not a benchmark against a running quantum processor. Polynomial time can still hide large constants, and the guarantee assumes fixed depth and fixed gate arity. It does not cover depth growing with system size, unbounded-fan-in operations, adaptive computation or arbitrary deep circuits. The next test is whether the same ideas can reach efficient sampling for broader shallow-circuit families.^[1]