Quantum Programmable Reflections

Abstract

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 $|\ddot{I}{ˆ}_U⟩$ 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\ddot{I}€|\ddot{I}ˆ⟩⟨\ddot{I}ˆ|}$ for an arbitrary pure state $|\ddot{I}ˆ⟩$ 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 $|\ddot{I}{ˆ}_U⟩=|\ddot{I}ˆ{⟩}^{\otimes n}$. We then identify the worst-case optimal algorithm among all processors of the form ${\text{tr}}_{\text{Program}}[V(|\ddot{I}•⟩⟨\ddot{I}•|\otimes (|\ddot{I}ˆ⟩⟨\ddot{I}ˆ|{)}^{\otimes n})V^{†}]$ where the algorithm $V$ is a unitary linear combination of permutations. By generalizing these algorithms to processors for arbitrary-angle rotations, $e^{i\hat{I}\pm |\ddot{I}ˆ⟩⟨\ddot{I}ˆ|}$ for $\hat{I}\pm \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.

Added complementary channel bound and refined conjectures. 63 pages, 5 figures