PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Power of Adaptivity in Testing Quantum States in Fidelity

Jan Seyfried, Sayantan Sen, Marco Tomamichel

arXiv:2609.08733v2quant-phcs.DS

TL;DR

The paper asks how adaptivity affects quantum state testing when guarantees are expressed in fidelity rather than trace distance. It uses partial learning and ℓ2 testing to study certification, equivalence, and independence testing, finding that certification needs no adaptivity while equivalence testing separates adaptive from non-adaptive protocols.

  • Problem

    Although trace-distance testing tasks share an optimal non-adaptive approach, whether fidelity testing has task-specific separations and benefits from adaptivity remains a question.

    Source: §1 · pp. 2–3

  • Method

    The paper adapts a partial-learning and testing framework that reduces testing under different distances to ℓ2 testing.

    Source: §1.2 · p. 8, §2 · p. 9

  • Results

    In fidelity, certification needs no adaptivity, while non-adaptive equivalence testing requires Ω̃(1/ε^2) samples even for qubits.

    Source: §1 · p. 4, §1.1 · p. 5

  • Takeaways & Limitations

    The results indicate that testing unknown states can require extracting information before testing, and adaptivity can help with that step.

    Source: §1.2 · p. 8

    Dimension-dependent lower bounds for non-adaptive testing and the optimality of the equivalence and independence testers remain open.

    Source: §1.2 · p. 8

Abstract

from arXiv · show

We study the problems of quantum state certification, equivalence testing and independence testing. In certification, given samples of an unknown quantum state $\rho$ and the description of a state $\sigma$, the goal is to test whether $\rho=\sigma$, or whether $\rho$ and $\sigma$ are far in a given distance measure. In equivalence testing, $\sigma$ is also unknown and only accessible via samples. Independence testing decides whether $\rho_{AC}=\rho_A\otimes\rho_C$, or is far from being a product. The sample complexities of these problems are now well-understood for a decision gap $\varepsilon$ in trace distance: in the single-copy measurement setting with $d$-dimensional states, all three tasks can be solved using the same non-adaptive approach, which uses $\Theta(d^{3/2}/\varepsilon^2)$ samples and is optimal in general, even without adaptivity. In this work, we consider decision gaps expressed in fidelity and study possible separations between these problems and how adaptivity can help. We prove that certification with respect to fidelity for a state $\sigma$ of rank $r$ does not benefit from adaptivity and requires $\widetilde{\Theta}(r^{3/2}/\varepsilon)$ samples. For equivalence testing and independence testing, we provide adaptive algorithms using $\widetilde{O}(\min\{d^{3/2}/\varepsilon^2,d^{9/4}/\varepsilon\})$ and $\widetilde{O}(\min\{(d_Ad_C)^{3/2}/\varepsilon^2,d_A^{9/4}d_C^{3/4}/\varepsilon\})$ samples, for $d_A\geq d_C$, respectively. Our main technique is a framework that uses partial learning and a reduction to testing in $\ell_2$-distance, adapted from the distribution testing literature. We show that adaptivity matters for equivalence testing in fidelity by proving that $\widetilde{\Omega}(1/\varepsilon^2)$ samples are necessary in the non-adaptive case even for qubits, showing a separation from certification.

1 Introduction

The introduction asks whether adaptivity changes quantum property testing when closeness is measured in fidelity, across certification, equivalence testing, and independence testing. It presents task-specific results: certification needs no adaptivity, while equivalence testing exhibits a separation between adaptive and non-adaptive protocols.

1 Introduction

  • The paper studies certification against a known state, equivalence testing between unknown states, and testing whether a bipartite state is a product.It frames fidelity as a setting in which these tasks may have different sample complexities and adaptivity may matter.Source: §1 · pp. 2–4
  • A partial-learning framework reduces testing under different distances to testing in ℓ2, using subroutines from quantum testing and learning.The authors note that this framework may also be adapted to settings such as joint measurements.Source: §1 · p. 4

1.1 Our Results

  • For known σ of rank r, non-adaptive certification in fidelity uses Θ̃(r^3/2/ε) samples, and a matching lower bound holds even for adaptive protocols.The upper bound is independent of the ambient dimension d.Source: §1.1 · p. 5
  • Adaptive equivalence testing uses Õ(min{d^3/2/ε^2, d^9/4/ε}) samples for two unknown states.The paper reports improvement over trace-distance testing when ε < 1/d^3/4.Source: §1.1 · p. 5
  • For independence testing, the paper gives an adaptive approach that uses partial learning and avoids the precision overhead of learning both subsystems before certification.When dA and dC are roughly equal, the reported sample complexity matches the cost of learning a subsystem.Source: §1.1 · pp. 6–7
  • Non-adaptive equivalence testing requires Ω̃(1/ε^2) samples even for qubits, establishing a separation from the adaptive upper bound.The authors state that the lower bound, combined with the adaptive algorithm, demonstrates the power of adaptivity for fidelity equivalence testing.Source: §1.1 · pp. 5, 7
  • For quantum Markov chains, the results give sufficient samples for certification when the reference chain is known and for equivalence testing when both chains are unknown.The approach tests marginals of the chain.Source: §1.1 · p. 7

1.2 Discussion

  • The discussion attributes the equivalence-testing benefit to adaptivity enabling needed information to be learned before testing, while noting that optimality and dimension-dependent non-adaptive lower bounds remain open.The authors also identify whether fidelity equivalence testing is harder than certification as unresolved.Source: §1.2 · p. 8

2 Overview of our Results

The paper adapts an ℓ2-testing framework to fidelity testing and studies when adaptivity helps across certification, equivalence, and independence testing. Its results include rank-dependent certification, an adaptive-versus-non-adaptive separation for equivalence testing, and a structured reduction for independence testing.

2 Overview of our Results

  • The ℓ2-testing framework reduces several testing tasks to equivalence testing, and this work presents the first single-copy algorithms for fidelity certification, equivalence, and independence testing.The framework uses a subset-support equivalence tester as a fundamental subroutine.Source: §2 · p. 9

2.1 State Certification in Fidelity

  • For rank-r σ, fidelity certification uses eΘ(r^3/2/ε) samples, and adaptivity is unnecessary for optimal sample complexity up to polylogarithmic factors.The approach bounds infidelity using weighted ℓ2 distances on buckets defined from σ’s eigenvalues.Source: §2.1 · p. 10

2.2 Equivalence Testing in Fidelity

  • Equivalence testing uses approximate learning to bucket large eigenvalues while testing smaller eigenvalues together, balancing learning and testing costs.The learning subroutine gives an operator-norm guarantee; careful bucket definitions and analysis avoid incorporating too much of the wrong subspaces.Source: §2.2 · p. 10
  • The adaptive equivalence algorithm uses logarithmically many phases, and its case distinction arises within one approach rather than by combining separate algorithms.The approach reduces the second term of the prior bound by a factor of d^3/4.Source: §2.2 · pp. 10–11

2.3 Non-adaptive Lower Bounds for Equivalence Testing in Qubits

  • Even for qubits, non-adaptive equivalence testing has a lower bound of eΩ(1/ε^2), separating it from adaptive testing.The hard instances randomize the eigenbasis; non-adaptive measurements are typically poorly aligned and reveal little information.Source: §2.3 · p. 11

2.4 Mutual Information Testing

  • Independence testing reduces to equivalence testing, while learning buckets separately for ρA and ρC is more efficient than bucketing their product state as a whole.The independence-testing guarantee is related to mutual information testing with only logarithmic factors.Source: §2.4 · p. 11

3 Preliminaries

The preliminaries establish notation, measurement and distance conventions, and classical testing tools used in the paper. The subspace-testing construction turns quantum measurements into distributions that can be compared with an ℓ2 tester.

3 Preliminaries

  • A POVM is a set of positive operators summing to the identity; measuring ρ produces label z with probability tr[ρMz].The paper uses eO, eΩ, and eΘ to hide polylogarithmic parameter dependencies.Source: §3 · pp. 11–12
  • The preliminaries define quantum-state distance measures and invoke the Fuchs-van de Graaf inequalities to relate them.They also state a reduction of fidelity certification to states with eigenvalues in eΩ(ε/d), at parameter ε/2.Source: §3 · pp. 12–13
  • The classical subroutine tests equality or ℓ2 separation for two unknown distributions restricted to a subset, under a bound on one restricted distribution’s ℓ2 norm.The stated guarantee is success probability at least 0.999.Source: §3 · p. 14

3.1 Subroutine: Testing Equivalence on Subspaces in ℓ2-Distance

  • On a known subspace, a random-unitary POVM produces classical distributions from ρ and σ for comparison on the unitary’s outcome set.The measurement uses the subspace eigenvectors and an additional outcome for probability outside the projection.Source: §3.1 · p. 14

4 Certification in Fidelity

The section establishes fidelity certification bounds: non-adaptive single-copy measurements suffice, and the rank-dependent sample complexity is optimal up to polylogarithmic factors even against adaptive protocols.

4.1 Certification in Fidelity with Rank Dependence

  • For certification, eO(r3/2/ε) samples of ρ suffice with probability at least 0.99; for some σ, eΩ(r3/2/ε) samples are necessary, even for adaptive protocols.The upper bound’s polylogarithmic factors have no dimensional dependence.Source: §4 · p. 16, §4.1 · p. 18

4 Certification in Fidelity

  • For general dimension d, non-adaptive single-copy certification uses eO(d^3/2/ε) samples with success probability at least 0.99.The proof partitions σ’s eigenvalues into buckets and tests the resulting subspaces.Source: §4 · pp. 16–17

4.1 Certification in Fidelity with Rank Dependence

  • The algorithm uses O(r^(3/2)/ε) samples to reject upon any hit outside supp(σ), then tests equivalence on supp(σ) using eO(r^(3/2)/ε) samples.Source: §4.1 · p. 18

4.2 Optimality of our Certification Bound

  • The rank-r lower bound follows by reducing fidelity certification to trace-distance certification at precision √ε and choosing σ maximally mixed on an r-dimensional subspace.Without a rank assumption, the lower bound is Ω(d^3/2/ε).Source: §4.2 · p. 21

5 Equivalence Testing in Fidelity

This section studies adaptive single-copy fidelity equivalence testing for two unknown quantum states, establishing a sample complexity of \(\widetilde{O}(\min\{d^{3/2}/\varepsilon^2,\,d^{9/4}/\varepsilon\})\).

5 Equivalence Testing in Fidelity

  • For equivalence testing of two unknown quantum states ρ and σ in dimension d, with ε∈(0,1), eO(min{d^(3/2)/ε^2, d^(9/4)/ε}) samples suffice using single-copy adaptive measurements with probability at least 0.99.Source: §5 · p. 22

5.1 Approximate Learning of a State via Bucketing

  • The bucketing algorithm iteratively learns approximate buckets to threshold η, projecting away previously defined buckets at each iteration, following.The analysis assumes minimal eigenvalues eΩ(ε/d).Source: §5 · p. 22, §5.1 · p. 23

5.2 Testing

  • With approximate bucket proxies, if every test indicates equivalence then ρ=σ with probability at least 0.99; a test indicating farness establishes ρ≠σ.The tests compare the states on empirical bucket projections rather than inaccessible ideal buckets.Source: §5.2 · pp. 27–28

5.3 Balancing the Costs of Learning and Testing

  • Choosing η = eΘ(ε/d^(1/4)) balances the learning and testing costs, yielding eO(min{d^(9/4)/ε, d^(3/2)/ε^2}) samples.The threshold is selected by equating the sample complexities of approximate learning via bucketing and testing.Source: §5.2 · p. 28, §5.3 · p. 30
  • The sample-complexity bound improves over testing in trace distance for ε < 1/d^3/4.Source: §5.3 · p. 30
  • O~(min{d^3/2/ε^2, d^9/4/ε}) samples suffice for equivalence testing of two unknown d-dimensional states using single-copy adaptive measurements, with success probability at least 0.99.The theorem states the sample bound for deciding between the two cases specified in the paper’s equivalence-testing problem.Source: §5.3 · p. 30
  • The method learns approximate buckets and uses them as substitutes for the actual buckets during testing, with the proof bounding both learning and testing costs.The proof states that successful testing guarantees 1 − F(ρ, σ) ≤ ε/2.Source: §5.3 · p. 31

6 Mutual Information Testing

The section develops adaptive mutual-information testing by reducing it to independence testing in fidelity, then using learned marginal buckets and piecewise tests. Its analysis balances learning and testing costs up to logarithmic factors.

6 Mutual Information Testing

  • The mutual-information testing result uses single-copy adaptive measurements on ρ_AC and ρ_A ⊗ ρ_C, with success probability at least 0.99.The theorem excerpt states a sample bound whose full expression is not present in the supplied passage.Source: §6 · p. 31

6.1 Reduction to Independence Testing in Fidelity

  • A fidelity-independence tester yields mutual-information testing after preprocessing, with η = O(ε/log(d_A d_C/ε)).The reduction applies to an algorithm distinguishing equality from fidelity at most 1−η.Source: §6.1 · pp. 31–32

6.2 Preprocessing Step

  • Preprocessing applies a channel to the bipartite state and obtains product-state samples from its marginals by partial traces.The channel parameters ν_A and ν_C are chosen later in the analysis.Source: §6.2 · pp. 32–33

6.3 Learning

  • The learning stage approximately learns the unknown state’s marginals σ_A and σ_C to precisions η_A and η_C using Algorithm 2.The learned marginal buckets are used to construct approximate projections for testing.Source: §6.3 · p. 33, §6.4 · p. 34

6.4 Testing

  • The testing stage uses approximate bucket projections, and global depolarization lets the analysis avoid handling very small eigenvalues.The depolarization preserves the product state’s eigenvectors and gives small eigenvalues a lower bound.Source: §6.4 · pp. 34–35

6.5 The Costs of Learning and Testing

  • Learning and testing costs are balanced up to logarithmic factors to obtain the overall sample complexity.The analysis identifies the last bucket learned at precision η_A as the most costly learning component.Source: §6.5 · p. 38

7 Nonadaptive Lower Bounds for Equivalence Testing in Qubits

For qubit equivalence testing with single-copy non-adaptive measurements, distinguishing equal states from states separated by a fidelity gap requires at least eΩ(1/ε^2) samples. The lower bound uses Haar-random instances and follows from how rarely a fixed measurement schedule is strongly aligned with the unknown basis.

7 Nonadaptive Lower Bounds for Equivalence Testing in Qubits

  • With probability at least 0.99, eΩ(1/ε^2) samples are necessary for single-copy non-adaptive equivalence testing, even for qubits.The testing task distinguishes two unknown states that are equal from states with fidelity at most 1−ε.Source: §7 · p. 39
  • The lower-bound instances compare identical state pairs with pairs whose fidelity is at most 1−ε, generated using a Haar-random unitary.The same random unitary defines the states in each pair.Source: §7 · pp. 39–40
  • A fixed non-adaptive schedule has only an O(ε) fraction of measurements strongly aligned with the unknown basis, motivating an eΩ(1/ε^2) sample requirement.The passage explains the scaling as O(1/ε) samples to obtain a strongly biased measurement, multiplied by 1/ε to distinguish the states.Source: §7 · p. 40
  • The proof buckets measurements by bias and bounds their contributions separately before concluding that the transcript distributions have distance at most 1/3.The resulting indistinguishability yields the lower bound via Lemma 7.1.Source: §7 · pp. 39, 40, 46

8 Certification & Equivalence Testing of Quantum Markov Chains

The section gives testing guarantees for quantum Markov chains, distinguishing the known-chain certification setting from equivalence testing when both chains are unknown. Its proof reduces the task to testing the chains’ marginals at precision Θ(ε).

8 Certification & Equivalence Testing of Quantum Markov Chains

  • A quantum Markov chain in this section is a state with conditional mutual information I(A : C|B) equal to zero.The section writes this quantity as a difference of relative entropies involving the ABC, AB, BC, and B states.Source: §8 · p. 46
  • With probability at least 0.99, the theorem gives certification when the comparison Markov chain is known and equivalence testing when both chains are unknown.The theorem states sample sufficiency for the two settings, but the supplied passages do not include the sample-complexity formulas.Source: §8 · p. 46
  • The proof reduces both tasks to testing the relevant marginals at precision Θ(ε), using the certification or equivalence-testing bounds as appropriate.The marginal reduction is attributed to a lemma stating that testing marginals suffices for Markov-chain certification and equivalence testing.Source: §8 · p. 46
Loading 2609.08733v2…