Source-linked AI summary
Quantum state restoration and single-copy tomography
Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Daniel Nagaj, Peter Shor
TL;DR
A single copy of an unknown quantum state limits what can be learned, while a verifier alone does not allow efficient preparation or learning. The paper combines a copy with verification to restore states and perform tomography, limiting a large class of quantum money schemes.
Problem
A single copy of an unknown state limits information extraction, and verification alone does not allow efficient preparation or learning.
Source: §I · p. 1Method
The paper combines a single copy with a state verifier to restore small subsystems and perform single-copy tomography, including estimation of general POVM statistics.
Source: §I · pp. 1–2Results
Restoration and tomography algorithms operate in time polynomial in the subsystem dimension or, for general POVM statistics, the number of operators.
Source: §I · pp. 1–2Takeaways & Limitations
These algorithms rule out a large class of possible quantum money schemes, while the existence of secure protocols remains open.
Source: §I · p. 2
Abstract
from arXiv · showhide
Given a single copy of a quantum state |ψ>, the no cloning theorem greatly limits the amount of information which can be extracted from it. On the other hand, given only a procedure which verifies the state, for example access to a measurement {1-|psi><psi|, |psi><psi|}, we cannot prepare |psi> or learn any information about it in polynomial time. In this paper, we consider the scenario in which we are given both a single copy of |psi> and the ability to verify it. We show that in this setting, we can do several things efficiently. We present a new algorithm called quantum state restoration which allows us to copy small subsystems of |psi>. In addition, we present algorithms that can perform tomography on small subsystems of |psi>, and we show to use these algorithms to estimate the statistics of any POVM acting on |psi> in time polynomial in the number of outcomes of the POVM. These algorithms put severe limitations on possible quantum money schemes.
I. INTRODUCTION
A single copy of an unknown state limits what can be learned, but pairing it with a verifier enables efficient recovery and measurement algorithms. The paper applies these methods to small-subsystem tomography and quantum-money security.
I. INTRODUCTION
- A single copy of an unknown quantum state cannot reveal even the description of a small part, while access to a verifier enables new algorithms.The verifier is a black-box measurement of P = |ψ⟩⟨ψ|.Source: §I · p. 1
- Quantum state restoration sets aside a small subsystem and uses the verifier to recover |ψ⟩, including for entangled states.The input may be the reduced density matrix on subsystem A; the algorithm outputs the full state.Source: §I · pp. 1–2
- Restoration can produce copies of a small subsystem for tomography, while specialized algorithms estimate general POVM statistics in time polynomial in the number of operators.The tomography algorithms run in time polynomial in the dimension of the subsystem being studied.Source: §I · pp. 1–2
- The algorithms rule out a large class of possible quantum money schemes, including product-state money that can be efficiently copied with its verifier.The paper leaves the existence of secure quantum money protocols an open question.Source: §I · p. 2
II. QUANTUM STATE RESTORATION
- For subsystem B of dimension d and state Schmidt rank χ, restoration succeeds in an expected χd iterations, including when Schmidt coefficients are unequal.Each unsuccessful attempt discards B while retaining support on the Schmidt basis of subsystem A.Source: §II · p. 3
A. Running Time of Quantum State Restoration
The expected number of iterations for quantum state restoration is χ·d, regardless of the Schmidt probabilities. Although iterations can reach low-weight Schmidt-basis states with lower success chances, those effects cancel in expectation.
A. Running Time of Quantum State Restoration
- The expected number of restoration iterations is χ·d, regardless of the Schmidt probabilities.When the probabilities are unequal, low-success states are less likely to be reached, exactly canceling their slower restoration.Source: A. Running Time of Quantum State… · p. 3
- Unequal Schmidt probabilities can lead to bad states with reduced per-iteration success, but their lower likelihood exactly offsets that slowdown.The figure describes conditional restoration probabilities and identifies the first two flat regions as metastable and the third as stable.Source: A. Running Time of Quantum State… · p. 3, Figure 1 · p. 4
- The proof defines two maps and analyzes the expected measurement count by conditioning on measurement outcomes.The maps describe unnormalized states conditioned on outcomes, whose sequences determine measurement probabilities.Source: A. Running Time of Quantum State… · pp. 3–5
III. SINGLE-COPY TOMOGRAPHY AND ESTIMATION OF MEASUREMENT STATISTICS
The paper presents approaches for single-copy tomography of subsystems of a verifiable state and for estimating general POVM statistics. These methods use state restoration or specialized algorithms, with the general-POVM procedure reducing estimation to subsystem measurement in an orthogonal basis.
III. SINGLE-COPY TOMOGRAPHY AND ESTIMATION OF MEASUREMENT STATISTICS
- Quantum state restoration can prepare unentangled states with subsystem density matrix ρB for standard tomography, or sample probabilities in an orthonormal basis directly.The specialized algorithms also estimate those probabilities one at a time using two-outcome measurements.Source: §III · p. 5
- A general POVM can be reduced to measuring a subsystem in an orthogonal basis, allowing the subsystem-estimation algorithms to estimate its statistics.The construction applies a unitary and relates outcome probabilities to measurement of register B.Source: §III · pp. 5–6
- Theorem 2 estimates all outcome probabilities of an efficiently implementable d-outcome POVM while returning an undamaged copy of the input state.The algorithm uses an expected number of calls to both the measurement oracle and the POVM; the supplied passage does not include the bound.Source: §III · p. 6
- An informationally complete POVM on a subsystem can be estimated using Theorem 2 to perform subsystem tomography.The paper notes that some tomography algorithms are faster than quantum state restoration.Source: §III · pp. 5–6
A. Using quantum state restoration to estimate measurement statistics
The restoration-based estimator repeatedly measures subsystem B and restores the state to estimate outcome probabilities. Its error analysis uses independent observations, Hoeffding’s inequality, and a union bound.
A. Using quantum state restoration to estimate measurement statistics
- The estimator counts observations of each outcome among N trials, with independent indicator variables for each fixed outcome.The observations follow subsystem measurement and restoration.Source: A. Using quantum state restoration to… · p. 6
- Hoeffding’s inequality bounds each outcome-estimation error, and a union bound extends the guarantee across outcomes.The cited analysis uses the bound to control the probability that any estimate exceeds the error threshold.Source: A. Using quantum state restoration to… · p. 6
- Each of N restoration repetitions takes an expected χ·d time, and the section derives the total expected number of uses of P for estimating the probabilities.The supplied passage truncates before giving the total-use expression.Source: A. Using quantum state restoration to… · p. 6
B. Improved algorithms to estimate measurement statistics
The paper describes two improved single-copy algorithms for estimating measurement statistics, based on Jordan’s lemma and QMA amplification schemes. They estimate all outcome probabilities within the specified precision with high probability.
B. Improved algorithms to estimate measurement statistics
- The algorithms estimate each outcome probability separately, repeating the procedure for every i.The supplied passage introduces a fixed outcome i and then states that the procedure is repeated for each value.Source: B. Improved algorithms to estimate… · p. 7
- The two algorithms compute q_i more efficiently than quantum state restoration for chosen precision δ and error probability ϵ.They are based on Jordan’s lemma and QMA amplification schemes.Source: B. Improved algorithms to estimate… · p. 7
- Both improved algorithms estimate every q_i within δ with probability at least 1−ϵ.The section summarizes their running times as a function of δ and ϵ in Table I.Source: B. Improved algorithms to estimate… · p. 7
1. Alternating Projections
Alternating projections estimate each measurement probability q_i by repeatedly measuring Q_i and the verifier P, then counting transitions between outcomes. The procedure recovers |ψ⟩ after a failed P measurement and uses an expected number of P measurements bounded by 2N for one estimate.
1. Alternating Projections
- After a failed measurement of P, the algorithm alternates Q_i and P measurements until it recovers |ψ⟩.It repeats the process to estimate the q_i values one at a time.Source: §1 · p. 8
- The estimator counts adjacent outcome changes, because the probability that successive outcomes match is q_i.After 2N alternating measurements, it uses the number of zeroes among the differences between adjacent outcome bits to estimate q_i.Source: §1 · p. 8
- The expected number of uses of P for one estimate is at most 2N.The bound follows by treating alternating measurements as a symmetric random walk and bounding the probability of any transition in N steps by a union bound.Source: §1 · p. 8
2. An improved algorithm using phase estimation
The phase-estimation algorithm estimates the measurement probabilities q_i and restores |ψ⟩ after failed verifier measurements. It uses quadratically fewer measurements of P than the previous two algorithms.
2. An improved algorithm using phase estimation
- The phase-estimation algorithm requires quadratically fewer measurements of P than the previous two algorithms.Its analysis bounds the expected number of phase-estimation-and-P-measurement iterations by 2r.Source: §2 · pp. 8, 10
- The algorithm estimates q_i by phase-estimating W_i and uses the resulting phase to estimate q_i = cos^2 θ_i.It repeats the estimation and takes a median to reduce failure probability.Source: §2 · p. 9
- After a failed measurement of P, the algorithm repeats phase estimation followed by P measurement until it recovers |ψ⟩.The algorithm is designed to lower the failure probability while recovering the state at completion.Source: §2 · p. 9
- The resulting estimates of all q_i are within δ of their correct values with probability at least 1 − ϵ.The phase estimates are combined using a median, with the success guarantee applying across all i.Source: §2 · p. 11
C. Performance comparison for estimating measurement statistics
The three algorithms estimate the probabilities q_i within δ with probability at least 1 − ϵ. The alternatives to state restoration perform better as a function of d, and phase estimation has a further advantage as δ approaches zero.
C. Performance comparison for estimating measurement statistics
- All three algorithms estimate each q_i within δ of its correct value with probability at least 1 − ϵ.Their expected running-time scalings are summarized in Table I.Source: C. Performance comparison for… · p. 11
- As δ → 0, phase estimation performs quadratically better than both other algorithms.The comparison concerns the expected number of measurements of P summarized in Table I.Source: C. Performance comparison for… · p. 11
- Both alternative tomography algorithms outperform state restoration as a function of d, while state restoration is conceptually simplest and may suffice for most purposes.The comparison assumes χ increases as a function of d.Source: C. Performance comparison for… · p. 11
IV. APPLICATIONS OF QUANTUM STATE RESTORATION AND SINGLE-COPY TOMOGRAPHY
This section presents applications of quantum state restoration and single-copy tomography.
IV. APPLICATIONS OF QUANTUM STATE RESTORATION AND SINGLE-COPY TOMOGRAPHY
- The section concerns applications of quantum state restoration and single-copy tomography.Source: §IV · p. 11
A. Breaking quantum money
Publicly verifiable quantum money gives would-be forgers access to the verification procedure. Projector-verifier protocols must withstand single-copy tomography, because the resulting measurement statistics must not be useful to a counterfeiter.
A. Breaking quantum money
- Earlier quantum money protocols kept verification secret, whereas publicly verifiable schemes give everyone, including would-be forgers, access to it.The paper identifies projector verifiers as a relevant setting for these schemes.Source: A. Breaking quantum money · p. 12
- With a projector verifier, an adversary can use single-copy tomography to learn statistics of efficiently implementable, small-outcome measurements on the money state.The protocol must be designed so those statistics are not useful to a counterfeiter.Source: A. Breaking quantum money · p. 12
- Any quantum money protocol whose verifier is a projector must be designed to withstand attacks based on single-copy tomography.The paper states this as a corollary of Theorem 2.Source: A. Breaking quantum money · p. 12
B. Studying ground states of many-body Hamiltonians
Single-copy tomography can support measurements on small parts of many-body ground states without preparing multiple copies, and may also inform adiabatic evolution. The conclusion emphasizes that a verifier combined with one state copy offers more power than either alone.
B. Studying ground states of many-body Hamiltonians
- Single-copy tomography permits multiple tomographic measurements, including non-commuting ones, on a small number of particles without preparing multiple ground-state copies.For sufficiently small systems with large enough energy gaps, ground-state preparation and phase-estimation verification may be quick enough; the authors describe a large speedup over traditional tomography.Source: B. Studying ground states of many-body… · p. 12
- During adiabatic evolution, single-copy tomography could characterize the ground state and potentially guide the choice of path in real time.The authors present this as a possible use.Source: B. Studying ground states of many-body… · p. 12
V. CONCLUSIONS
- The conclusion states that a verifier combined with a single copy of |ψ⟩ is more powerful than either resource alone.The authors hope these methods will serve as tools for developing further algorithms.Source: §V · p. 12