We consider the problem of finding a near ground state of a p-spin model with Rademacher couplings by means of a low-depth circuit. As a direct extension of the authors' recent work [GJW20], we establish that any poly-size n-output circuit that produces a spin assignment with objective value within a certain constant factor of optimality, must have depth at least log n=(2 log log n) as n grows. This is stronger than the known state of the art bounds of the form (log n=(k(n) log log n)) for similar combinatorial optimization problems, where k(n) depends on the optimality value. For example, for the largest clique problem k(n) corresponds to the square of the size of the clique [Ros10]. At the same time our results are not quite comparable since in our case the circuits are required to produce a solution itself rather than solving the associated decision problem. As in our earlier work [GJW20], the approach is based on the overlap gap property (OGP) exhibited by random p-spin models, but the derivation of the circuit lower bound relies further on standard facts from Fourier analysis on the Boolean cube, in particular the Linial-Mansour-Nisan Theorem. To the best of our knowledge, this is the first instance when methods from spin glass theory have ramifications for circuit complexity.
We consider the problem of finding a near ground state of a p-spin model with Rademacher couplings by means of a low-depth circuit. As a direct extension of the authors' recent work [GJW20], we establish that any poly-size n-output circuit that produces a spin assignment with objective value within a certain constant factor of optimality, must have depth at least log n=(2 log log n) as n grows. This is stronger than the known state of the art bounds of the form (log n=(k(n) log log n)) for similar combinatorial optimization problems, where k(n) depends on the optimality value. For example, for the largest clique problem k(n) corresponds to the square of the size of the clique [Ros10]. At the same time our results are not quite comparable since in our case the circuits are required to produce a solution itself rather than solving the associated decision problem. As in our earlier work [GJW20], the approach is based on the overlap gap property (OGP) exhibited by random p-spin models, but the derivation of the circuit lower bound relies further on standard facts from Fourier analysis on the Boolean cube, in particular the Linial-Mansour-Nisan Theorem. To the best of our knowledge, this is the first instance when methods from spin glass theory have ramifications for circuit complexity.
A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum p-spin glasses, random Hamiltonians whose interactions act on p-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement.
We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with n, we prove that, for all sufficiently large fixed p, any circuit preparing an n-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth Ωp(logn). In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed D, a sufficiently large degree prefactor rules out depth-D preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits.
Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.
The quantum approximate optimization algorithm (QAOA) is a method of approximately solving combinatorial optimization problems. While QAOA is developed to solve a broad class of combinatorial optimization problems, it is not clear which classes of problems are best suited for it. One factor in demonstrating quantum advantage is the relationship between a problem instance and the circuit depth required to implement the QAOA method. As errors in NISQ devices increases exponentially with circuit depth, identifying lower bounds on circuit depth can provide insights into when quantum advantage could be feasible. Here, we identify how the structure of problem instances can be used to identify lower bounds for circuit depth for each iteration of QAOA and examine the relationship between problem structure and the circuit depth for a variety of combinatorial optimization problems including MaxCut and MaxIndSet. Specifically, we show how to derive a graph, G, that describes a general combinatorial optimization problem and show that the depth of circuit is at least the chromatic index of G. By looking at the scaling of circuit depth, we argue that MaxCut, MaxIndSet, and some instances of Vertex Covering and Boolean satisifiability problems are suitable for QAOA approaches while Knapsack and Traveling Sales Person problems are not.
In this work, we prove the strongest known lower bounds for QAC0, allowing polynomially many gates and ancillae. Our main results show that:
(1) Depth-3 QAC0 circuits cannot compute PARITY, and require Ω(exp(n)) gates to compute MAJORITY.
(2) Depth-2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size.
We develop new classical simulation techniques for QAC0 to obtain our depth-3 bounds. In these results, we relax the output requirement of the quantum circuit to a single bit, making our depth 2 approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC0 circuits, which can compute PARITY exactly in depth 2 (exp size). Our techniques further suggest that, for boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth 2 QAC0 circuits, regardless of size, cannot exactly synthesize an n-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth 2 exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound). Finally, we argue that approximating PARITY in QAC0, with significantly better than 1/poly(n) advantage on average, is just as hard as computing it exactly. Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems
In an important recent development, Anshu, Breuckmann, and Nirkhe \cite{anshu2022nlts} resolved positively the so-called No Low-Energy Trivial State (NLTS) conjecture by Freedman and Hastings. The conjecture postulated the existence of linear-size local Hamiltonians on n qubit systems for which no near-ground state can be prepared by a shallow (sublogarithmic depth) circuit. The construction in \cite{anshu2022nlts} is based on recently developed good quantum codes. Earlier results in this direction included the constructions of the so-called Combinatorial NLTS – a weaker version of NLTS – where a state is defined to have low energy if it violates at most a vanishing fraction of the Hamiltonian terms \cite{anshu2022construction}. These constructions were also based on codes. In this paper we provide a "non-code" construction of a class of Hamiltonians satisfying the Combinatorial NLTS. The construction is inspired by one in \cite{anshu2022construction}, but our proof uses the complex solution space geometry of random K-SAT instead of properties of codes. Specifically, it is known that above a certain clause-to-variables density the set of satisfying assignments of random K-SAT exhibits an overlap gap property, which implies that it can be partitioned into exponentially many clusters each constituting at most an exponentially small fraction of the total set of satisfying solutions. We establish a certain robust version of this clustering property for the space of near-satisfying assignments and show that for our constructed Hamiltonians every combinatorial near-ground state induces a near-uniform distribution supported by this set. Standard arguments then are used to show that such distributions cannot be prepared by quantum circuits with depth o(log n). Since the clustering property is exhibited by many random structures, including proper coloring and maximum cut, we anticipate that our approach is extendable to these models as well.
Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored.
We prove an explicit depth hierarchy theorem for QNC0. For each d≥12, we construct a family of two-round interactive problems on which no depth-(d−1) quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than d by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every d, yielding a hierarchy of problems that show unconditional quantum advantage of QNC0 over NC0.
A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits.
These results show that increasing depth strictly increases computational power within QNC0, establishing a genuinely quantum hierarchy.
We use heuristic optimization methods in extensive computations to determine with low systematic error ground-state configurations of the mean-field p-spin glass model with p=3. Here, all possible triplets in a system of N Ising spins are connected with a bond. This model has been of recent interest, since it exhibits the "overlap gap condition," which should make it prohibitive to find ground states asymptotically with local search methods when compared, for instance, with the p=2 case better known as the Sherrington-Kirkpatrick model (SKM). Indeed, it proves more costly to find good approximations for p=3 than for the SKM, even for our heuristic. Compared to the SKM, the ground-state behavior for p=3 is quite distinct also in other ways. For the SKM, finite-size corrections for large system sizes N→∞, of both the ensemble average over ground-state energy densities and the width of their distribution, vary anomalously with noninteger exponents. In the p=3 case here, the energy density and its distribution appear to scale with lnN/N and 1/N corrections, respectively. The distribution itself is consistent with a Gumbel form. Even more stark is the contrast for the bond-diluted case, where the SKM has shown previously a notable variation of the anomalous corrections exponent with the bond density, while for p=3 no such variation is found here. Hence, for the 3-spin model, all measured corrections scale the same as for the random energy model (REM), corresponding to p=∞. This would suggest that all p-spin models with p≥3 exhibit the same ground-state corrections as in the REM.