acceptodds
Withdrawn from ICLR 2027

Polynomially Trainable Variational Quantum Circuits with BQP-Hard Costs

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Understanding when parameterized quantum circuits can be both trainable and computationally advantageous is an important challenge in assessing the potential of variational quantum algorithms. Avoiding exponentially vanishing gradients is essential for scalable optimization, but a trainable landscape is of limited computational interest if its cost function can also be efficiently evaluated classically. Of particular interest is the intermediate regime beyond the immediate neighborhood of Clifford circuits, where inverse-polynomial gradients and the breakdown of known efficient classical approximations had previously been observed numerically, but their coexistence had not been proved. In this work, we establish this phenomenon rigorously under the standard assumption that . Our results provide a theoretical basis for seeking computationally useful trainable quantum models.

Primary area:
learning theory
Keywords:
Parameterized Quantum Circuits, Barren Plateaus, Quantum Advantage

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_4ExqOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This manuscript builds on numerical observations about near-Clifford circuits and tries to rigorously prove that "trainable + classically hard" can coexist. The authors construct a family of PRC (Pauli-rotated Clifford) cost functions. The circuit is a tensor product of three components. There are three main results included in the paper.

Critical strengths
  1. The derivations are clean. I haven't found any arithmetic or logical errors so far.
  2. The paper states explicitly that the results are existential and the hardness is worst-case (Sec. 7), and it also includes a Disclaimer. This is honest and earns credit.
  3. Besides the second moment, the paper also gives a variance lower bound and a full characterization of the width sweep. Overall, the coverage is sufficient.
Critical weaknesses
  1. The "trainable" part and the "hard" part are separated by a tensor product, so the coexistence is essentially trivial.
  2. The paper shows that there exists a worst-case point at which the cost is BQP-hard, and that this point lies inside a certain cube. This has no real structural connection to the D^{-1/2} scale discussed by Meyer et al. Packaging it as a "rigorous realization of the transition-zone phenomenon" (Section 8) is an over-interpretation.
  3. Section 7 admits that average-case hardness is missing, but the abstract and introduction still say the two properties coexist "within the same patch." Readers may easily misread this as holding for random points.
  4. Consecutive K R_Z rotations on the same qubit merge into a single R_Z(Σβ) (Eq. 70). At θ*, each block is just a genuine T gate. At that point the circuit is simply a Clifford+T circuit with t T gates, and its "effective distance" from Clifford is not small.
  5. Definitions C.4 and C.5 only require that one designated component (or the expected squared gradient norm) be inverse-polynomial. In the construction, most gradient components are either zero (dummy) or unanalyzed (β), so the claim of being "free of an exponential barren plateau" is not rigorous. I suggest stating explicitly that it applies only to the readout components, and giving either a result or a counterexample for the β components.
  6. The main text is only about 9 pages and all proofs are in the appendix, so it is hard for readers to see from the main text why the result holds.
Questions for authors

Please see Weaknesses

Reviewer_YNDyOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies whether near-Clifford parameterized quantum circuits can exhibit inverse-polynomial gradients while retaining classically hard cost evaluation. Starting from a Clifford+T circuit, the authors replace each T/T†T/T^\dagger gate with a sequence of small-angle parameterized RZR_Z rotations. They then add a separate readout/spectator register and dummy parameters, and construct an observable with three nonzero Pauli terms (Section 3). Theorem 4.1 and Proposition 4.2 establish inverse-polynomial second-moment and variance bounds for a designated readout gradient. Theorem 5.3 and Corollary 5.4 establish BQP-hardness of cost and gradient evaluation at constructed points in the same parameter patch. Lemma 5.5 addresses finite-precision parameter encoding, and Theorem 6.1 combines these results into an existence theorem.

Critical strengths

1. Clear motivation and a strong Introduction. The paper distinguishes the absence of barren plateaus from classical intractability, rather than treating a favorable gradient scale as evidence of quantum advantage. The discussion of prior near-Clifford results leads naturally to a precise existence question (Section 1, especially page 2).

2. A well-organized theoretical development. The circuit construction, cost formula, gradient bounds, complexity reduction, and finite-precision treatment are presented in a coherent sequence (Sections 3–6 and Appendix F). In particular, Corollary 5.4 strengthens the cost-hardness result by showing that evaluating the designated gradient at a constructed hard point, to inverse-polynomial additive precision, is also BQP-hard.

Critical weaknesses

1. The gradient guarantee does not establish trainability of the hard computation.

The cost in Section 3.6 (Eqs. (27)–(28)) has the form

=\frac{2}{5}\bigl(1+g(\phi,\vartheta)\bigr)\bigl(1+p_Q(\beta)\bigr)-\frac{3}{5}.$$ The parameters $\beta$ encode the Clifford+T computation, whereas Theorem 4.1 and Proposition 4.2 establish gradient bounds for the readout parameters $\phi$ in an independent auxiliary register. For a hard-computation parameter $\beta_j$, $$\frac{\partial C_Q}{\partial\beta_j} =\frac{2}{5}\bigl(1+g(\phi,\vartheta)\bigr) \frac{\partial p_Q}{\partial\beta_j}.$$ Within the prescribed initialization patch, the prefactor is bounded above and below by positive constants for sufficiently large $D$. With the auxiliary parameters fixed, the optimization landscape in $\beta$ is therefore only rescaled: its stationary points and asymptotic gradient scaling are unchanged. The polynomial gradient guarantee does not establish a corresponding property for the parameters carrying the hard computation. There is also a direct distinction between hard cost evaluation and hard energy minimization in this construction. Without restricting the parameters to the near-Clifford patch, setting $\phi_1=-\pi/2$ and the other readout and spectator angles to zero gives $g=-1$ and hence $C_Q=-3/5$, independently of $\beta$ (Eq. (28); Appendix F.2). Thus, finding the unrestricted global minimum does not require optimizing the hard-computation block. The main trainability result has limited bearing on the optimization problem that motivates variational quantum algorithms. **2. The coexistence result relies heavily on a tailored parameterization and observable.** In Section 3.3, each $T/T^\dagger$ gate is replaced by $K$ consecutive rotations about the same $Z$ axis. These rotations can be combined exactly; the implemented unitary depends only on their sum. Consequently, small values of the individual parameters in a $D^{-r}$ coordinate-wise patch do not imply a comparably small accumulated departure from Clifford evolution (Eqs. (15)–(17)). The number of spectator qubits is chosen to produce the required gradient scaling, while the dummy parameters do not affect the cost (Eqs. (4)–(6), (18)–(22)). The transition in Theorem 4.3 is driven by the resulting product of cosine factors. Furthermore, although the observable contains only three Pauli terms, $P_A Z_o$ has weight $M+2$, increasing with system size (Eqs. (19), (25)). These features are integral to the construction, but they make it difficult to interpret the result as a structural property of near-Clifford variational circuits more generally. The paper does not identify which aspects of the coexistence survive a nonredundant parameterization or a more natural, low-weight observable.
Questions for authors
  1. Trainability of the hard-computation parameters (Section 3.6; Theorem 4.1). Can any nontrivial gradient or optimization guarantee be established for the β\beta parameters, independently of the auxiliary register? What does the readout-gradient bound tell us about optimizing the embedded hard computation?

  2. Dependence on the construction (Sections 3.2–3.5; Theorem 4.3). Does the claimed near-Clifford transition persist after consolidating consecutive same-axis rotations and removing the cost-independent dummy parameters? If not, which part of the result depends essentially on the chosen redundant parameter coordinates?

Reviewer_yuiqOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper studies whether a variational quantum circuit can have gradients that are not exponentially small while its cost function remains hard to evaluate classically. It works in the setting of Meyer et al. (2026), where the circuits consist of fixed Clifford gates and one-qubit Pauli rotations and the parameters are initialized uniformly in a small cube around a Clifford point. Meyer et al. showed that for a cube of width about D−1/2D^{-1/2}, with DD the number of parameters, gradients can be kept constant and their Taylor surrogate simulates the cost classically on average. Their numerics suggested a wider transition patch in which gradients decay only polynomially while the surrogate is no longer efficient, and they left a proof of this coexistence as an open direction. The present paper aims to give such a proof for an explicit family of circuits.

The construction puts hardness and trainability on separate registers. On the first register, the hard computation block, an arbitrary Clifford+T circuit QQ is implemented with each TT gate split into many small rotations, so that one point of the cube reproduces QQ exactly while every parameter stays small. The second register, the trainability handle, is a product state of a readout qubit and many spectator qubits, measured with a Pauli string that acts on all of them. Each spectator multiplies the gradient by the cosine of its angle, so the number of spectators sets how fast the gradient decays. The remaining parameters act on dummy qubits that do not affect the cost. The observable is chosen so that the cost is, up to constants, a product of a term from the handle and a term from the acceptance probability of QQ.

The main theorem has two parts. For uniform initialization on a cube of width D−rD^{-r} with fixed 0<r<1/20<r<1/2, which is wider than the D−1/2D^{-1/2} scale, the gradient with respect to the readout parameters has an inverse-polynomial second moment and variance, with an exponent tuned through the number of spectators. For the same circuits this gradient is constant at width D−1/2D^{-1/2} and superpolynomially small on any polynomially wider cube. At the same time, the cube contains an explicit point at which estimating the cost, or the gradient to inverse-polynomial precision, is BQP-hard. Under BQP⊈BPP\mathrm{BQP}\not\subseteq\mathrm{BPP}, the family therefore has polynomially large gradients and a classically hard cost in the same region. The paper is purely theoretical, with all proofs in the appendix.

Critical strengths
  1. A rigorous and explicit answer to a question of current interest. Whether gradients that are not exponentially small can coexist with classically hard costs matters to the QML community, and the paper answers a precise version of this question with a fully explicit construction. I checked the main computations, including the gradient bounds and the hardness reduction, and did not find errors. The complexity-theoretic part is handled with care, and because the cost factorizes, the dependence of the gradient on the initialization width can be computed exactly. The paper proves its stated claims and my concerns below are about the meaning and interpretation of the theorems mean rather than about their validity.
Critical weaknesses

My reservations are about the conceptual content of the result and about whether it supports the framing in the abstract and introduction.

  1. Trainability and hardness come from separate registers

Up to constants, the cost is a product of a term from the trainability handle and a term from the hard block, and the hard block only enters the analyzed gradient through the factor 1+pQ(β)∈[1,2]1+p_Q(\beta)\in[1,2]. The rest comes from a product state whose expectation value is known in closed form, and the polynomial decay of the gradient is put in by hand through the number MM of spectator qubits. With M=0M=0 the gradients are constant on the whole patch, and the hardness argument goes through with different thresholds.

Nothing is shown about the gradients with respect to the hard-block parameters β\beta, which are the only ones that touch the hard computation. For fixed β\beta, the landscape in the trainable directions is known classically once the single number pQ(β)p_Q(\beta) has been estimated, which is the quantum-enhanced classical simulation scenario of Cerezo et al. (2025). So the tension that motivates the paper is not really addressed.

This mechanism is also not new. Gil-Fuster et al. (ICLR 2025, not cited) build trainable and non-dequantizable models from a tensor product of a hard circuit and an easy trainable one, and point out themselves that the trainable part only appears as a multiplicative factor. The supplementary information of Cerezo et al. (2025) also has a non-concentrated loss that is easy on average but classically hard on a measure-zero set of parameters. The new ingredient here is that the hard point sits inside a near-Clifford cube, and I do not think this gives QML researchers new understanding.

  1. The hardness is worst-case and does not single out the transition patch

The KK rotations that replace a TT gate act on the same qubit about the same axis, so they compose to a single rotation. The hard point is just QQ with redundant parameters, and its ℓ1\ell_1 norm is of the order of the TT-count. With about D1/2D^{1/2} rotations per TT gate and M=0M=0, the same construction has a BQP-hard point and constant gradients inside the D−1/2D^{-1/2} cube, which the paper treats as classically accessible. This is consistent with Meyer et al., whose D−1/2D^{-1/2} boundary comes from an average-case (mean-squared error) analysis, while their worst-case analysis already shows super-polynomial runtime for the surrogate once ∥θ∥1\Vert\theta\Vert_1 grows.

The interesting version of the question, and the one suggested by the numerics of Meyer et al., is about typical points of the patch, where training starts. Since worst-case hardness at one point is already present at the D−1/2D^{-1/2} scale, the claim in the abstract to "establish this phenomenon rigorously" overstates what is proved. The limitations section says that random points are not shown to be hard, but I see this as the central issue rather than a limitation.

  1. (Minor) The abstract says that the breakdown of known classical approximations beyond the near-Clifford scale had only been observed numerically. Meyer et al. prove super-polynomial lower bounds on the runtime of their surrogate there, and what is numerical in their work is the polynomial gradient decay.

Overall, the paper is careful and its theorems are correct, but the coexistence comes from placing a trainable product circuit next to a fixed hard circuit, and the worst-case hardness is already present in the regime the paper treats as classically accessible. I do not think the result adds to the understanding of trainability versus classical simulability for QML researchers, and I lean towards rejection.

Questions for authors

Clarification requests.

  1. If each TT gate is split into about D1/2D^{1/2} rotations and M=0M=0, the D−1/2D^{-1/2} cube already contains a BQP-hard point and the gradients there are constant. Apart from the gradient scaling, which is set by the number of spectator qubits, is there a property proved in the paper that holds on the D−rD^{-r} patch but fails on the D−1/2D^{-1/2} cube? My second weakness rests on the hardness being present at both scales, so a positive answer would change my reading of the main claim.
  2. What does the result show beyond the tensor-product construction of Gil-Fuster et al. (ICLR 2025) and the example in the supplementary information of Cerezo et al. (2025), where a non-concentrated loss is easy on average but classically hard on a measure-zero set of parameters? A conceptual point that is specific to the near-Clifford setting would address my first weakness.

Suggestions for future work.

  1. Do the authors see a way to prove hardness at typical points of the patch, for example for estimating the cost at parameters drawn from the initialization distribution, or a lower bound against classical simulation of the patch from quantum data in the sense of Cerezo et al.? This is the statement that would separate the transition patch from the near-Clifford regime.
  2. Do the authors see a way to make the trainable directions involve the hard computation, for example through a lower bound on the derivatives with respect to the hard-block parameters, or for the circuits modified by the linear Clifford encoder in Meyer et al.? This would address the concern that trainability and hardness come from separate registers.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.