PaperlayerView exact revision on arXiv

Source-linked AI summary

Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries

Natsuto Isogai, Satoshi Yoshida, Mio Murao

arXiv:2609.38403v1quant-phcs.LGstat.ML

TL;DR

Whether forward-only state-preparation access can improve quantum PAC learning’s accuracy dependence remained unclear. The paper reduces forward-query learning to state-copy lower bounds using a Haar-averaged-output approximation, and shows that worst-case query complexities match classical- and quantum-copy sample complexities in both realizable and agnostic settings.

  • Problem

    It remained unclear whether forward-only access to a state-preparation unitary can improve PAC learning’s accuracy dependence, unlike access that also includes its inverse.

    Source: §1 · pp. 2–3

  • Method

    The proof approximates the Haar-averaged output of a forward-query algorithm using state copies, then applies known lower bounds for quantum-example copies.

    Source: §1.4 · p. 9

  • Results

    Worst-case forward-only query complexities are asymptotically optimal in both learning settings, matching upper bounds from measuring examples and applying an optimal classical learner.

    Source: §1.1 · p. 4, §1.4 · p. 9

  • Takeaways & Limitations

    In the worst-case setting, inverse access is crucial to achieving the known quadratic improvement in realizable learning’s accuracy dependence.

    Source: §1.1 · p. 5, §1.4 · p. 9

    The lower bounds take the worst case over permitted ambient dimensions and compatible state-preparation unitaries.

    Source: §1.1 · p. 4

Abstract

from arXiv · show

Whether quantum computation can reduce the amount of data sampled from an unknown probability distribution required to learn a prediction rule is a fundamental question in quantum machine learning. Quantum PAC learning studies this question using quantum data as a quantum state whose squared amplitudes encode the unknown distribution from which classical learning data are sampled. With only copies of such quantum data, the optimal worst-case sample complexity asymptotically matches that of classical PAC learning. In contrast, access to both a state-preparation unitary for this state and its inverse can improve the query-complexity dependence on the accuracy parameter in realizable learning. However, it has remained unclear whether forward-only access allows such an improvement. In this work, taking the worst case over compatible state-preparation unitaries and their finite ambient dimensions, we show that the optimal forward-only query complexities of realizable and agnostic learning are, respectively, $\Theta((d+\log(1/\delta))/\varepsilon)$ and $\Theta((d+\log(1/\delta))/\varepsilon^2)$, where $d$ is the VC dimension of the concept class, $\varepsilon$ the accuracy parameter, and $\delta$ the failure probability. These bounds match the optimal sample complexities with classical data or quantum data copies. To prove them, we establish a reduction using $q$ copies of the prepared state to approximate the Haar-averaged output of any $q$-query forward-only algorithm. These results show that forward-only access cannot provide an asymptotic query-complexity advantage over learning from classical data or quantum data copies in this worst-case setting, and establish the essential role of inverse access in the known realizable-setting improvement. Our reduction also provides a new framework for analyzing limitations of forward state-preparation access via state-copy lower bounds.

1 Introduction

The section examines whether forward-only access can reduce query complexity, focusing on realizable and agnostic quantum PAC learning in the worst case over ambient dimensions and compatible unitary completions. It presents a reduction from forward queries to state copies that transfers copy lower bounds to forward-query lower bounds and, for sufficiently small approximation error, can help analyze other tasks with copy lower bounds.

1 Introduction

  • PAC learning enables matched accuracy-and-confidence comparisons across access models; quantum-state copies alone give no worst-case asymptotic sample advantage, while forward-and-inverse access improves realizable accuracy dependence [16].The known inverse-access improvement changes the dependence from 1/ε to 1/√ε, up to logarithmic factors.Source: §1 · pp. 2–3

1.1 Main Results

  • In the worst case over ambient dimensions and compatible unitary completions, forward-only query lower bounds for realizable and agnostic learning match sample-access upper bounds up to constant factors.The bounds are optimal, and forward-only access does not achieve the known realizable accuracy improvement available with inverse access [16].Source: §1.1 · pp. 4–5, §1.4 · p. 9

1.2 Method

  • Haar-randomly choosing the unitary completion lets a simulator approximate any q-query forward algorithm’s averaged output using q copies, with error controlled by ambient dimension.Increasing the ambient dimension suppresses the part of the unitary action not reproduced from copies, allowing known copy lower bounds to transfer without asymptotic loss.Source: §1.2 · pp. 6–7, §1.3 · p. 9

1.3 Related Works

  • Forward-only state-estimation methods can improve accuracy dependence when N = O(d), so the worst-case bounds do not rule out advantages for every fixed low-dimensional unitary.The agnostic-learning query complexity with both forward and inverse access remains undetermined by these results.Source: §1.3 · p. 8

1.4 Conclusion

  • The reduction is task-independent and allows limitations of forward-access algorithms to be assessed through limits on information obtainable from state copies.It applies even when algorithms use arbitrary superpositions of inputs and adapt operations to earlier queries.Source: §1.4 · p. 9
  • With sufficiently small approximation error, the reduction lets known state-copy lower bounds replace task-specific analysis of forward-access operations.It provides a tool for investigating whether forward access reduces query counts for tasks with known copy lower bounds.Source: §1.4 · p. 10
  • The paper introduces notation and access models in Section 2, proves the reduction in Section 3, and applies it to learning lower bounds in Section 4.Technical proofs are deferred to the appendices.Source: §1.4 · p. 10

2 Preliminaries

The preliminaries set the mathematical notation and define classical and quantum PAC settings, then compare example-copy and state-preparation-unitary access and review sample and query complexity.

2.1 Basic notation and distances

  • The paper fixes notation for finite-dimensional Hilbert spaces, operators, quantum channels, and trace distance.Source: §2.1 · pp. 10–11

2.2.1 Classical PAC model

  • In classical realizable learning, PEX returns (x, c(x)); in agnostic learning, AEX returns joint-distribution examples and the hypothesis is compared with the best concept in C.Source: §2.2.1 · pp. 11–12

2.2 Probably Approximately Correct (PAC) learning models

  • PAC learning evaluates whether examples support a hypothesis with prescribed accuracy and confidence, while the paper counts examples or oracle queries rather than computation time.Source: §2.2.1 · pp. 11–12

2.2.2 Quantum PAC model with coherent quantum examples

  • Quantum example oracles provide fresh state copies encoding examples, which learners may process jointly or measure; they do not specify the preparation unitary on other inputs.Source: §2.2.2 · pp. 12–13

2.2.3 Quantum PAC model with state-preparation-unitary access

  • A state-preparation unitary maps a known initial state to the quantum example; forward-only access supplies U, while forward-and-inverse access also supplies U†.Source: §2.2.3 · p. 13
  • The paper requires forward-only learners to succeed for every compatible preparation unitary and permitted ambient dimension, with query complexity taken in the worst case.Source: §2.2.3 · p. 13, §2.2.4 · p. 14

2.2.4 Sample complexity and the number of state-preparation queries

  • Forward-only query lower bounds transfer quantum-example-copy lower bounds to realizable and agnostic learning, including improper learners; measuring prepared states also gives classical-example upper bounds.Source: §2.2.4 · pp. 14–15

3 Reduction from forward state-preparation unitaries to quantum states

The section reduces forward-only state-preparation access to quantum-state copies by simulating the Haar-averaged output of any q-query algorithm. Its proof separates a copy-simulable component from a residual component whose weight is bounded.

3.1 The forward state-preparation access setting and the reduction theorem

  • The learner must succeed for every unitary completion satisfying U|0⟩=|ψ⟩, so the analysis averages over Haar-random choices of the unitary's free action.The state lies in a known finite-dimensional subspace; the unitary's action on the orthogonal complement of |0⟩ is unconstrained.Source: §3 · p. 15, §3.1 · p. 16
  • Theorem 3.3 simulates the Haar-averaged output of any q-query forward-only algorithm using q copies of the prepared state, with an error bound.The result applies to states in a known subspace and the simulator is independent of the particular state.Source: §3.1 · pp. 16–17, §3 · p. 16

3.2 Decomposition of the output quantum state and simulation using state copies

  • A three-block decomposition separates the copy-reproducible main and good terms from a bad term that depends on |ψ⟩ and is treated as error.The output is split into copy-simulable sectors and sectors containing bad blocks.Source: §3.2 · pp. 17–18

3.3 Bounding the weight of the remaining output component

  • Lemma 3.8 concerns the weight of sectors containing B under condition q(r−1) < N−1; the supplied passage ends before stating the bound.Source: §3.3 · p. 21

4 Lower bounds for quantum PAC learning with forward unitary queries

The section transfers known quantum-example copy lower bounds to forward-only unitary queries using the Haar-averaged-output simulation. It derives lower bounds for both realizable and agnostic PAC learning in the worst case over permitted ambient dimensions and compatible unitary completions.

4 Lower bounds for quantum PAC learning with forward unitary queries

  • The lower-bound proofs use Theorem 3.3 to reproduce a forward-query learner's Haar-averaged output from q quantum-example copies, enabling copy-model lower bounds to apply.The hard instances use a finite signal subspace orthogonal to the known initial state.Source: §4 · p. 22, §4.1 · p. 23

4.1 Forward-query lower bounds for realizable learning

  • For Boolean concept classes with finite VC dimension d≥2, any realizable (ε, δ)-PAC learner using forward-only access requires queries in the worst case over permitted ambient dimensions, instances, and compatible unitary completions.The stated conditions are 0<ε≤1/32 and 0<δ≤1/4.Source: §4.1 · p. 23

4.2 Forward-query bounds for agnostic learning

  • For a Boolean concept class of finite VC dimension d≥1, any (ε, δ)-agnostic PAC learner in forward-only access requires queries in the worst case over permitted ambient dimensions, joint example distributions, and compatible unitary completions.The theorem assumes 0 < ε ≤ 1/16 and 0 < δ ≤ 1/4.Source: §4.2 · p. 24

A Choi representation

This appendix presents the Choi representation of linear maps and identities used to characterize their properties. It also gives a pairing formula relating Choi operators to maps.

A Choi representation

  • The Choi operator of a linear map is defined through its Choi representation, with the transpose taken in the fixed computational basis.The section also defines Choi vectors and the rank-one Choi operator for a map induced by an operator.Source: A Choi representation · p. 28
  • The Choi pairing formula gives an equivalent identity for relating a map to its Choi representation.Source: A Choi representation · p. 28
  • A linear map is completely positive exactly when its Choi operator is positive semidefinite.Source: A Choi representation · p. 28
  • For a completely positive map, the cited text gives if-and-only-if characterizations of trace preservation and trace nonincrease, although these excerpts do not reveal the conditions being characterized.Source: A Choi representation · p. 28

B Schur–Weyl Decomposition and Schur Orthogonality

This appendix reviews Schur–Weyl duality and Schur orthogonality, then describes how these decompositions represent collective unitary and isometry actions. It defines the Schur transform as the basis change implementing the decomposition.

B Schur–Weyl Decomposition and Schur Orthogonality

  • Schur–Weyl duality decomposes the tensor-power space into unitary-group Weyl modules and symmetric-group Specht modules.Young diagrams index the sectors, with the diagram size and row count constrained by the tensor power and dimension.Source: B Schur–Weyl Decomposition and Schur… · p. 29
  • The Schur transform is a fixed basis change from the tensor-product basis to one adapted to irreducible symmetry sectors.In the Schur basis, collective unitary actions act on the Weyl-module factor while leaving the Specht-module label unchanged.Source: B Schur–Weyl Decomposition and Schur… · pp. 29–30
  • The decomposition also represents isometries between different-dimensional spaces in the Schur basis.The induced action of the tensor-power isometry acts separately on each Weyl module.Source: B Schur–Weyl Decomposition and Schur… · p. 30
  • Schur orthogonality states the Haar-averaged relation between matrices in distinct irreducible unitary-group representations.The averaging uses normalized Haar measure.Source: B Schur–Weyl Decomposition and Schur… · p. 30

C Proof of Lemma 3.4

Lemma 3.4 decomposes a Haar-random state-preparation unitary using a Haar-random rank-(r −1) projector and independent Haar-random isometries. The projector and the good-block isometry have distributions independent of |ψ⟩.

C Proof of Lemma 3.4

  • A Haar-random state-preparation unitary is generated by first sampling a rank-(r −1) Haar-random projector, then choosing independent Haar-random isometries conditioned on it.The isometries act on the orthogonal domain and range blocks in the decomposition.Source: C Proof of Lemma 3.4 · p. 31
  • The projector is uniformly distributed over rank-(r −1) projectors on |0⟩⊥, as follows from the Haar-random isometry W.The proof defines the projector through the image of Bψ under W†.Source: C Proof of Lemma 3.4 · p. 31
  • The distributions of Π and GΠ depend only on the fixed space S⊥, not on |ψ⟩, and the isometry distributions are invariant under independent phases.These properties yield the stated Haar distribution.Source: C Proof of Lemma 3.4 · p. 31

D Proof of Lemma 3.5

Lemma 3.5 constructs a success-branch simulator for the b = 0 sector using q copies of |ψ⟩. Its averaged map reuses a shared random pair across the simulated queries, with dependence on |ψ⟩ entering through the copy-state input.

D Proof of Lemma 3.5

  • The simulator initializes q copy registers in |ψ⟩⊗q, alongside a query register, counter, and failure qubit.The query register is where the original algorithm applies each oracle query.Source: D Proof of Lemma 3.5 · p. 31
  • On successful histories, the simulator swaps the next unused copy into the query register and applies the fixed good block GΠ.The success branch reuses the same pair (Π, GΠ) for every simulated query.Source: D Proof of Lemma 3.5 · p. 33
  • Averaging the success maps over the shared pair defines a completely positive, trace-nonincreasing map, with unknown-state dependence only through P⊗q.The averaging is over the pair shared by all q queries, not a composition of independently averaged single-query channels.Source: D Proof of Lemma 3.5 · p. 33

E Proof of Lemma 3.6

The proof of Lemma 3.6 analyzes the probability of a first B outcome by decomposing adaptive query histories according to their uses of GΠ. It handles adaptive reuse through Haar averaging and an auxiliary completely positive map.

E Proof of Lemma 3.6

  • Lemma 3.6 is stated for m ∈ {0, 1, . . . , q −1} satisfying m(r −1) < N −1 and concerns pfirst.The supplied statement does not show the remainder of its bound.Source: E Proof of Lemma 3.6 · p. 34
  • The final state is decomposed into terms indexed by the number g of uses of GΠ, with each term a homogeneous polynomial of degree g.The fixed linear map Lm,g substitutes matrix-unit basis elements for the corresponding uses in the circuit.Source: E Proof of Lemma 3.6 · pp. 34–35
  • Averaging the common phase removes cross terms between different g, while a completely positive trace-nonincreasing map handles the adaptive reuse of GΠ.The auxiliary lemma is described as a specialization of Lemma 2.11 of [28] for random purifications.Source: E Proof of Lemma 3.6 · p. 35

There exists a positive operator

This section constructs a positive operator for bounding the probability of a first B outcome. The argument combines a decomposition by the number of GΠ uses with a tensor-moment bound for a Haar-random projector.

There exists a positive operator

  • A completely positive map yields a positive Choi operator, which is used to define the positive operator ZL.The proof then uses cyclicity of the trace to obtain the stated relation.Source: There exists a positive operator · pp. 36, 38
  • A Haar-projector tensor-moment bound applies when gk < n and combines the first-moment identity with an operator union bound.The bound concerns projectors acting on distinct tensor factors.Source: There exists a positive operator · pp. 36–37
  • The first-B probability is obtained by testing the pre-query state with Π0, then averaging the decomposition by GΠ-use count over phase and the shared isometry.The resulting operator is independent of Π before the final projector average.Source: There exists a positive operator · pp. 37–38

F Proof of the Haar Moment Lemma

Lemma E.2 constructs a parameter-dependent completely positive, trace-nonincreasing map that applies to every rank-d0 projector. Its proof uses Haar-random isomorphisms and Schur-orthogonality-based block reduction.

Proof of Lemma E.2

  • Lemma E.2 gives a completely positive, trace-nonincreasing map depending only on g, n, k, and the fixed spaces, with the stated property for every rank-d0 projector.The lemma separately specifies that when g = 0, both sides are the scalar 1.Source: F Proof of the Haar Moment Lemma · p. 38
  • For g ≥ 1, the proof identifies S⊥ with C^d0 and extends a Haar-random isomorphism by zero outside the projected subspace.For g = 0, it defines T0(1) = 1.Source: F Proof of the Haar Moment Lemma · pp. 38–39
  • Schur orthogonality eliminates cross terms between Young diagrams, while vectorization yields a fixed unitary Wg independent of Q and G.Wg consists of the input and output Schur transforms and a fixed permutation of tensor factors.Source: F Proof of the Haar Moment Lemma · pp. 38–39
  • Returning to tensor-product coordinates and applying the listed completely positive operations establishes that Tg is completely positive and independent of Q.The proof then substitutes into the preceding equation, compares expressions, and takes a trace to complete the claim.Source: F Proof of the Haar Moment Lemma · p. 40
Loading 2609.38403v1…