Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Where the Quantum-Memory Advantage Lives: Copy Complexity of the Harmonics of a Shifted Self-Overlap

Özcan Kasal

Published Oct 5, 2026• 0 citations
Publisher

Abstract

This preprint is the second part of a series on Fourier harmonics of shifted overlaps under a U(1) symmetry. The first part (Fourier sectors of shifted overlaps under a compact abelian symmetry, doi:10.5281/zenodo.23137889) introduced the framework: the overlap of two states, one shifted by a group element, decomposes into a finite Fourier series whose coefficients are positive semi-definite sector kernels, read exactly from 2n+1 shifts. That paper made no advantage claim. This paper determines the copy complexity of the diagonal of those kernels for an unknown n-qubit mixed state: the harmonics κ_m(ρ) = ‖A_m ρ‖₂² of the self-overlap Tr(ρ e^{iΔN} ρ e^{−iΔN}), with N the number operator and A_m the projection onto relative charge m. For a reduced state graded by its subsystem charge, these are the replica-two charged moment of the entanglement asymmetry and, normalised, the sector weights of symmetry-resolved operator entanglement. The setting is the model of learning with and without quantum memory of Chen, Cotler, Huang and Li. The results are unconditional. With a quantum memory of one copy, swap tests between a copy and a shifted copy at 2n+1 shifts return every harmonic within ε from O(ε⁻² log(n/δ) + n) pairs of copies. Without quantum memory, and whatever the classical memory and adaptivity, a single harmonic needs Ω(max{ε⁻², √D_{n,m}/ε}) copies, where D_{n,m} = C(n, ⌊(n−m)/2⌋) is the dimension of the charge sectors at distance m; O((2n+1)(ε⁻² + 2^{n/2}ε⁻¹) ln((2n+1)/δ)) single-copy measurements suffice. The separation between learning with and without quantum memory therefore survives symmetry resolution, with its lower bound fixed by the sector dimension rather than by 2ⁿ. The paper locates the boundaries of this separation. It is absent for pure states, where charge statistics suffice, and for n−m bounded, where polynomially many single-copy measurements suffice. It survives unital phase-covariant noise, including charge dephasing of any strength and depolarising noise up to a fixed rate. The bounded-memory bounds of Gong, Haferkamp, Ye and Zhang transfer to each harmonic. A dimension cap shows how far reductions affine in the purity can reach. A final corollary carries the lower bound to the normalised sector weights and to the Rényi-2 entanglement asymmetry: at constant error, estimating the entanglement asymmetry of an n-qubit mixed state from single copies costs Ω(2^{n/2}/n^{1/4}) copies, while two swap tests between pairs of copies return it from O(1) pairs for states of bounded purity. The lower-bound technique is that of Chen, Cotler, Huang and Li (purity testing) and Anshu, Landau and Liu (distributed inner-product estimation), applied through an embedding of a 2^k-dimensional problem across two charge sectors. The purity-testing bound is reproved in an appendix with an explicit constant. No advantage is claimed for states given with a classical description, for which every harmonic is classically computable in polynomial time. The repository contains a numpy implementation, 65 tests tied to the numbered statements, and the script that regenerates every figure and number of the paper from a single seed. Keywords: quantum learning theory; copy complexity; quantum memory; symmetry-resolved entanglement; entanglement asymmetry; modes of asymmetry; swap test; purity estimation; U(1) symmetry

DOI
10.5281/zenodo.23171200

Related papers

Fourier Sectors of Shifted Overlaps under a Compact Abelian Symmetry

Özcan Kasal

A compact abelian group acts unitarily on a finite-dimensional space. This paper proves that the overlap of two states, one shifted by a group element, is a finite Fourier series whose coefficients are positive semi-definite kernels indexed by the isotypic components of the conjugation representation; the coefficient of the trivial character is the inner product of the twirled states, and the sum of the squared moduli of the other coefficients is the variance of the overlap over the group. For the circle the series is a trigonometric polynomial whose degree is bounded by the total charge, so it is determined exactly by its values at finitely many equally spaced shifts. The same decomposition is applied to a reset channel, a fixed unitary that absorbs encoded inputs one at a time into a hidden register and discards the input between steps. Its readout under a common shift of the inputs is a finite Fourier series whose zero mode is the readout of the jointly twirled input; this need not equal the readout of inputs twirled one at a time, and an explicit Clifford channel separates the two. The degree of the readout is at most the charge bound times the number of steps, and for every charge bound an explicit channel attains it. Every coefficient can be estimated from overlaps measured at finitely many shifts, with a number of runs quadratic in the inverse error and logarithmic in the number of coefficients, and a charge sector of an encoded state can be read at the amplitude level by exact phase estimation of the charge followed by a Hadamard test. Sector kernels of product encodings and Fourier sectors of Clifford channels with Pauli readout are shown to be classically computable in polynomial time. The paper claims no quantum advantage. A final section carries the Fourier argument to the signature of a piecewise-linear path, read as a vector in a Fock space, and decomposes the signature kernel under rotation of the increments into harmonics that are themselves kernels.

•Oct 4, 2026•0 citations

The Shift Winding: An Integer Invariant of a Pair of Quantum States that Phase-Insensitive Overlap Kernels Cannot See

Özcan Kasal

For two pure states ψ, φ of an n-qubit register, the overlap after a common phase shift, g(θ) = ⟨ψ|e^{iθN}|φ⟩ with N the number operator, is a trigonometric polynomial of degree at most n. When g does not vanish on the circle, its winding number W(ψ, φ), the shift winding of the pair, counts the zeros in the unit disk of the polynomial whose coefficients are the overlaps within each Hamming-weight sector. W is invariant under independent global phases, under common shifts and under every joint unitary that commutes with N. Along a path of pairs it can change only where some common shift makes the two states orthogonal. The sector kernels are blind to W. These kernels are the Fourier coefficients of |g|², measured by swap tests on a shift grid; their diagonal values are the multiple-quantum-coherence intensities of NMR. An antiunitary mirror preserves every kernel and sends W to n − W. Product states: W counts the qubits with h_q + h′_q > 1. Spin-coherent reference: W counts the Majorana stars of the partner's symmetric part beyond a circle of latitude. The kernels are then the Fourier coefficients of the partner's Husimi function on the reference's circle of latitude. Haar-random partner: averaged over the partner, W(ψ, ·) equals the mean excitation number ⟨ψ|N|ψ⟩. For the reference |+⟩^⊗n, its variance is ζ(3/2)/(8√π)·√n to leading order. With one control qubit and copies of the two states, a certified protocol returns W exactly or abstains, using O(n log²n log(n/δ)/ν²) copy pairs. The margin ν is inverse-polynomial exactly for pairs that stay close under every common shift, and exponentially small for random partners. Classically, W is efficiently computable for product, matrix-product and computationally tractable states. Deciding W for circuit-prepared pairs at constant margin is BQP-complete. We claim no quantum advantage. 13 pages, 3 figures, 2 tables. The deposit includes the LaTeX source and a reference implementation in numpy. Its tests cover every theorem, proposition, lemma and corollary, and all figures and numbers are regenerated from a fixed seed.

•Oct 15, 2026•0 citations

Causal quantum-channel simulation: memory beyond entropy

Seth Douglas, Nidhal Mghirbi

How much memory does it take to apply the same quantum channel many times, when each output must be released before the next input arrives and every retained qubit counts? One-use invariants do not decide it. Two explicit channels on dimension 1664 have identical normalized Choi spectra (32 eigenvalues 1/32), the same maximal complementary entropy 5, and zero asymptotic purity cost. At the same optimal exchange rate, one is implemented exactly with five memory qubits for any number of uses, while the other needs Omega(n^(1/(2 log_2(107)+2))) memory qubits for n uses, at every fixed error at most 1/16 and whatever purity is available; memory O(n^(1/3) log^(4/3) n) suffices for it. The hard channel is built from Houghton's group H_3. Behind the example is a general theory: the achievable exchange and purity rates, the purity cost kappa, which vanishes exactly on the closure of finite tracial factorizations, and memory bounds from how well a channel's environment is approximated by finite ones, and, for channels built from finite presentations, from the approximation profile of the group. Version 1.1 adds where the expensive channels lie: on the relative boundary of the closure; any fixed depolarizing admixture brings them down to polylogarithmic memory at the rank rate; on a face containing the Houghton channel a single moment of a trace on the group decides expense; and one free fermion per site already forces polynomial memory. Version 1.1.1 adds a map of what the main separation depends on (published inputs, companion results and new arguments), sets finite-budget and asymptotic-rate statements side by side, cites the companion papers at their published versions, pins the tested software versions, and makes every check refuse to run under optimized Python. The mathematical results are unchanged. Version 1.1.2 corrects attributions and makes two headline statements precise. The separation of Theorem A is stated at the exchange budget 5n/2, and the channels that need polynomial memory at every exchange rate are those with purity limited to O(log n). Credits added or corrected: Bisio, D'Ariano, Perinotti and Chiribella, and Bisio, D'Ariano, Perinotti and Sedlak; Boes et al. for the square-root dephasing construction; Lie, Son, Boes, Ng and Wilming for the exact case of the tracialization lemma; Faist, Berta and Brandao for the relation to the thermodynamic capacity; Haagerup, Musat and Rordam for the moment criteria; Thoma, Johnson, Watrous, Horodecki-Oppenheim-Winter and Lie-Jeong; Cornulier for the Baumslag-Solitar bound. Known results are moved out of numbered statements. The mathematical results and the numbering are unchanged. All operational bounds use complete-experiment error against adaptive observers with quantum references. The general rate-region achievability result uses a cited closed-device theorem; the explicit separation does not. This preprint archive includes the PDF, TeX source, finite verification scripts, and scoped Lean arithmetic proofs. The artifacts do not formally verify the entire manuscript; their scope and external dependencies are documented in verification/README.md.

•Sep 29, 2026•1 citation

The power and limitations of restricted quantum learning models

Louis Schatzki

Quantum technologies have rapidly advanced over the past decade or so.However, noise and decoherence are still challenges.At the same time, quantum learning theory has quickly grown and many techniques have been developed with applications in verifying and benchmarking quantum devices.However, known generic but optimal protocols may require entangled measurements across many copies of a state, rendering experimental implementations rather difficult.With this mind, it is interesting to ask what learning tasks can and cannot be achieved with limited models of measurements, a question which has received much attention in recent years.In this thesis we answer several questions in this vein.First, we consider entangled versus separable measurements for exactly learning a function c ∈ C from a quantum example state |c⟩ = 1 √ 2 nx |x, c(x)⟩.We show that, if T copies suffice to learn f using entangled measurements, O(nT 2 ) copies suffice to learn f using only separable measurements.Second, we study the Quantum Statistical Query model.We exhibit a concept class C based of degree-2 functions with an exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise).This proves the "quantum analogue" of the seminal result of Blum, Kalai, & Wasserman.[1] that separates classical SQ learning from classical PAC learning with classification noise.To obtain these bounds, we introduce a quantum statistical query dimension (QSD).We prove superpolynomial QSQ lower bounds for testing purity of quantum states, reconstructing a state via shadow tomography, learning coset states for the Abelian hidden subgroup problem, approximating degree-2 functions, finding planted bi-cliques, and learning the output states of Clifford circuits of depth polylog(n).We also show that an extension of QSD characterizes the complexity of general search problems.Lastly, we give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model.Prior works by Quek et al. [2], Hinsche et al. [3], and Nietner et al. [4] proved analogous results assuming diagonal measurements and our work removes this assumption.Next, we consider the fundamental task of distributed inner product estimation when allowed limited communication.Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩ , |ϕ⟩ respectively.They are allowed to send q qubits to one another with the goal of estimating |⟨ψ|ϕ⟩| 2 up to constant additive error.We show that k = Θ( √ 2 n-q ) copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC'22) who considered the case when q = 0).Additionally, we also consider the task when the goal of the players is to estimate |⟨ψ|M |ϕ⟩| 2 , for arbitrary Hermitian M .For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M |ϕ⟩| 2 when using only classical communication.Returning to separable vs entangled measurements, we make progress on proving a hierarchy of copycomplexity separations.To that end, we prove that estimating Tr[ρ k ], for k a constant, requires Ω(log d) samples with (k -1)-copy measurements.By contrast, O(1) samples suffice with k-copy measurements.To obtain our bounds, we extend Harrow's [5] method of PPT constraints on sums of permutations.This thesis and the work within would not have been possible without the support and encouragement of many people.I would like to start with my PhD advisor Eric Chitambar, whose support and guidance has been invaluable over the past five years.I have been fortunate to have had the opportunity to spend time at both Los Alamos and IBM while a PhD student and want to thank my collaborators and friends at those institutions.In particular, I want to express my gratitude to my close collaborations and mentors Srinivasan

•Aug 25, 2025•0 citations

How fast does quantum copying become estimation? A sharp finite-copy law for phase states

M. Weldon

Copying an unknown quantum state into many approximate copies is known to become equivalent to estimating it and re-preparing: the best measure-and-prepare copier approaches the best quantum copier as the number of copies grows. We determine how fast. For equatorial qubit states, one input copy and m output copies, judged by the global fidelity, we prove F_EB/F_coh = 1 − 1/√(2m) + O(1/m). For phase states on d levels we prove, with explicit constants, the law 1 − F_EB/F_coh = (d − 1)/√(2m) + O(1/m), confirmed by exact computations up to m = 400; for qubits with T input copies the gap is √2·σ_T/√m, proved with explicit constants for T = 2, 3 (the upper bound conditionally on the optimality of the flat seed, R0(T); the lower bound unconditionally). The measure-and-prepare copier's deficit is the ground-state energy of a harmonic oscillator, one quantum per unknown phase. The exact quantum fidelity has plateaus at m = kd and kd + 1 (m = kd + 1 is the economical point). Numerical results suggest a period-d modulation of the ratio at order 1/m; a proof of its next-order coefficient remains open. This complements the known universality of the cloning fidelity itself, which depends only on the number of free parameters: within the phase-state family, the leading gap coefficient counts the independent phase directions. The classical values rest on the flat-seed theorem of the companion Paper 5, and the several-copy quantum values on the reduced coherent dual of the companion Paper 5. Core lemmas of the qubit proof and its explicit upper-bound constants are machine-checked in Lean 4; the remaining steps are proved on paper and independently refereed.

•Nov 1, 2026•0 citations

The Parity-Entanglement Bound

Ram Kirpitch

In the Page–Wootters relational-time framework a ℤ₂ parity constraint (P_C ⊗ P_S)|Ψ⟩ = +|Ψ⟩ ties a clock C to a system S. We show that the constraint controls one specific term of the entanglement entropy — the sector (charge) entropy — which obeys H({p_e, p_o}) ≤ 1 bit with equality iff the two parity sectors are equally weighted, for every system size N, every clock size k, and every state in the constrained subspace. The familiar value I(C;S) = 2 bits is recovered exactly when the complementary configurational term vanishes, i.e. on the rank-2 family, to which the uniform ℤ₂ ground state belongs; there I = 2 bits independently of N, of k and of which qubits form the clock. We further prove an exact complementarity V² + P² = 1 between the clock–system fringe visibility and the sector predictability. On IBM quantum hardware we measure the quantity the theory actually predicts: the weight of the reduced clock state inside the rank-2 subspace. For an 8-dimensional (k = 3) clock register at N = 5 we find 0.920, against 0.250 expected if the register carried the naive 2k = 6 bits; the two surviving eigenvalues are 0.445 and 0.475. A depolarisation parameter calibrated from an independent stabilizer fidelity witness returns I = 1.998, 1.999, 1.997 bits for k = 1, 2, 3. A separable control state is included: a single-basis clock-marginal estimator returns 1.9991 bits on it, while the tomographic estimator used here returns 0.835 bits and V² + P² = 0.0005, so the protocol separates the constrained state from a classical mixture.

•May 24, 2026•1 citation
This preprint is the second part of a series on Fourier harmonics of shifted overlaps under a U(1) symmetry. The first part (Fourier sectors of shifted overlaps under a compact abelian symmetry, doi:10.5281/zenodo.23137889) introduced the framework: the overlap of two states, one shifted by a group element, decomposes into a finite Fourier series whose coefficients are positive semi-definite sector kernels, read exactly from 2n+1 shifts. That paper made no advantage claim. This paper determines the copy complexity of the diagonal of those kernels for an unknown n-qubit mixed state: the harmonics κ_m(ρ) = ‖A_m ρ‖₂² of the self-overlap Tr(ρ e^{iΔN} ρ e^{−iΔN}), with N the number operator and A_m the projection onto relative charge m. For a reduced state graded by its subsystem charge, these are the replica-two charged moment of the entanglement asymmetry and, normalised, the sector weights of symmetry-resolved operator entanglement. The setting is the model of learning with and without quantum memory of Chen, Cotler, Huang and Li. The results are unconditional. With a quantum memory of one copy, swap tests between a copy and a shifted copy at 2n+1 shifts return every harmonic within ε from O(ε⁻² log(n/δ) + n) pairs of copies. Without quantum memory, and whatever the classical memory and adaptivity, a single harmonic needs Ω(max{ε⁻², √D_{n,m}/ε}) copies, where D_{n,m} = C(n, ⌊(n−m)/2⌋) is the dimension of the charge sectors at distance m; O((2n+1)(ε⁻² + 2^{n/2}ε⁻¹) ln((2n+1)/δ)) single-copy measurements suffice. The separation between learning with and without quantum memory therefore survives symmetry resolution, with its lower bound fixed by the sector dimension rather than by 2ⁿ. The paper locates the boundaries of this separation. It is absent for pure states, where charge statistics suffice, and for n−m bounded, where polynomially many single-copy measurements suffice. It survives unital phase-covariant noise, including charge dephasing of any strength and depolarising noise up to a fixed rate. The bounded-memory bounds of Gong, Haferkamp, Ye and Zhang transfer to each harmonic. A dimension cap shows how far reductions affine in the purity can reach. A final corollary carries the lower bound to the normalised sector weights and to the Rényi-2 entanglement asymmetry: at constant error, estimating the entanglement asymmetry of an n-qubit mixed state from single copies costs Ω(2^{n/2}/n^{1/4}) copies, while two swap tests between pairs of copies return it from O(1) pairs for states of bounded purity. The lower-bound technique is that of Chen, Cotler, Huang and Li (purity testing) and Anshu, Landau and Liu (distributed inner-product estimation), applied through an embedding of a 2^k-dimensional problem across two charge sectors. The purity-testing bound is reproved in an appendix with an explicit constant. No advantage is claimed for states given with a classical description, for which every harmonic is classically computable in polynomial time. The repository contains a numpy implementation, 65 tests tied to the numbered statements, and the script that regenerates every figure and number of the paper from a single seed. Keywords: quantum learning theory; copy complexity; quantum memory; symmetry-resolved entanglement; entanglement asymmetry; modes of asymmetry; swap test; purity estimation; U(1) symmetry
A compact abelian group acts unitarily on a finite-dimensional space. This paper proves that the overlap of two states, one shifted by a group element, is a finite Fourier series whose coefficients are positive semi-definite kernels indexed by the isotypic components of the conjugation representation; the coefficient of the trivial character is the inner product of the twirled states, and the sum of the squared moduli of the other coefficients is the variance of the overlap over the group. For the circle the series is a trigonometric polynomial whose degree is bounded by the total charge, so it is determined exactly by its values at finitely many equally spaced shifts. The same decomposition is applied to a reset channel, a fixed unitary that absorbs encoded inputs one at a time into a hidden register and discards the input between steps. Its readout under a common shift of the inputs is a finite Fourier series whose zero mode is the readout of the jointly twirled input; this need not equal the readout of inputs twirled one at a time, and an explicit Clifford channel separates the two. The degree of the readout is at most the charge bound times the number of steps, and for every charge bound an explicit channel attains it. Every coefficient can be estimated from overlaps measured at finitely many shifts, with a number of runs quadratic in the inverse error and logarithmic in the number of coefficients, and a charge sector of an encoded state can be read at the amplitude level by exact phase estimation of the charge followed by a Hadamard test. Sector kernels of product encodings and Fourier sectors of Clifford channels with Pauli readout are shown to be classically computable in polynomial time. The paper claims no quantum advantage. A final section carries the Fourier argument to the signature of a piecewise-linear path, read as a vector in a Fock space, and decomposes the signature kernel under rotation of the increments into harmonics that are themselves kernels.
For two pure states ψ, φ of an n-qubit register, the overlap after a common phase shift, g(θ) = ⟨ψ|e^{iθN}|φ⟩ with N the number operator, is a trigonometric polynomial of degree at most n. When g does not vanish on the circle, its winding number W(ψ, φ), the shift winding of the pair, counts the zeros in the unit disk of the polynomial whose coefficients are the overlaps within each Hamming-weight sector. W is invariant under independent global phases, under common shifts and under every joint unitary that commutes with N. Along a path of pairs it can change only where some common shift makes the two states orthogonal. The sector kernels are blind to W. These kernels are the Fourier coefficients of |g|², measured by swap tests on a shift grid; their diagonal values are the multiple-quantum-coherence intensities of NMR. An antiunitary mirror preserves every kernel and sends W to n − W. Product states: W counts the qubits with h_q + h′_q > 1. Spin-coherent reference: W counts the Majorana stars of the partner's symmetric part beyond a circle of latitude. The kernels are then the Fourier coefficients of the partner's Husimi function on the reference's circle of latitude. Haar-random partner: averaged over the partner, W(ψ, ·) equals the mean excitation number ⟨ψ|N|ψ⟩. For the reference |+⟩^⊗n, its variance is ζ(3/2)/(8√π)·√n to leading order. With one control qubit and copies of the two states, a certified protocol returns W exactly or abstains, using O(n log²n log(n/δ)/ν²) copy pairs. The margin ν is inverse-polynomial exactly for pairs that stay close under every common shift, and exponentially small for random partners. Classically, W is efficiently computable for product, matrix-product and computationally tractable states. Deciding W for circuit-prepared pairs at constant margin is BQP-complete. We claim no quantum advantage. 13 pages, 3 figures, 2 tables. The deposit includes the LaTeX source and a reference implementation in numpy. Its tests cover every theorem, proposition, lemma and corollary, and all figures and numbers are regenerated from a fixed seed.
How much memory does it take to apply the same quantum channel many times, when each output must be released before the next input arrives and every retained qubit counts? One-use invariants do not decide it. Two explicit channels on dimension 1664 have identical normalized Choi spectra (32 eigenvalues 1/32), the same maximal complementary entropy 5, and zero asymptotic purity cost. At the same optimal exchange rate, one is implemented exactly with five memory qubits for any number of uses, while the other needs Omega(n^(1/(2 log_2(107)+2))) memory qubits for n uses, at every fixed error at most 1/16 and whatever purity is available; memory O(n^(1/3) log^(4/3) n) suffices for it. The hard channel is built from Houghton's group H_3. Behind the example is a general theory: the achievable exchange and purity rates, the purity cost kappa, which vanishes exactly on the closure of finite tracial factorizations, and memory bounds from how well a channel's environment is approximated by finite ones, and, for channels built from finite presentations, from the approximation profile of the group. Version 1.1 adds where the expensive channels lie: on the relative boundary of the closure; any fixed depolarizing admixture brings them down to polylogarithmic memory at the rank rate; on a face containing the Houghton channel a single moment of a trace on the group decides expense; and one free fermion per site already forces polynomial memory. Version 1.1.1 adds a map of what the main separation depends on (published inputs, companion results and new arguments), sets finite-budget and asymptotic-rate statements side by side, cites the companion papers at their published versions, pins the tested software versions, and makes every check refuse to run under optimized Python. The mathematical results are unchanged. Version 1.1.2 corrects attributions and makes two headline statements precise. The separation of Theorem A is stated at the exchange budget 5n/2, and the channels that need polynomial memory at every exchange rate are those with purity limited to O(log n). Credits added or corrected: Bisio, D'Ariano, Perinotti and Chiribella, and Bisio, D'Ariano, Perinotti and Sedlak; Boes et al. for the square-root dephasing construction; Lie, Son, Boes, Ng and Wilming for the exact case of the tracialization lemma; Faist, Berta and Brandao for the relation to the thermodynamic capacity; Haagerup, Musat and Rordam for the moment criteria; Thoma, Johnson, Watrous, Horodecki-Oppenheim-Winter and Lie-Jeong; Cornulier for the Baumslag-Solitar bound. Known results are moved out of numbered statements. The mathematical results and the numbering are unchanged. All operational bounds use complete-experiment error against adaptive observers with quantum references. The general rate-region achievability result uses a cited closed-device theorem; the explicit separation does not. This preprint archive includes the PDF, TeX source, finite verification scripts, and scoped Lean arithmetic proofs. The artifacts do not formally verify the entire manuscript; their scope and external dependencies are documented in verification/README.md.
Quantum technologies have rapidly advanced over the past decade or so.However, noise and decoherence are still challenges.At the same time, quantum learning theory has quickly grown and many techniques have been developed with applications in verifying and benchmarking quantum devices.However, known generic but optimal protocols may require entangled measurements across many copies of a state, rendering experimental implementations rather difficult.With this mind, it is interesting to ask what learning tasks can and cannot be achieved with limited models of measurements, a question which has received much attention in recent years.In this thesis we answer several questions in this vein.First, we consider entangled versus separable measurements for exactly learning a function c ∈ C from a quantum example state |c⟩ = 1 √ 2 nx |x, c(x)⟩.We show that, if T copies suffice to learn f using entangled measurements, O(nT 2 ) copies suffice to learn f using only separable measurements.Second, we study the Quantum Statistical Query model.We exhibit a concept class C based of degree-2 functions with an exponential separation between QSQ learning and quantum learning with entangled measurements (even in the presence of noise).This proves the "quantum analogue" of the seminal result of Blum, Kalai, & Wasserman.[1] that separates classical SQ learning from classical PAC learning with classification noise.To obtain these bounds, we introduce a quantum statistical query dimension (QSD).We prove superpolynomial QSQ lower bounds for testing purity of quantum states, reconstructing a state via shadow tomography, learning coset states for the Abelian hidden subgroup problem, approximating degree-2 functions, finding planted bi-cliques, and learning the output states of Clifford circuits of depth polylog(n).We also show that an extension of QSD characterizes the complexity of general search problems.Lastly, we give an unconditional separation between weak and strong error mitigation and prove lower bounds for learning distributions in the QSQ model.Prior works by Quek et al. [2], Hinsche et al. [3], and Nietner et al. [4] proved analogous results assuming diagonal measurements and our work removes this assumption.Next, we consider the fundamental task of distributed inner product estimation when allowed limited communication.Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩ , |ϕ⟩ respectively.They are allowed to send q qubits to one another with the goal of estimating |⟨ψ|ϕ⟩| 2 up to constant additive error.We show that k = Θ( √ 2 n-q ) copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC'22) who considered the case when q = 0).Additionally, we also consider the task when the goal of the players is to estimate |⟨ψ|M |ϕ⟩| 2 , for arbitrary Hermitian M .For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M |ϕ⟩| 2 when using only classical communication.Returning to separable vs entangled measurements, we make progress on proving a hierarchy of copycomplexity separations.To that end, we prove that estimating Tr[ρ k ], for k a constant, requires Ω(log d) samples with (k -1)-copy measurements.By contrast, O(1) samples suffice with k-copy measurements.To obtain our bounds, we extend Harrow's [5] method of PPT constraints on sums of permutations.This thesis and the work within would not have been possible without the support and encouragement of many people.I would like to start with my PhD advisor Eric Chitambar, whose support and guidance has been invaluable over the past five years.I have been fortunate to have had the opportunity to spend time at both Los Alamos and IBM while a PhD student and want to thank my collaborators and friends at those institutions.In particular, I want to express my gratitude to my close collaborations and mentors Srinivasan
Copying an unknown quantum state into many approximate copies is known to become equivalent to estimating it and re-preparing: the best measure-and-prepare copier approaches the best quantum copier as the number of copies grows. We determine how fast. For equatorial qubit states, one input copy and m output copies, judged by the global fidelity, we prove F_EB/F_coh = 1 − 1/√(2m) + O(1/m). For phase states on d levels we prove, with explicit constants, the law 1 − F_EB/F_coh = (d − 1)/√(2m) + O(1/m), confirmed by exact computations up to m = 400; for qubits with T input copies the gap is √2·σ_T/√m, proved with explicit constants for T = 2, 3 (the upper bound conditionally on the optimality of the flat seed, R0(T); the lower bound unconditionally). The measure-and-prepare copier's deficit is the ground-state energy of a harmonic oscillator, one quantum per unknown phase. The exact quantum fidelity has plateaus at m = kd and kd + 1 (m = kd + 1 is the economical point). Numerical results suggest a period-d modulation of the ratio at order 1/m; a proof of its next-order coefficient remains open. This complements the known universality of the cloning fidelity itself, which depends only on the number of free parameters: within the phase-state family, the leading gap coefficient counts the independent phase directions. The classical values rest on the flat-seed theorem of the companion Paper 5, and the several-copy quantum values on the reduced coherent dual of the companion Paper 5. Core lemmas of the qubit proof and its explicit upper-bound constants are machine-checked in Lean 4; the remaining steps are proved on paper and independently refereed.
In the Page–Wootters relational-time framework a ℤ₂ parity constraint (P_C ⊗ P_S)|Ψ⟩ = +|Ψ⟩ ties a clock C to a system S. We show that the constraint controls one specific term of the entanglement entropy — the sector (charge) entropy — which obeys H({p_e, p_o}) ≤ 1 bit with equality iff the two parity sectors are equally weighted, for every system size N, every clock size k, and every state in the constrained subspace. The familiar value I(C;S) = 2 bits is recovered exactly when the complementary configurational term vanishes, i.e. on the rank-2 family, to which the uniform ℤ₂ ground state belongs; there I = 2 bits independently of N, of k and of which qubits form the clock. We further prove an exact complementarity V² + P² = 1 between the clock–system fringe visibility and the sector predictability. On IBM quantum hardware we measure the quantity the theory actually predicts: the weight of the reduced clock state inside the rank-2 subspace. For an 8-dimensional (k = 3) clock register at N = 5 we find 0.920, against 0.250 expected if the register carried the naive 2k = 6 bits; the two surviving eigenvalues are 0.445 and 0.475. A depolarisation parameter calibrated from an independent stabilizer fidelity witness returns I = 1.998, 1.999, 1.997 bits for k = 1, 2, 3. A separable control state is included: a single-basis clock-marginal estimator returns 1.9991 bits on it, while the tomographic estimator used here returns 0.835 bits and V² + P² = 0.0005, so the protocol separates the constrained state from a classical mixture.