Compute probability of counterfeiting quantum money 1.
The primal problem for the \(n\)-fold parallel repetition is given as follows:
\[
\begin{equation}
\begin{aligned}
\text{maximize:} \quad &
\langle W_{\pi} \left(Q^{\otimes n} \right) W_{\pi}^*, X \rangle \\
\text{subject to:} \quad & \text{Tr}_{\mathcal{Y}^{\otimes n}
\otimes \mathcal{Z}^{\otimes n}}(X)
= \mathbb{I}_{\mathcal{X}^{\otimes
n}},\\
& X \in \text{Pos}(
\mathcal{Y}^{\otimes n}
\otimes \mathcal{Z}^{\otimes n}
\otimes \mathcal{X}^{\otimes n}).
\end{aligned}
\end{equation}
\]
The dual problem for the \(n\)-fold parallel repetition is given as follows:
\[
\begin{equation}
\begin{aligned}
\text{minimize:} \quad & \text{Tr}(Y) \\
\text{subject to:} \quad & \mathbb{I}_{\mathcal{Y}^{\otimes n}
\otimes \mathcal{Z}^{\otimes n}} \otimes Y \geq W_{\pi}
\left( Q^{\otimes n} \right) W_{\pi}^*, \\
& Y \in \text{Herm} \left(\mathcal{X}^{\otimes n} \right).
\end{aligned}
\end{equation}
\]
Parameters:
-
states
(list[ndarray])
–
A list of states provided as either matrices or vectors.
-
probs
(list[float])
–
Respective list of probabilities each state is selected.
-
num_reps
(int, default:
1
)
–
Number of parallel repetitions to perform.
-
strategy
(bool, default:
False
)
–
Boolean that denotes whether to return strategy.
Returns:
-
float | ndarray
–
The optimal probability with of counterfeiting quantum money.
Examples:
Wiesner's original quantum money scheme 2 was shown in
1 to have an optimal probability of 3/4 for succeeding a counterfeiting attack.
Specifically, in the single-qubit case, Wiesner's quantum money scheme corresponds to the
following ensemble:
\[
\left\{
\left( \frac{1}{4}, |0\rangle \right),
\left( \frac{1}{4}, |1\rangle \right),
\left( \frac{1}{4}, |+\rangle \right),
\left( \frac{1}{4}, |-\rangle \right)
\right\},
\]
which yields the operator
\[
\begin{equation}
Q = \frac{1}{4} \left(|000 \rangle \langle 000| + |111 \rangle \langle 111| +
|+++ \rangle + \langle +++| + |--- \rangle \langle ---| \right).
\end{equation}
\]
We can see that the optimal value we obtain in solving the SDP is 3/4.
import numpy as np
from toqito.states import basis
from toqito.state_opt import optimal_clone
e_0, e_1 = basis(2, 0), basis(2, 1)
e_p = (e_0 + e_1) / np.sqrt(2)
e_m = (e_0 - e_1) / np.sqrt(2)
states = [e_0, e_1, e_p, e_m]
probs = [1 / 4, 1 / 4, 1 / 4, 1 / 4]
print(np.around(optimal_clone(states, probs), decimals=2))
References
1 Molina, Abel and Vidick, Thomas and Watrous, John. Optimal counterfeiting attacks and generalizations for Wiesner's quantum money. (2012).
2 Wiesner, Stephen. Conjugate Coding. SIGACT News. vol. 15(1). (1983). doi:10.1145/1008908.1008920.
Source code in toqito/state_opt/optimal_clone.py
| def optimal_clone(
states: list[np.ndarray],
probs: list[float],
num_reps: int = 1,
strategy: bool = False,
) -> float | np.ndarray:
r"""Compute probability of counterfeiting quantum money [@molina2012optimal].
The primal problem for the \(n\)-fold parallel repetition is given as follows:
\[
\begin{equation}
\begin{aligned}
\text{maximize:} \quad &
\langle W_{\pi} \left(Q^{\otimes n} \right) W_{\pi}^*, X \rangle \\
\text{subject to:} \quad & \text{Tr}_{\mathcal{Y}^{\otimes n}
\otimes \mathcal{Z}^{\otimes n}}(X)
= \mathbb{I}_{\mathcal{X}^{\otimes
n}},\\
& X \in \text{Pos}(
\mathcal{Y}^{\otimes n}
\otimes \mathcal{Z}^{\otimes n}
\otimes \mathcal{X}^{\otimes n}).
\end{aligned}
\end{equation}
\]
The dual problem for the \(n\)-fold parallel repetition is given as follows:
\[
\begin{equation}
\begin{aligned}
\text{minimize:} \quad & \text{Tr}(Y) \\
\text{subject to:} \quad & \mathbb{I}_{\mathcal{Y}^{\otimes n}
\otimes \mathcal{Z}^{\otimes n}} \otimes Y \geq W_{\pi}
\left( Q^{\otimes n} \right) W_{\pi}^*, \\
& Y \in \text{Herm} \left(\mathcal{X}^{\otimes n} \right).
\end{aligned}
\end{equation}
\]
Args:
states: A list of states provided as either matrices or vectors.
probs: Respective list of probabilities each state is selected.
num_reps: Number of parallel repetitions to perform.
strategy: Boolean that denotes whether to return strategy.
Returns:
The optimal probability with of counterfeiting quantum money.
Examples:
Wiesner's original quantum money scheme [@wiesner1983conjugate] was shown in
[@molina2012optimal] to have an optimal probability of 3/4 for succeeding a counterfeiting attack.
Specifically, in the single-qubit case, Wiesner's quantum money scheme corresponds to the
following ensemble:
\[
\left\{
\left( \frac{1}{4}, |0\rangle \right),
\left( \frac{1}{4}, |1\rangle \right),
\left( \frac{1}{4}, |+\rangle \right),
\left( \frac{1}{4}, |-\rangle \right)
\right\},
\]
which yields the operator
\[
\begin{equation}
Q = \frac{1}{4} \left(|000 \rangle \langle 000| + |111 \rangle \langle 111| +
|+++ \rangle + \langle +++| + |--- \rangle \langle ---| \right).
\end{equation}
\]
We can see that the optimal value we obtain in solving the SDP is 3/4.
```python exec="1" source="above" result="text"
import numpy as np
from toqito.states import basis
from toqito.state_opt import optimal_clone
e_0, e_1 = basis(2, 0), basis(2, 1)
e_p = (e_0 + e_1) / np.sqrt(2)
e_m = (e_0 - e_1) / np.sqrt(2)
states = [e_0, e_1, e_p, e_m]
probs = [1 / 4, 1 / 4, 1 / 4, 1 / 4]
print(np.around(optimal_clone(states, probs), decimals=2))
```
"""
dim = len(states[0]) ** 3
# Construct the following operator:
# ___ ___
# Q = ∑_{k=1}^N p_k |ψ_k ⊗ ψ_k ⊗ ψ_k> <ψ_k ⊗ ψ_k ⊗ ψ_k|
q_a = np.zeros((dim, dim))
for k, state in enumerate(states):
q_a += probs[k] * tensor(state, state, state.conj()) @ tensor(state, state, state.conj()).conj().T
# The system is over:
# Y_1 ⊗ Z_1 ⊗ X_1, ... , Y_n ⊗ Z_n ⊗ X_n.
num_spaces = 3
# In the event of more than a single repetition, one needs to apply a
# permutation operator to the variables in the SDP to properly align
# the spaces.
if num_reps == 1:
pperm = np.array([1])
else:
# The permutation vector `perm` contains elements of the
# sequence from: https://oeis.org/A023123
q_a = tensor(q_a, num_reps)
perm = []
for i in range(num_spaces):
perm.append(i)
var = i
for j in range(1, num_reps):
perm.append(var + num_spaces * j)
pperm = permutation_operator(2, perm)
if strategy:
return primal_problem(q_a, pperm, num_reps)
return dual_problem(q_a, pperm, num_reps)
|