PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum state restoration and single-copy tomography

Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Daniel Nagaj, Peter Shor

arXiv:0912.3823v2quant-ph

TL;DR

With only one copy of an unknown quantum state, the no-cloning theorem limits learning and copying, while verification alone does not efficiently prepare the state. The paper combines a single copy with verification to introduce quantum state restoration, which supports subsystem copying, single-copy tomography, and efficient estimation of general POVM statistics.

  • Problem

    A single copy of an unknown quantum state does not permit full or small-subsystem description, and verification alone does not efficiently prepare the state.

    Source: §I · p. 1, §V · p. 12

  • Method

    Quantum state restoration extends a known subsystem to the full state using a verifier, and related algorithms produce copies of small reduced states for tomography.

    Source: §I · p. 2

  • Results

    The methods efficiently copy small subsystems, perform tomography on them, and estimate general POVM statistics in time polynomial in the subsystem dimension or number of POVM operators.

    Source: §I · pp. 2–3

  • Takeaways & Limitations

    A single copy together with a verifier is more powerful than either resource alone and rules out a large class of publicly verifiable quantum money schemes.

    Source: §I · p. 2, §V · p. 12

Abstract

from arXiv · show

Given a single copy of an n qubit quantum state |psi>, the no-cloning theorem greatly limits the amount of information which can be extracted from it. Moreover, given only a procedure which verifies the state, for example a procedure which measures the operator |psi><psi|, we cannot prepare |psi> in time polynomial in n . 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 novel things efficiently. We present a new algorithm that we call quantum state restoration which allows us to extend a large subsystem of |psi> to the full state, and in turn this 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 how to use these algorithms to estimate the statistics of any efficiently implementable POVM acting on |psi> in time polynomial in the number of outcomes of the POVM.

I. INTRODUCTION

With one copy of an unknown quantum state, extracting its full or partial description is generally impossible, but a verifier adds substantial power. The paper introduces quantum state restoration and related tomography methods to recover, copy, and measure small subsystems efficiently.

Motivation

  • A verifier combined with one copy of |ψ⟩ enables operations that neither resource provides alone, including copying parts of the state and nondestructive measurements.The verifier may be a projector onto |ψ⟩, and a known gapped Hamiltonian can provide a verification procedure through its ground-state energy.Source: §I · p. 1

Quantum state restoration

  • Quantum state restoration uses a known subsystem and repeated randomized guesses of the missing subsystem, with verification recovering |ψ⟩ after a successful measurement.For |ψ⟩ in HA ⊗ HB, the expected running time is polynomial in dim HB, and failed iterations minimally damage subsystem A.Source: §I · pp. 1–2

Single-copy tomography

  • Restoration enables single-copy tomography by producing multiple copies of a small reduced state, with running time polynomial in the subsystem dimension.The same framework reduces estimation of a general POVM’s statistics, including noncommuting operators, to polynomial time in the number of POVM operators.Source: §I · p. 2

Applications to quantum money

  • These techniques challenge public-key quantum money schemes because publicly available projector verifiers can enable copying or tomography attacks against a large class of protocols.The paper’s original motivation is analyzing schemes whose money states are publicly verifiable and returned undamaged after verification.Source: §I · p. 2
  • The product-state money example uses |ψ⟩ = ⊗i|θi⟩ and local projectors that uniquely identify it, while requiring a secure quantum-resistant digital signature for the projector description.The angles must be freshly chosen for each money state because reusing them would permit standard tomography.Source: §I · p. 2

Quantum state restoration

  • The method works even for entangled states, whereas the introductory copying procedure copies the full state efficiently because the product-state structure permits qubit-by-qubit restoration.Repeating the product-state procedure for each qubit clones |ψ⟩ in linear time.Source: §I · pp. 2–3

II. QUANTUM STATE RESTORATION

Quantum state restoration reconstructs an unknown entangled state from a subsystem using coherent access to its projector, with expected runtime determined by the Schmidt rank and subsystem dimension. Its expected number of iterations is χ·d even when individual failure histories have metastable or low-success regions.

II. QUANTUM STATE RESTORATION

  • Quantum state restoration reconstructs |ψ⟩ from a mixed state on subsystem A using coherent measurement access to P = |ψ⟩⟨ψ|.The input state on A is Tr_B |ψ⟩⟨ψ|, and the algorithm outputs the full state.Source: §II · p. 3
  • Schmidt decomposition explains the runtime: if χ is the Schmidt rank and d = dim HB, equal Schmidt weights give success probability 1/(χ·d) per iteration.For unequal weights, the iteration-time distribution changes, but the expected runtime remains the same.Source: §II · p. 3
  • The algorithm sets aside subsystem B, adds a random state on B, measures P, and repeats after failures while discarding B.A successful measurement restores |ψ⟩; a failed iteration preserves the relevant Schmidt-basis support on A.Source: §II · p. 3
  • χ·d ≤ d^2 is the expected number of projector uses required by the restoration algorithm.This is the stated running-time bound in measurement-oracle calls.Source: §II · p. 3

A. Running Time of Quantum State Restoration

  • Unequal Schmidt weights can create metastable or low-success states, but their reduced probability of being reached exactly offsets their lower per-iteration success.Consequently, the expected number of iterations is χ·d regardless of the values of the Schmidt weights.Source: A. Running Time of Quantum State… · p. 4, Figure 1 · p. 4

III. SINGLE-COPY TOMOGRAPHY AND ESTIMATION OF MEASUREMENT STATISTICS

The paper develops single-copy tomography methods that use state verification to obtain subsystem information without consuming the original state. These methods also extend to estimating all outcome probabilities of any efficiently implementable POVM while returning an undamaged copy.

General tomography on a subsystem

  • Quantum state restoration can prepare many states with reduced density matrix ρB, enabling standard tomography of a subsystem from one original copy.The resulting algorithms have running time polynomial in the dimension of the restored subsystem.Source: §III · p. 5

Measurement of a subsystem in an orthogonal basis

  • For measurements in an orthonormal basis, restoration directly estimates subsystem probabilities qi = Tr[|i⟩B⟨i|B|ψ⟩⟨ψ|].Two specialized algorithms also estimate these probabilities one at a time using two-outcome measurements and QMA-amplification schemes.Source: §III · p. 5

Estimation of the statistics of any POVM

  • An efficiently implementable POVM can be converted into a computational-basis measurement on an ancillary register via a unitary U.After estimating the ancillary-register probabilities, U is uncomputed to recover the original state.Source: §III · p. 6
  • Theorem 2 gives estimates qest_i for every outcome of a d-outcome POVM with probability at least 1−ϵ while outputting an undamaged copy of the input state.The procedure uses an expected number of measurement-oracle and POVM calls specified by the theorem’s running-time bound.Source: §III · p. 6
  • The same general POVM procedure supports subsystem tomography by estimating an informationally complete POVM on that subsystem.This connects complete-state measurement-statistics estimation to tomography of reduced states.Source: §III · p. 6

A. Using quantum state restoration to estimate measurement statistics

The restoration-based estimator repeatedly measures a subsystem and restores the state, using empirical outcome frequencies to estimate all basis probabilities. Hoeffding’s inequality and a union bound control the simultaneous estimation error.

A. Using quantum state restoration to estimate measurement statistics

B. Improved algorithms to estimate measurement statistics

Two alternative single-copy tomography algorithms use Jordan’s lemma and QMA-amplification ideas to estimate each basis probability more efficiently than direct state restoration. Their running times are summarized as functions of precision and failure probability.

B. Improved algorithms to estimate measurement statistics

  • The paper describes two algorithms for single-copy tomography, both based on Jordan’s lemma [5] and QMA amplification schemes of Marriott and Watrous [6] and Nagaj et al. [8].Source: B. Improved algorithms to estimate… · p. 7
  • Each algorithm fixes an outcome i, constructs the relevant projectors and states, estimates qi, and repeats for every outcome.The construction relates the bases {|ψ⟩, |ψ⊥_i⟩} and {|v_i⟩, |v⊥_i⟩}.Source: B. Improved algorithms to estimate… · p. 7
  • Both algorithms produce qest_i with error below δ for all outcomes with probability at least 1−ϵ, and their running times are summarized in Table I.The comparison is expressed as a function of δ and ϵ.Source: B. Improved algorithms to estimate… · p. 7

1. Alternating Projections

Alternating projections estimate subsystem probabilities by repeatedly measuring a subsystem projector and the state projector, restoring |ψ⟩ when measurements leave it. The method achieves the desired precision with high probability while controlling expected verifier uses.

Algorithm

  • The algorithm alternates measurements of Q_i and P, recording outcomes and recovering |ψ⟩ through further alternating measurements when necessary.The estimator uses outcome differences to infer q_i, while failed state-projector measurements trigger restoration before continuing.Source: §1 · p. 8

Estimator

  • The estimator uses the number of unchanged consecutive outcomes to estimate q_i, because outcome agreement occurs with probability q_i.The resulting count is binomial with mean q_i(2N −1).Source: §1 · p. 8

Accuracy

  • The estimates achieve precision δ with probability at least 1 −ϵ.This guarantee follows by applying Hoeffding’s inequality to the estimator.Source: §1 · p. 8

Runtime

  • The alternating-projection procedure uses at most 2N expected measurements of P.Its runtime is N plus an expected recovery cost bounded using a union bound.Source: §1 · p. 8

2. An improved algorithm using phase estimation

The improved tomography algorithm replaces alternating projections with phase estimation of a reflection-based operator, while repeatedly measuring P to preserve or recover the state. It achieves controlled estimation accuracy with a quadratic reduction in verifier measurements as precision becomes stringent.

Overview

  • Phase estimation provides an improved single-copy tomography algorithm based on a fast QMA amplification scheme [8].The algorithm estimates each subsystem probability and uses medians of repeated estimates to reduce failure probability.Source: §2 · p. 9

Estimator

  • The reflection-based operator W_i encodes q_i through phase estimation, with q_i = ⟨ψ|Q_i|ψ⟩ = cos^2 θ_i.The relevant eigenphases are related by φ_i and 1 −φ_i, which yield the same cosine-squared estimate.Source: §2 · p. 9

Procedure

  • The algorithm repeatedly performs phase estimation followed by measurement of P, recovering |ψ⟩ when a failed measurement leaves the orthogonal state.Each iteration can be analyzed as a symmetric random walk between |ψ⟩ and |ψ⊥⟩.Source: §2 · pp. 9–10

Runtime

  • The expected number of phase-estimation-and-P-measurement uses is at most 2r.This bounds the repetitions needed for the median-based estimator.Source: §2 · p. 10

Accuracy

  • Phase estimation yields estimates within the target interval with high probability, and the median construction makes all q_i estimates simultaneously accurate with probability at least 1 −ϵ.The analysis uses phase-estimation accuracy and a median lemma across repeated trials.Source: §2 · pp. 10–11

C. Performance comparison for estimating measurement statistics

All three algorithms estimate the subsystem probabilities within δ with probability at least 1 −ϵ, but their expected verifier-measurement costs differ. Phase estimation has the strongest asymptotic dependence on precision, while state restoration remains the simplest and most adaptable.

Accuracy

Comparison

  • State restoration is conceptually simplest and can incorporate different tomography schemes, but it is slowest as a function of d and δ when χ increases with d.Its modularity may allow performance improvements by replacing the tomography component.Source: C. Performance comparison for… · p. 11
  • Phase estimation performs quadratically better than the other algorithms as δ →0.Without a better tomography scheme, both specialized alternatives also outperform state restoration as a function of d.Source: C. Performance comparison for… · p. 11

A. Breaking quantum money

The paper applies single-copy tomography and state restoration to public-key quantum money, where public verification can expose information about the money state. Projector-based verifiers must therefore withstand attacks that estimate efficiently implementable measurement statistics.

Public-key quantum money

  • Public-key quantum money combines a quantum state with a verification procedure intended to accept valid bank-issued money and reject efficiently forgeable states.Public verifiability gives would-be forgers access to the verification procedure.Source: A. Breaking quantum money · pp. 11–12

Attack implication

  • If the verifier is a projector, single-copy tomography can estimate any efficiently implementable measurement with a small number of outcomes on the money state.Thus projector-based protocols must be designed to withstand these attacks.Source: A. Breaking quantum money · p. 12

B. Studying ground states of many-body Hamiltonians

Single-copy tomography enables efficient study of small subsystems of many-body ground states when a single ground-state copy can be prepared and verified. More broadly, combining a verifier with one copy of an unknown state is more powerful than either resource alone.

B. Studying ground states of many-body Hamiltonians

  • Single-copy tomography supports multiple tomographic measurements, including of noncommuting operators, on small particle subsets without preparing multiple ground-state copies.For sufficiently small systems with sufficiently large energy gaps, algorithms such as [10] may prepare one ground-state copy efficiently, and phase estimation can verify it.Source: B. Studying ground states of many-body… · p. 12
  • Tomographic information from a ground state could characterize it during adiabatic evolution and guide the adiabatic path in real time.Source: B. Studying ground states of many-body… · p. 12

V. CONCLUSIONS

  • The combination of a verifier and a single copy of |ψ⟩ provides more power than either verification ability or state possession alone.Efficiently producing an unknown verified state is otherwise strongly believed to be impossible in general.Source: §V · p. 12
Loading 0912.3823v2…