Molina, Vidick & Watrous 2012 · Theorem 2

Citations

• https://arxiv.org/abs/1202.4010(opens in a new tab)
• https://arxiv.org/pdf/1202.4010v1(opens in a new tab)

Record

Every field of the source record, in file order.

Proof obligationproof_obligation

P-W1-CV

Gamegame

W1_CV

Source paper idsource_paper_id

P01

Source urlsource_url

https://arxiv.org/abs/1202.4010

Anchoranchor

Theorem 2, p.3; game Sec. 4.1 eq.(8) p.13; Lemma 5 and proof p.14; matching lower bound Lemma 6 p.15

Statusstatus

VERIFIED_FROM_SOURCE

Bound latexbound_latex

P^{\mathrm{opt}}(n)=\left(\tfrac34+\tfrac{\sqrt2}{8}\right)^{n}

Bound plainbound_plain

(3/4 + sqrt(2)/8)**n # = 0.92677669529...**n

General form lemma5general_form_lemma5

Lemma 5 (p.14): for the n-qudit classical-verification scheme with two bases {e^0_t},{e^1_t} of C^d, success probability <= (3/4 + sqrt(c)/4)^n where c = max_{s,t} |<e^0_s|e^1_t>|^2 (effective overlap; c >= 1/d, footnote 9). Achievable when d = 2. For d = 2 MUB c = 1/2 gives 3/4 + 1/(4 sqrt 2) = 3/4 + sqrt2/8. Qudit Fourier scheme: (3/4 + 1/(4 sqrt d))^n (Lemma 6, tight).

Variablesvariables

n: number of qubits per ticket
c: effective overlap max_{s,t}|<e^0_s|e^1_t>|^2 (Lemma 5)
d: local dimension (d=2 for Wiesner)

Game definitiongame_definition

Ticket = Wiesner-type state with secret key k and serial number. Honest verification: user announces serial, bank sends uniformly random challenge c in {0,1}^n (C = {0,1} per qubit); user measures qubit i in the computational basis if c_i=0 and in the Hadamard basis if c_i=1 and reports outcomes; bank accepts iff every position where c_i equals the encoding basis has the correct outcome. Valid single-qubit answers: a = t if b = c, any a if b != c (Sec. 4.2). Simple counterfeiting attack: from ONE ticket, answer TWO independent uniformly random challenges c1, c2 correctly. Attack is modelled as POVMs A^{c1 c2} that depend on BOTH challenges (eq. 8, p.13). Verification destroys the ticket (footnote 6).

Assumptionsassumptions

• –ideal states; exact verification of matching-basis positions
• –the counterfeiter sees both challenges before measuring (as modelled in eq. 8)
• –no additional bank interaction

Quantifier over adversariesquantifier_over_adversaries

all POVMs on the ticket conditioned on (c1, c2)

Tightnesstightness

exact for d = 2 (Lemma 5 'moreover' part)

Not valid fornot_valid_for

• –W1 (quantum verification): different game, value (3/4)^n
• –S1: Kent et al. ideal S-token bound is (1/2 + 1/(2 sqrt2))^N, a different game and value
• –noisy/threshold or lossy classical verification

Verificationverification

statement_verbatim: VERIFIED_FROM_SOURCE
bound_latex: VERIFIED_FROM_SOURCE
general_form_lemma5: VERIFIED_FROM_SOURCE
game_definition: VERIFIED_FROM_SOURCE

Related entries

• P01Optimal counterfeiting attacks and generalizations for Wiesner's quantum moneyFULL TEXT READ