acceptodds
Under review as a conference paper at ICLR 2027

Query Learning Nearly Pauli Sparse Unitaries in Diamond Distance

Abstract

We study the problem of learning nearly -sparse unitaries, meaning that the Pauli spectrum is concentrated on at most components with at most residual mass in Pauli -norm. This class generalizes well-studied families, including sparse unitaries, quantum -juntas, -Pauli dimensional channels, and compositions of depth circuits with near-Clifford circuits. Given only forward query access to an unknown nearly sparse unitary , our goal is to efficiently (both in time and query complexity) construct a quantum mapping that is close in diamond distance to . We design a learning algorithm achieving this guarantee using (non-controlled) forward queries to , and running time polynomial in relevant parameters. A key contribution is an efficient quantum algorithm that, given query access to an arbitrary unknown unitary , estimates all Pauli coefficients (up to a shared global phase) whose magnitude exceeds a given threshold . We also study the broader class of unitaries with bounded Pauli -norm. For that class, we prove an exponential query lower bound . We introduce a more relaxed accuracy metric, which is the diamond distance restricted to a set of input states. Then, we show that, under this metric, unitaries with Pauli -norm uniformly bounded by are learnable with queries.

Primary area:
learning theory
Keywords:
Quantum Learning Theory, Quantum Unitary Learning, Pauli Sparsity, Sparse Recovery

Reviews

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

This paper studies learning an unknown unitary whose Pauli expansion has at most ss significant coefficients and an ℓ1\ell_1-tail of size at most ε\varepsilon, using only non-controlled forward queries. Its main technical ingredient combines Bell sampling of the Choi state with Clifford-based classical shadows to estimate large Pauli coefficients, including their relative phases. For nearly (s,ε)(s,\varepsilon)-sparse unitaries, the paper obtains a sparse-operator approximation with O(ε)O(\varepsilon) diamond-distance error using O~(s3/ε2)\widetilde O(s^3/\varepsilon^2) queries. Separately, it gives an LCU-based circuit implementation with the weaker error guarantee O(sε)O(\sqrt{s\varepsilon}). These two output guarantees should be distinguished. The paper also establishes an Ω(2n/2)\Omega(2^{n/2}) query lower bound for worst-case diamond-distance learning of unitaries with constant Pauli ℓ1\ell_1-norm. Under a restricted distance allowing only inputs with a maximally mixed system marginal, it gives a O~(L14/ε8)\widetilde O(L_1^4/\varepsilon^8)-query approximation algorithm.

Critical strengths
  1. The paper gives an explicit way to recover relative phases without controlled access to the unknown unitary. The observables Rt,sR_{t,s} and It,sI_{t,s} extract the real and imaginary parts of αt∗αs\alpha_t^*\alpha_s, and Lemma 2 quantifies the error amplification associated with the reference coefficient. This is a concrete, reusable ingredient for learning general fixed unitaries, rather than only short-time Hamiltonian evolutions.
  2. The phase-oracle family Ux=I−2∣x⟩⟨x∣U_x=I-2|x\rangle\langle x| has Pauli (ell1(ell_1-norm below three, yet accurate worst-case diamond-distance learning identifies the marked string and therefore inherits the unstructured-search lower bound. Although the reduction is simple, it directly explains why a bounded norm alone cannot replace the nearly sparse assumption for efficient worst-case learning.
Critical weaknesses
  1. In Theorem 2, the O(ε)O(\varepsilon) guarantee applies to a sparse operator U^\widehat U, whereas the implemented circuit is only guaranteed to achieve O(sε)O(\sqrt{s\varepsilon}) error. These are different guarantees, particularly because ε\varepsilon also specifies the structural tail promise and cannot simply be reduced for a fixed target unitary. Query-complexity comparisons should therefore distinguish the output type and use a common final accuracy.
  2. The abstract and introduction describe compositions of shallow circuits with near-Clifford circuits as included in the nearly sparse framework. However, this does not hold with polynomial sparsity in general. For example, consider the depth-one Clifford circuit H⊗n=2−n/2(X+Z)⊗nH^{\otimes n}=2^{-n/2}(X+Z)^{\otimes n}. It has 2n2^n nonzero Pauli coefficients, each of magnitude 2−n/22^{-n/2}. Retaining any s≤2ns\leq 2^n coefficients leaves an ℓ1\ell_1-tail of (2n−s)2−n/2(2^n-s)2^{-n/2}. Thus, a constant tail bound requires exponentially large ss. The relevant prior framework concerns the sparsity or Pauli dimensionality of conjugated operators U†PUU^\dagger P U, which is different from the sparsity of UU itself. This distinction narrows the claimed applicability of the present results.
Questions for authors
  1. Can Theorems 2 and 3 be stated with explicit output types and separate parameters for the structural tail and final learning accuracy? In particular, is Theorem 3 intended only as an improper linear-operator learning result, or is there an efficient CPTP implementation achieving its stated restricted-distance guarantee?
  2. The conclusion calls the O(sε)O(\sqrt{s\varepsilon}) implementation overhead unavoidable and its removal a fundamental open problem. However, Remark 7.8 of the cited Grewal–Liang work describes implementing a nearby CPTP channel through block-encoding and approximate polar decomposition. What prevents that approach from applying to the sparse, operator-norm-close approximation produced by Theorem 2?
1 comment

We thank the reviewer for identifying these points. We will distinguish the guarantees for the two outputs in Theorem 2. We will state these output types and error guarantees separately and use distinct notation for the structural tail parameter and the final learning accuracy.

We thank the reviewer for pointing out the example about the Clifford circuits. We will revise the manuscript to clarify that these circuits are not generally contained in our nearly sparse class. Our method remains useful for learning and characterizing unitaries that do satisfy the small Pauli-ℓ1\ell_1-tail assumption, with potential applications in process characterization, circuit verification, and reverse engineering in quantum optics.

Regarding the suggested block-encoding and approximate-polar-decomposition approach, thank you for pointing us to it. We will examine whether its assumptions apply to the sparse operator produced by Theorem 2 and clarify the scope of our implementation guarantee. Finally, we agree that “unavoidable” is too strong. Our analysis establishes an O(sε)O(\sqrt{s\varepsilon}) error for the stated LCU implementation, but does not prove that this overhead is necessary for all implementations. We will remove that wording and describe reducing the implementation error as an open question.

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

This paper studies the problem of learning nearly Pauli sparse unitary channels in diamond distance using forward query access. This family contains unitaries whose vector of Pauli coefficients are l1l_1 ϵ\epsilon-close to an ss- sparse vector (supported on ss Paulis) . An algorithm is proposed using O~(s3/ϵ2)\tilde{O}(s^3/\epsilon^2) queries. It's also shown that near sparsity condition is essential to obtain efficient algorithm. This is done by proving a lower bound Ω(2n/2)\Omega(2^{n/2}) queries to learn unitaries with bounded l1l_1 norm. Finally, it's shown that learning unitaries in Choi distance is possible using O~(L14/ϵ8)\tilde{O}(L_1^4/\epsilon^8) queries where L1L_1 is the Pauli l1l_1 norm.

Critical strengths
  • Learning in diamond distance is known to be difficult either in terms of complexity and technical proofs.
  • The separation between diamond distance and Choi distance is interesting.
  • Recovering relative phases using forward queries is a nice contribution (Lemma 2).
Critical weaknesses
  • The upper bound is not known to be optimal. In particular, it's not known if the additional ss factor compared to exact sparsity is needed.

  • Technically, the algorithm seems to rely on classical shadows, the lower bound is a reduction to (Grover) search problem LB.

Questions for authors
  • Could you achieve O(s2/ϵ2)O(s^2/\epsilon^2) complexity?

  • It seems that you are using Definition 3 just with A={I/N}\mathcal{A} = \{I/N\} which gives l1l_1 norm between Choi states. Why not working with the latter norm directly?

1 comment

We thank the reviewer for the thoughtful comments. We believe an O~(s2/ε2)\widetilde O(s^2/\varepsilon^2) bound for general nearly Pauli-sparse unitaries may be possible, and are investigating whether the remaining factor of ss can be removed. At present, however, we do not have a proof of this improvement. We view closing this gap as an important direction for future work.

The algorithm does use classical shadows for estimating relative phases. This is a standard and powerful method that has been widely used in related work. The observables MsM_s, Rt,sR_{t,s}, and It,sI_{t,s} have constant Hilbert-Schmidt norm. Under the Clifford measurement scheme used in our algorithm, this yields a constant shadow norm and thus a dimension-independent sample bound, with logarithmic dependence on the number of observables. We had not included the derivation because we thought it was straightforward; we will clarify the bound and provide its derivation in the revised paper.

To the best of our knowledge, the reduction to Grover search is new. It provides a simple, intuitive example showing that a bounded Pauli ℓ1\ell_1-norm alone does not guarantee efficient learning in the standard worst-case diamond distance.

For A={I/N}\mathcal A=\{I/N\}, Definition 3 reduces to the trace norm distance between the normalized Choi operators, as proved in Appendix E, Lemma 5. We presented the restricted diamond norm as a useful notion that can incorporate the limits of practical problems and opens the door to study a broader family of distance metrics beyond the Choi states.

Reviewer_ZDUYOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies learning unitaries with approximately sparse Pauli coefficients, i.e. those that are ε\varepsilon close to unitaries with ss-sparse Pauli coefficients in Pauli L1 distance. The authors design an algorithm using roughly s3/\varpsilon2queriess^3/\varpsilon^2 queries. The authors also study learning unitaries with bounded Pauli L1 norm.

Critical strengths
  1. The authors generalize the existing work on Pauli sparse unitaries by considering unitaries that are approximately sparse. The algorithm proposed by the authors has reasonable query complexity compared to existing algorithms that rely on the sparsity assumption.
  2. While the algorithm draws ideas from previous works, in particular the algorithm for learning Hamiltonians and classical shadows, the authors overcome some important technical challenges. One challenge is that the linear approximation for small-evolution-time Hamiltonians does not work for nearly-sparse unitaries. Another challenge is that the classical shadow algorithm only outputs real coefficients.
Critical weaknesses
  1. There is still an ss-factor gap compared to the algorithm for exactly sparse unitaries, and the authors did not provide a lower bound argument that shows s2s^2 is impossible. However, this is not a weakness that warrants rejection.
Questions for authors

Do you think obtaining an s2s^2 algorithm is possible for approximatly Pauli-sparse unitaries?

1 comment

We thank the reviewer for raising this question. We believe that an O~(s2/ε2)\widetilde O(s^2/\varepsilon^2) query bound for general nearly Pauli-sparse unitaries may be possible, and we are investigating how to remove the remaining factor of ss. At present, however, we do not have a proof of this improvement. Our current general bound remains O~(s3/ε2)\widetilde O(s^3/\varepsilon^2); the O~(s2/ε2)\widetilde O(s^2/\varepsilon^2) bound in Corollary 1 requires the additional assumption that the target has a Pauli coefficient of constant magnitude. We view closing this gap as an important direction for future work.

Comments on the paper

2 comments
Area_Chair_4MtjOpenReview ↗

Discussion?

Dear reviewers,

could you please confirm whether the very brief responses by the authors answered your questions?

Dear authors,

if you want to engage in a more robust discussion, the time is now. The forum will close to the authors on November 18, 2026: https://iclr.cc/Conferences/2027/Dates

Sincerely Your AC

Based on the reviewer's comments, we slightly modified the paper. Particularly, we added details for the shadow norm, modified the statement of Theorem 2 to separate the sparse description and the unitary implementation. Lastly, we added a remark for using the polar-decomposition to implement the algorithm's output as a quantum channel.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.