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 computing primitive used to embed non-unitary operators into larger systems via ancilla post-selection. In standard LCU implementations, only the zero-state ancilla outcome is retained, while all other measurement branches are discarded as unusable overhead. We study these discarded parts. Every computational-basis outcome of the ancilla projects the system onto a different linear combination of the target unitaries; collecting these outcome states in a matrix gives a factorization Φ=CX, where C is determined by the ancilla preparation and the rows of X are the states Ut|ψ⟩, so that rank(Φ)≤ K. Although this holds for any LCU circuit; to make the analysis easier, we use a simplified model circuit with Hadamard gates on the index register and a single rotation qubit in place of the coefficient preparation unitary, in which C is explicit. The structure suggests two complementary applications: (i) in an explicit amplitude-access model, classical low-rank matrix completion can reconstruct the full output (including the target) from a subset of its amplitude entries, while computational basis counts provide intensities and generally require additional phase information for full complex recovery; (ii) treating C as a secret key suggests a candidate quantum trapdoor function, whose security remains informal and depends on the difficulty of structured phase retrieval. The scheme thus turns the "junk" ancilla outcomes into a structured resource, possibly opening paths for further applications.
Related
- Characterizing unitaries via quasi-process functions
- Generating random unitaries by products of conjugated Hamiltonian evolutions
- Low-Depth Random Unitaries without Ancillae
- Optimal Quantum-Circuit Synthesis and Implementation of General Unitaries with Parallelized Bitstring-Conditioned Rotations
- A Catalytic Algorithm for Transposing Unknown Qutrit Unitaries with Tight Query Bounds
BibTeX
@misc{daskin2026exploiting,
title = {{Exploiting all ancilla outcomes in linear combinations of unitaries: low-rank recovery and quantum trapdoor functions}},
author = {Ammar Daskin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.02986},
eprint = {2605.02986},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.02986},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exploiting all ancilla outcomes in linear combinations of unitaries: low-rank recovery and quantum trapdoor functions
AU - Ammar Daskin
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2605.02986
UR - https://arxiv.org/abs/2605.02986
AB - The linear combination of unitaries (LCU) is a fundamental quantum computing primitive used to embed non-unitary operators into larger systems via ancilla post-selection. In standard LCU implementations, only the zero-state ancilla outcome is retained, while all other measurement branches are discarded as unusable overhead. We study these discarded parts. Every computational-basis outcome of the ancilla projects the system onto a different linear combination of the target unitaries; collecting these outcome states in a matrix gives a factorization Φ=CX, where C is determined by the ancilla preparation and the rows of X are the states U_t|ψ⟩, so that rank(Φ)≤ K. Although this holds for any LCU circuit; to make the analysis easier, we use a simplified model circuit with Hadamard gates on the index register and a single rotation qubit in place of the coefficient preparation unitary, in which C is explicit. The structure suggests two complementary applications: (i) in an explicit amplitude-access model, classical low-rank matrix completion can reconstruct the full output (including the target) from a subset of its amplitude entries, while computational basis counts provide intensities and generally require additional phase information for full complex recovery; (ii) treating C as a secret key suggests a candidate quantum trapdoor function, whose security remains informal and depends on the difficulty of structured phase retrieval. The scheme thus turns the "junk" ancilla outcomes into a structured resource, possibly opening paths for further applications.
ER -