- 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 significant coefficients and an -tail of size at most , 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 -sparse unitaries, the paper obtains a sparse-operator approximation with diamond-distance error using queries. Separately, it gives an LCU-based circuit implementation with the weaker error guarantee . These two output guarantees should be distinguished. The paper also establishes an query lower bound for worst-case diamond-distance learning of unitaries with constant Pauli -norm. Under a restricted distance allowing only inputs with a maximally mixed system marginal, it gives a -query approximation algorithm.
Critical strengths
- The paper gives an explicit way to recover relative phases without controlled access to the unknown unitary. The observables and extract the real and imaginary parts of , 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.
- The phase-oracle family has Pauli -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
- In Theorem 2, the guarantee applies to a sparse operator , whereas the implemented circuit is only guaranteed to achieve error. These are different guarantees, particularly because 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.
- 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 . It has nonzero Pauli coefficients, each of magnitude . Retaining any coefficients leaves an -tail of . Thus, a constant tail bound requires exponentially large . The relevant prior framework concerns the sparsity or Pauli dimensionality of conjugated operators , which is different from the sparsity of itself. This distinction narrows the claimed applicability of the present results.
Questions for authors
- 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?
- The conclusion calls the 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?
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-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ε) 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.