PaperlayerView exact revision on arXiv

Source-linked AI summary

Unforgeable Noise-Tolerant Quantum Tokens

Fernando Pastawski, Norman Y. Yao, Liang Jiang, Mikhail D. Lukin, J. Ignacio Cirac

arXiv:1112.5456v1quant-ph

TL;DR

Quantum-token verification must tolerate realistic noise, but allowing qubit failures can also make forgery easier. This paper develops error-tolerant quantum-token protocols and proves soundness and security when dishonest fidelity is below tolerance fidelity, which is below experimental fidelity.

  • Problem

    Noise-tolerant verification must permit some qubit failures, but that relaxation can increase forgery ability, making their interplay a central research question.

    Source: p. 1

  • Method

    The paper extends quantum money into error-tolerant qtickets and a classical-verification variant that accommodate finite qubit errors.

    Source: pp. 1–2

  • Results

    For both qticket and cv-qticket protocols, soundness and security are provable when Fdishonest < Ftol < Fexp.

    Source: p. 3

  • Takeaways & Limitations

    Derived tolerance thresholds suggest proof-of-principle experiments are currently accessible in trapped ions, superconducting devices, and solid-state spins.

    Source: p. 3

Abstract

from arXiv · show

The realization of devices which harness the laws of quantum mechanics represents an exciting challenge at the interface of modern technology and fundamental science. An exemplary paragon of the power of such quantum primitives is the concept of "quantum money". A dishonest holder of a quantum bank-note will invariably fail in any forging attempts; indeed, under assumptions of ideal measurements and decoherence-free memories such security is guaranteed by the no-cloning theorem. In any practical situation, however, noise, decoherence and operational imperfections abound. Thus, the development of secure "quantum money"-type primitives capable of tolerating realistic infidelities is of both practical and fundamental importance. Here, we propose a novel class of such protocols and demonstrate their tolerance to noise; moreover, we prove their rigorous security by determining tight fidelity thresholds. Our proposed protocols require only the ability to prepare, store and measure single qubit quantum memories, making their experimental realization accessible with current technologies.

Methods

The methods define valid qtickets using a fidelity-threshold acceptance projector and use Chernoff bounds to analyze honest redemption and security against arbitrary counterfeiting attacks.

Proof of Quantum Ticket Soundness

  • The acceptor projects an N-qubit product state onto valid qtickets, defined by Boolean strings with at least FtolN entries equal to 1.The string's number of 1s is its Hamming weight, and the valid subspace depends on the verifier's tolerance Ftol.Source: Methods · p. 4
  • Fexp is the average achievable experimental fidelity, defined as the mean of the individual encoding, storage, and decoding fidelities Fi.Each qubit map Mi characterizes the overall fidelity Fi.Source: Methods · p. 4
  • When Fexp > Ftol, an honest holder redeems a qticket with high probability, as shown by applying a Chernoff bound to independent Boolean fidelity outcomes.The outcomes have probabilities Fi, and acceptance requires at least FtolN successes.Source: Methods · p. 4
  • The security proof handles arbitrary counterfeiting attacks, including those that may correlate qticket components, using a generalized Chernoff-Hoeffding bound.The paper states that the generalized bound is required to rigorously address such correlations.Source: Methods · p. 4

S.1. NOTATION AND EXTERNAL RESULTS

This section establishes the quantum-state and probability notation used in the proofs, defines fidelity and relative entropy, and states concentration bounds for dependent random variables.

S.1. NOTATION AND EXTERNAL RESULTS

  • A quantum state t-design reproduces Haar-measure averages for polynomials up to degree t, and the six listed qubit states with equal weights form a 3-design [S1].The states are |0⟩, |1⟩, |+⟩, |−⟩, |+i⟩, and |−i⟩.Source: §S.1 · p. 6
  • Average fidelity quantifies how well a map preserves quantum states and can be evaluated as a weighted average over a quantum state 2-design.The passage relates the fidelity expression to a Haar integral of a degree-2 polynomial in bras and kets.Source: §S.1 · p. 6
  • Boolean values are encoded as 1 and 0, strings use length and last-element removal notation, and Pr and Exp denote probability and expectation, respectively.For Boolean formulas, probability and expectation may be used interchangeably.Source: §S.1 · p. 6
  • Bernoulli relative entropy D(p∥q) is a distinguishability measure and satisfies D(p∥q) ≥ 2(p − q)^2.The definition applies to parameters p and q between 0 and 1.Source: §S.1 · p. 6
  • A generalized Chernoff–Hoeffding bound from Panconesi and Srinivasan [S2] allows dependent Boolean random variables under a relaxed hypothesis.The supplied passage introduces the theorem but does not provide enough of its formula to state its quantitative bound.Source: §S.1 · p. 6
  • A further bound adapted from Impagliazzo and Kabanets [S3] treats dependent real-valued random variables in [0, 1].Its hypotheses constrain expectations over every set of variables and specify parameters δ and γ.Source: §S.1 · p. 6

S.2. QTICKETS

The section defines qtickets and their verification, then establishes honest redemption, security against repeated forgery attempts, and a tight security threshold. It also extends the results to producing multiple identical qtickets.

S.2. QTICKETS

  • The section defines qtickets and specifies how verifiers check them.Source: §S.2 · p. 6
  • An honest holder can successfully redeem a qtickets when its storage fidelity is sufficiently good.Source: §S.2 · p. 6
  • A dishonest holder has negligible chance of producing two accepted qtickets from one valid qticket, even after repeated verification attempts.Source: §S.2 · p. 6
  • A simple counterfeiting strategy succeeds with high probability when verification tolerance is set below the security threshold.Source: §S.2 · p. 6
  • The section generalizes its results to producing multiple identical qtickets.Source: §S.2 · p. 6

S.2.1. Definition of qtickets

A qticket is an N-component pure product state sampled from a specified set, associated with a serial number whose state description is kept secret by verifiers. Verification consumes the submitted ticket and accepts it according to the fraction of qubits matching the original state.

S.2.1. Definition of qtickets

  • Each qticket has a serial number and an N-component pure product state, with tickets drawn uniformly from the product set formed from components in ˜Q.The serial number is omitted from notation after the ticket is introduced.Source: §S.2.1 · p. 7
  • For each serial number, verifiers keep a secret classical description of the corresponding qticket state, which is not disclosed to ticket holders or the public.Source: §S.2.1 · p. 7
  • Verification measures the submitted ticket in the original product basis, counts correct outcomes, and accepts it if at least a fraction Ftol of its N qubits are correct.The authority returns only the binary accept-or-reject outcome, not the ticket.Source: §S.2.1 · p. 7

S.2.2. Soundness

Soundness is analyzed at the single-qubit level: Theorem 6 states that an honest holder can redeem a qticket when average qubit fidelity exceeds Ftol, while significant correlated failures can ruin legitimate qtickets.

Soundness

  • The soundness model represents each qubit’s encoding, storage, and readout by a CPTP map Mi, because significant correlated qubit failures can ruin legitimate qtickets.The result is therefore formulated at the single-qubit level.Source: §S.2.2 · p. 7
  • Fexp is the average of the component maps’ average fidelities Fi across the full map M.Each Fi is defined as the average fidelity of qubit map Mi.Source: §S.2.2 · p. 7
  • Theorem 6 states that when Fexp > Ftol, an honest holder can successfully redeem a qticket with a probability.The supplied passage does not include the probability expression.Source: §S.2.2 · p. 7
  • The proof uses the qubit-space 2-design property to make the Xi independent Boolean variables with Pr[Xi] = Fi, then applies a Chernoff-Hoeffding bound.The supplied passages do not state the resulting probability bound.Source: §S.2.2 · p. 7

S.2.3. Security

The security results show that when Ftol > 5/6, forging two accepted qtickets from one genuine qticket has exponentially small probability in N, even against general CPTP counterfeiting maps.

S.2.3. Security

  • For Ftol > 5/6, the average probability that a dishonest participant forges two accepted qtickets from one genuine qticket is exponentially small in N, without access to its classical description.The bound applies when the two submissions are produced by the most general transformation T, a CPTP map.Source: §S.2.3 · pp. 7–8
  • The proof excludes non-product counterfeiting strategies that could outperform product strategies such as optimal cloning of each qubit.The map T need not factorize across the qticket components; D(2Ftol − 1∥2/3) is zero precisely at Ftol = 5/6 and positive otherwise.Source: §S.2.3 · p. 8
  • With v verification submissions, the probability of two or more accepted qtickets is bounded by a quantity polynomial of degree 2 in v, preserving exponentially good security for exponentially many submissions.Submissions may use information learned from previous acceptance or rejection outcomes.Source: §S.2.3 · p. 8

1. Proof outline

The proof of theorem 8 replaces averaging over Q with averaging over pure product states, bounds cloning probability, and applies a generalized Chernoff bound. Theorem 9 follows from a counting argument linking multiple verification attempts to theorem 8’s static counterfeiting fidelity bound.

1. Proof outline

  • Theorem 8 is proved by averaging over pure product states, bounding average cloning probability by (2/3)N, and applying the dependent-variable generalized Chernoff bound from theorem 3.The proof follows the lines of R. F. Werner [S4] for optimal cloning of pure states.Source: §1 · p. 8
  • Theorem 9 follows from a counting argument relating security across multiple verification attempts to theorem 8’s static counterfeiting fidelity bound.Source: §1 · p. 8

2. Equivalence with continuous statement

The qticket protocol uses discrete component states for an efficient classical description, while its counterfeiting fidelity can be analyzed as a uniform average over pure product states. Because the fidelity integrand has degree at most 3 in each qubit component, that average is equivalent to sampling each component from a qubit 3-design.

2. Equivalence with continuous statement

  • The average counterfeiting fidelity can also be expressed as a uniform average over all pure product states.The expression uses nested Haar-measure integrations over the qubit components.Source: §2 · p. 8
  • Drawing each qticket component from a discrete set of states is required for an efficient classical description.Source: §2 · p. 8
  • The counterfeiting-fidelity average over qticket states is equivalent to uniformly sampling each qubit component from a qubit 3-design.The integrand has degree at most 3 in each component.Source: §2 · p. 8

3. Optimal cloning for pure product states

For pure product states, optimal cloning is achieved by cloning each component independently; entanglement or correlations do not improve the cloning probability. The paper presents the result for two copies of a qubit product state and says the derivation generalizes fully.

3. Optimal cloning for pure product states

  • Cloning each component independently achieves the optimal average fidelity for an N-component pure product state; entanglement and correlations cannot improve the cloning probability.Lemma 11 states a bound on the average cloning fidelity of a CPTP map, but the bound's formula is not visible in the supplied passage.Source: §3 · p. 8
  • The result is presented for cloning two copies from a qubit product state, and its derivation generalizes fully to N components.Source: §3 · p. 8
  • The proof symmetrizes any fidelity-achieving cloning map into a covariant map with the same average fidelity, using equivalence of product states under local unitaries.It also invokes the rank-3 projector onto the symmetric space of two qubits.Source: §3 · pp. 8–9

4. Pigeonhole argument and Chernoff bound

The proof of Theorem 8 uses a pigeonhole argument to require many components to be measured correctly on both qtickets, then applies a Chernoff bound to establish the no-counterfeiting result.

4. Pigeonhole argument and Chernoff bound

  • If both qtickets are accepted, at least 2FtolN − N components must have been measured correctly on both, by the pigeonhole principle.Each qticket must have at least FtolN correctly measured components.Source: §4 · p. 9
  • Although the correctness-event variables Ei may be dependent for arbitrary T, Lemma 11 bounds them for any subset S of qubit components.Source: §4 · p. 9
  • Theorem 3 supplies an upper bound on the right-hand side of equation 12, yielding the thesis of Theorem 8.Source: §4 · p. 9

5. Combinatorial bound on learning

The section extends the two-copy counterfeiting bound to adaptive strategies: even after receiving feedback from repeated verifications, a counterfeiter with a valid qticket is very unlikely to produce more than one accepted token.

5. Combinatorial bound on learning

  • Theorem 9 bounds counterfeiting success over v adaptive submissions by reducing it to the bound for producing two counterfeits from one qticket.The per-map bound is B = e−ND(2Ftol−1∥2/3); the supplied passage truncates the final expression for the interactive-strategy bound.Source: §5 · pp. 9–10
  • A v-step interactive strategy is modeled as CPTP maps that depend on previous verification outcomes and act on a holder’s memory.Fixing an outcome string gives a composed CPTP map that produces len(b) + 1 possibly entangled qticket outputs from one input.Source: §5 · p. 9
  • Every full verification outcome with at least two acceptances has a unique shortest prefix containing exactly two acceptances.The prefix is made shortest by requiring its last verification to be one of those two acceptances.Source: §5 · p. 10
  • For each such prefix, the proof constructs a static two-token strategy from the interactive strategy and bounds its counterfeiting probability by B.This lets the proof bound the contributions associated with each pair of successful submissions using the single-copy, two-counterfeit bound.Source: §5 · p. 10

S.2.4. Tightness

The tightness analysis places the security threshold at Ftol = 5/6: cloning gives a counterfeiting strategy below it, while asymptotically no strategy works above it.

Tightness

  • For Ftol < 5/6, independently cloning each qubit can produce two accepted qtickets, with acceptance probability approaching a step function at 5/6 as N increases.The probability that either qticket fails verification is bounded by the sum of their individual failure probabilities, even if failures are anticorrelated.Source: Figure S2 · p. 10, §S.2.4 · p. 10
  • Asymptotically in N, no counterfeiting strategy works for Ftol > 5/6, although other schemes could outperform cloning when Ftol = 1.The passage states that cloning provides optimal forging probability at Ftol = 1.Source: §S.2.4 · p. 10

S.2.5. Extension: Issuing multiple identical qtickets … S.4.6. Combining with classical computational assumptions

This section develops extensions of qticket protocols and analyzes their security, including cv-qticket counterfeiting and double use under different verification settings. It also surveys practical applications and examines a quantum/classical zero-knowledge token construction.

S.2.5. Extension: Issuing multiple identical qtickets

  • For c issued copies, the extension excludes successful verification of c + 1; it requires a state t-design with t = c+(c+1), and states a fidelity threshold for security.For two issued copies, t = 5; the proofs follow the c = 1 case, and the text also extends the bound to v > c + 1 verification attempts without supplying the bound's expression here.Source: §S.2.5 · p. 10

S.3.1. Definition of cv-qticket

  • Each cv-qticket contains n × r qubit pairs drawn from eight specified two-qubit states, and verification asks for n random X or Z axes, one per block.Within each block, at least Ftolr reported outcomes for qubits prepared in eigenstates of the requested axis must be correct.Source: §S.3.1 · p. 11

S.3.2. Soundness

  • When the minimum expected block fidelity Fexp exceeds Ftol, an honest holder can successfully redeem a cv-qticket.Randomly remapping Cartesian axes is needed to connect performance to average storage fidelity when physical polarizations are lost unevenly.Source: §S.3.2 · p. 11

S.3.3. Security

  • A cv-qticket holder is exponentially unlikely to satisfy two verification questions, even with v attempts, adaptive answer order, and continued attempts after failures.The proof models the protocol with QRGs, bounds answers to complementary questions, then uses a combinatorial bound for multiple attempts.Source: §S.3.3 · pp. 11–12

S.3.4. Quantum retrieval games

  • For a weighted QRG G = (ϱ, σ), the selective value is Sel(G) = maxa ∥O(a)∥, with O(a) defined from the ensemble, utility, and average state.The result supplies an explicit selective-value formula and construction; the passage also gives a condition for selective and physical values to coincide, though its expression is truncated.Source: §S.3.4 · p. 13
  • For independent games, tensor-product selective value equals the product of their selective values; for WQRGs Gj with Sel(Gj)=δj, Theorem 27 bounds Sel(Gγ) by 2e^-nD(γ∥δ).Source: §S.3.4 · pp. 13–14

S.3.5. cv-qticket qubit pair building block

  • In the cv-qticket qubit-pair game, Alice asks for both qubits' Z polarization, and measuring both in the Z basis always gives a correct answer under the stated criterion.The criterion checks agreement on the qubit prepared in a Z eigenstate.Source: §S.3.5 · p. 14

S.3.5–S.3.6. cv-qticket qubit pair building block and cv-qticket

  • With sufficiently large r, the n-pair forgery bound decays exponentially; single-pair conjunction and complementary-average values are 3/4 and ≈0.8536, reaching ≈0.927 when half the questions coincide.The repeated-pair bound is a factor below one raised to n.Source: §S.3.5 · p. 14, §S.3.6 · p. 15

S.3.7. Combinatorial bound on choosing and learning

  • With v verification attempts, holders can choose among simultaneously obtained questions or adapt to prior feedback; the analysis bounds two-or-more acceptances using question-pair and feedback branches.When r is large and n relatively small, the question-pair bound can be close to the collision probability 2^-n.Source: §S.3.7 · p. 15

S.4.1. Enforcing single usage with a single verifier

  • A single verifier or verifiers with a centralized database can prevent double use with classical tickets, so qtickets add no protection in those settings.A redeemed ticket can be removed from the database and invalidated for subsequent attempts.Source: §S.4.1 · p. 16

S.4.2. Multiple non communicating verifiers

  • With multiple non-communicating verifiers, qtickets address settings where classical approaches fail, such as witness asylum at hotels that cannot share location information.The example requires hotels to verify tokens without communicating with one another or the issuing authority.Source: §S.4.2 · p. 16

S.4.3. Reduced availability under sporadic verification

  • For sporadically checked transit tickets, a qticket can prevent simultaneous use by colluding commuters because it cannot be shared without long-distance quantum communication, unlike classical copies [S7].A valid ticket is accepted at control and replaced with a fresh one.Source: §S.4.3 · p. 16

S.4.4. The Quantum Credit Card

  • Gavinsky’s proposal [S5] extends a token to multiple verification rounds without allowing it to split into independently valid parts, suggesting a quantum credit card or cash token.For the credit-card interpretation, the holder can publicize the issuer’s challenge-question exchange to a merchant as evidence of validity.Source: §S.4.4 · p. 16

S.4.5. Excluding eavesdropers

  • A quantum TAN list can be checked using sacrificed qubits to bound eavesdropper leakage; after verification, the chance an eavesdropper succeeds using leaked information is exponentially small.The proposal applies prepare-and-measure memories even when the token travels through an untrusted channel.Source: §S.4.5 · p. 17

S.4.6. Combining with classical computational assumptions

  • Bennett et al.’s proposal [S6] to encode a one-time proof in a quantum token fails against coherent attacks: sequential measurements can recover both messages with success approaching one.The construction combines a classical cut with two possible proofs encoded in a quantum state; the argument considers two-bit multiplexing.Source: §S.4.6 · pp. 17–18
Loading 1112.5456v1…