Quantum Programmable Reflections

Similar to a classical processor, which is an algorithm for reading a program and executing its instructions on input data, a universal programmable quantum processor is a fixed quantum channel that reads a quantum program $\lvert\psi_{U}\rangle$ that causes the processor to approximately apply an arbitrary unitary $U$ to a quantum data register. The present work focuses on a class of simple programmable quantum processors for implementing reflection operators, i.e. $U = e^{i \pi \lvert\psi\rangle\langle\psi\rvert}$ for an arbitrary pure state $\lvert\psi\rangle$ of finite dimension $d$. Unlike quantum programs that assume query access to $U$, our program takes the form of independent copies of the state to be reflected about $\lvert\psi_U\rangle = \lvert\psi\rangle^{\otimes n}$. We then identify the worst-case optimal algorithm among all processors of the form $\text{tr}_{\text{Program}}[V (\lvert\phi\rangle\langle\phi\rvert \otimes (\lvert\psi\rangle\langle\psi\rvert)^{\otimes n}) V^\dagger]$ where the algorithm $V$ is a unitary linear combination of permutations. By generalizing these algorithms to processors for arbitrary-angle rotations, $e^{i \alpha \lvert\psi\rangle\langle\psi\rvert}$ for $\alpha \in \mathbb R$, we give a construction for a universal programmable processor with better scaling in $d$. For programming reflections, we obtain a tight analytical lower bound on the program dimension by bounding the Holevo information of an ensemble of reflections applied to an entangled probe state. The lower bound makes use of a block decomposition of the uniform ensemble of reflected states with respect to irreps of the partially transposed permutation matrix algebra, and two representation-theoretic conjectures based on extensive numerical evidence.