Exploiting all ancilla outcomes in linear combinations of unitaries: low-rank recovery and quantum trapdoor functions

Abstract

The linear combination of unitaries (LCU) is a fundamental quantum algorithm primitive that embeds non-unitary operators via post-selection on an ancilla register. In standard LCU, only the $|0\dots 0⟩$ ancilla outcome is retained; the remaining "junk" outcomes are discarded. We study these discarded parts by introducing an alternative LCU circuit which simplifies the coefficient preparation unitary with Hadamard gates and a single rotation qubit. Every computational basis measurement of the ancilla projects the system onto a different linear combination of the target unitaries. Collecting these outcome states and reshaping them into a $2K\times N$ matrix reveals a factorization $\Phi =CX$, where $C$ encodes the coefficients and $X$ contains the action of each unitary on the input; this immediately shows $\mathrm{rank}(\Phi )\le K$. This structure enables two complementary applications: (i) classical low-rank matrix completion can reconstruct the full output (including the target) from a fraction of its entries, turning every shot into useful information; (ii) treating $C$ as a secret key hides the input state, leading to a candidate quantum trapdoor function and symmetric encryption. The scheme thus turns the "junk" ancilla outcomes into a structured resource, possibly opening paths for further applications.

13 pages, 5 figures. Comments are welcome. In v2, the trapdoor function discussion is more formalized with showing that its security can be improved by using generic coefficient matrix as in LCU. The simulation code is publicly available on GitHub at https://github.com/adaskin/lcu-full-output-recovery