2
$\begingroup$

enter image description here

I was watching a presentation and I run into this example.

What does $\phi$ with the (x)t on the exponent mean?, similarly for the other symbol

$\endgroup$

2 Answers 2

2
$\begingroup$

This presentation seems to be about pseudorandom quantum states.

A set of quantum states $\left\{\phi_k\right\}_k$ indexed by some key values is said to be pseudorandom if no adversary can distinguish polynomially many copies of a state sampled by choosing a random key $k$ from as many copies of a Haar-random state $|\psi\rangle$.

In cryptography, such properties are often modeled via some games, which is the case here. The challenger will choose a bit $b\in\{0,1\}$ at random.

  • If $b=0$, then they will choose a random key $k$ and give the adversary $t$ copies of $\phi_k$. This is what $\phi_k^{\otimes t}$ represents, as mentioned by @DaftWullie in his answer.
  • If $b=1$, then they will sample a Haar-random state $|\psi\rangle$ and give the adversary $t$ copies of the same Haar-random state, which is represented by $|\psi\rangle^{\otimes t}$.

(By the way, if you don't know what an Haar-measure is, picking a Haar-random state means here to pick a quantum state uniformly at random among the set of all states.)

The adversary, upon being given $t$ copies of a state, must tell whether $b=0$ or $b=1$. If they cannot win with probability significantly larger than $\frac12$, which is just the probability of guessing, then the set $\left\{\phi_k\right\}_k$ is pseudorandom.

This is exactly what's depicted here. Note that what's potentially misleading is that both $\varphi_k$ and $|\psi\rangle$ are quantum states, even though the first one is not written using ket notation. It is usually written $\left|\phi_k\right\rangle$, which means that $t$ copies of it are usually denoted $\left|\phi_k\right\rangle^{\otimes t}$.

$\endgroup$
2
$\begingroup$

This is the tensor product symbol. Thus, something like $\phi^{\otimes t}$ means that you have $t$ copies of the state $\phi$.

$\endgroup$
2
  • $\begingroup$ Could you comment also on what $\phi^{\otimes t}_k$ might mean? $\endgroup$ Jul 24, 2023 at 14:00
  • $\begingroup$ Without more context, not really. I assume it just means that $\phi$ depends on the parameter $k$ that was the input to the StateGen function, and you have $t$ copies of it. $\endgroup$
    – DaftWullie
    Jul 24, 2023 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.