The usual hybrid argument tells us that if two efficiently sampled ensembles are computationally indistinguishable based on a single sample, then, computational indistinguishability holds even for polynomially-many independent samples.

My question is based on the fact of a quantum state induces a probability distribution, and is as follows:

Can the hybrid argument be extended to the fact that if two quantum states $\rho_0,\rho_1$ are computationally indistinguishable to all QPT adversaries $\mathcal{A}$, then by giving any adversary $\mathcal{A}$ polynomially-many copies of the quantum states $\rho_0^{\otimes p(\lambda)}, \rho_1^{\otimes p(\lambda)}$, then the distributions of the outputs of $\mathcal{A}$ are still indistinguishable? (I.e., $\rho_0^{\otimes p(\lambda)}, \rho_1^{\otimes p(\lambda)}$ are computational indistinguishable?)


1 Answer 1


Assuming $\mathcal{A}$ can by itself generate copies of $\rho_0$ and $\rho_1$, then yes this is the case.

\begin{align*} &\| \mathcal{A}(\rho_0^{\otimes p}) - \mathcal{A}(\rho_0^{\otimes p})\| \\ &\leq \sum_i \| \mathcal{A}(\rho_0^{\otimes (p-i)}\otimes \rho_1^{\otimes i}) - \mathcal{A}(\rho_0^{\otimes (p-i-1)}\otimes \rho_1^{\otimes i+1}) \|\\ &\leq \sum_i \| \mathcal{A}_i(\rho_1) - \mathcal{A}_i(\rho_0)\|\\ \end{align*} where $\mathcal{A}_i$ prepares $p-i-1$ copies of $\rho_0$ and $i$ copies of $\rho_1$ and on input $\rho$ outputs $\mathcal{A}(\rho_0^{\otimes (p-i-1)}\otimes \rho \otimes \rho_1^{\otimes i})$.

If $\mathcal{A}$ cannot construct copies of $\rho_0$ or $\rho_1$ by itself, then you need to assume nonuniform indistinguishability of $\rho_0$ and $\rho_1$, so that the state $\rho_0^{\otimes (p-i-1)}\otimes\rho_1^{\otimes i}$ can be given as quantum advice to $\mathcal{A}_i$.


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.