Molina, Vidick & Watrous 2012 · Theorem 1

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

Gamegame

W1

Source paper idsource_paper_id

P01

Source urlsource_url

https://arxiv.org/abs/1202.4010

Anchoranchor

Theorem 1, p.2 (statement); Sec. 3.1 SDP p.7; Sec. 3.2 n=1 primal/dual p.7-8; Sec. 3.4 parallel repetition p.9-10

Statusstatus

VERIFIED_FROM_SOURCE

Bound latexbound_latex

P^{\mathrm{opt}}_{\mathrm{two\ valid}}(n)=\left(\tfrac34\right)^{n}

Bound plainbound_plain

(3/4)**n

Variablesvariables

n: number of qubits per bank note (positive integer)

Game definitiongame_definition

Bank picks key k uniformly at random, i.e. each of n qubits is |0>,|1>,|+>,|-> with probability 1/4 independently (n-fold parallel repetition of the single-qubit ensemble, Sec. 3.4). The counterfeiter receives ONE note (register X) and applies any CPTP map Phi: L(X) -> L(Y (x) Z). Success = both Y and Z independently pass the bank's projective test {Pi=|psi_k><psi_k|, 1-Pi} (eq. 2, p.7: sum_k p_k <psi_k (x) psi_k| Phi(|psi_k><psi_k|) |psi_k (x) psi_k>).

Sdp n1sdp_n1

primal: maximize <Q,X> s.t. Tr_{Y(x)Z}(X) = 1_X, X >= 0 on Y(x)Z(x)X (p.7)
dual: minimize Tr(Y) s.t. 1_{Y(x)Z} (x) Y >= Q, Y Hermitian on X (p.7)
Q: 'Q = sum_k p_k |psi_k psi_k conj(psi_k)><psi_k psi_k conj(psi_k)| ; for Wiesner n=1: Q = (1/4)(|000><000|
  + |111><111| + |+++><+++| + |---><---|) (p.8)'
subsystem_order: 'Choi operator J(Phi) in L(Y (x) Z (x) X), output registers first, input last (Sec. 2.2:
  J(Phi) = sum_ij Phi(|i><j|) (x) |i><j|)'
optimal_primal: Phi(rho) = A0 rho A0^* + A1 rho A1^*, A0 = (1/sqrt12)[[3,0],[0,1],[0,1],[1,0]], A1 = (1/sqrt12)[[0,1],[1,0],[1,0],[0,3]]
  (4x2 matrices, output basis |00>,|01>,|10>,|11>) (p.8)
optimal_dual: Y = (3/8) 1_X ; ||Q|| = 3/8 (p.8)
optimum: 3/4

Assumptionsassumptions

• –ideal, noiseless BB84 states; exact accept-all-qubits verifier
• –no access to the bank's verifier beyond the final two independent verifications
• –single genuine note as input

Quantifier over adversariesquantifier_over_adversaries

all CPTP maps from one note to two candidate notes (unbounded quantum adversary)

Tightnesstightness

exact (optimal attack achieves the value)

Not valid fornot_valid_for

• –W1_CV (classical verification) -> use T-MVW12-THM2
• –W2 noisy/threshold verifier (per-copy thresholds) -> no closed form here
• –adaptive attacks with verification queries (paper p.2: 2^-n Bell attack; Lutomirski O(n) attack when post-measurement qubits are returned)
• –S1/S2 S-money games
• –m -> m+1 counterfeiting for m > 1 (not analysed)

Verificationverification

statement_verbatim: VERIFIED_FROM_SOURCE
bound_latex: VERIFIED_FROM_SOURCE
game_definition: VERIFIED_FROM_SOURCE
sdp_n1: VERIFIED_FROM_SOURCE
optimum_n1_recomputed: RECOMPUTED_BY_LANE_A

Recomputation notesrecomputation_notes

Lane A checked with numpy that the Kraus pair above is trace preserving, gives success 0.75 on the 4-state ensemble, and that ||Q|| = 0.375. This is a consistency check of the transcription. It doesn't replace lane C's SDP.

Related entries

• P01Optimal counterfeiting attacks and generalizations for Wiesner's quantum moneyFULL TEXT READ
• P-W1MVW2012 Theorem 1 (p.2)PUBLISHED REPRODUCED