⚛️ quantum physics

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

This paper proposes a method to transform discarded ancilla measurement outcomes in Linear Combinations of Unitaries (LCU) circuits into a structured low-rank resource, enabling applications such as classical low-rank matrix completion for state reconstruction and the construction of candidate quantum trapdoor functions.

Original authors: Ammar Daskin

Published 2026-10-27

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ammar Daskin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of quantum computing, scientists work with machines that process information in ways fundamentally different from the laptops and phones we use every day. These quantum devices rely on delicate states of matter that can exist in multiple possibilities at once, a property that allows them to solve certain problems with incredible speed. However, a major hurdle in building useful quantum computers is that they are notoriously fragile. When a quantum computer performs a calculation, it often involves a process called post-selection, where the machine runs a complex operation and then checks a specific result. If the result is exactly what was hoped for, the calculation is kept; if it is anything else, the entire attempt is discarded as a failure, and the machine must start over. This waste of effort is a significant bottleneck, as the discarded attempts are usually thrown away without a second thought, treated as mere noise in the system.

A researcher named Ammar Daskin from Istanbul Medeniyet University has proposed a new way of looking at this discarded information. In a recent study, he explored what happens when we stop throwing away the "failed" outcomes of a specific type of quantum calculation known as a linear combination of unitaries. Instead of viewing these outcomes as useless errors, Daskin showed that they actually contain a hidden, organized structure. By collecting all the possible results from a single run of the circuit, including the ones usually ignored, the data forms a pattern that can be mathematically reconstructed. This discovery suggests that what was once considered waste could be turned into a valuable resource, potentially allowing scientists to recover the full answer to a problem from just a fraction of the data, or even to create new types of secure communication methods that rely on the difficulty of decoding this hidden structure.

The core of Daskin's work involves a standard quantum technique used to combine different operations into a single, more complex one. In a typical setup, a quantum computer uses a set of extra helper bits, called ancilla qubits, to manage the coefficients of the calculation. The machine prepares these helper bits in a specific state, performs the calculation, and then checks the helper bits. If the helper bits return to their starting position, the main calculation is considered successful. In the standard method, any other position the helper bits end up in is treated as a mistake, and the corresponding result is discarded. Daskin decided to investigate these "mistakes" by simplifying the circuit design. He replaced the complex machinery usually used to prepare the helper bits with a straightforward arrangement of basic quantum gates, specifically using a set of gates that create an equal mix of possibilities and a single rotating gate to control the weights of the calculation.

When this simplified circuit runs, it produces a variety of outcomes based on how the helper bits are measured. Daskin found that if you take the results from every possible measurement outcome and stack them together, they form a large grid of data. This grid has a remarkable property: it can be broken down into two smaller pieces that multiply together to recreate the whole. One piece is a known pattern determined by the circuit's design, and the other piece contains the actual results of the individual operations the computer was trying to perform. Because the circuit only generates a limited number of independent combinations, the entire large grid is mathematically "low-rank," meaning it is much simpler than it appears on the surface. This structure implies that the full answer to the calculation is hidden within the data, even if you only have access to a small portion of it.

To test this idea, the researcher simulated the circuit on a computer to see if the full output could be recovered from partial information. The simulations showed that if you know the design of the circuit, you can use classical mathematical techniques to fill in the missing parts of the data grid. By observing just a subset of the results, the algorithm could reconstruct the entire matrix of outcomes, including the specific result that the standard method would have kept. This recovery works best when the data is clean, but the study also examined how the method holds up when the data is noisy, mimicking the errors that occur in real quantum hardware. The results indicated that while the method is robust, it requires a significant amount of data to work reliably when the measurements are imperfect. The study suggests that in a real-world scenario where only the intensity of the signals is measured, rather than the full complex values, additional steps would be needed to recover the complete information, but the underlying structure remains a powerful tool for reconstruction.

Beyond the practical application of recovering data, this finding opens a door to a new kind of cryptographic idea. The researcher proposed that the specific pattern used to mix the results in the circuit could be kept secret, acting like a private key. If an observer sees the final grid of data but does not know the secret mixing pattern, they would face a difficult mathematical puzzle to figure out what the original input was. This is similar to a lock where the key is hidden inside the mechanism itself. However, the study is careful to note that this is only a candidate for a secure system. The security relies on the difficulty of solving a specific type of problem known as phase retrieval, which involves figuring out the hidden details of a wave from its intensity. While this problem is known to be hard, the researcher has not proven that it is impossible to break, and the system's security depends on the assumption that no one can find a shortcut to solve it.

The paper also explores how this structure could be used in other ways, such as in recommendation systems or ranking algorithms, where large amounts of data are broken down into simpler components. The mathematical relationship found in the quantum circuit mirrors techniques used in classical computing to predict user preferences or analyze links between web pages. By treating the quantum circuit as a way to generate these patterns, the researcher suggests that quantum computers could offer a new way to perform these tasks. The study concludes that by changing how we view the output of quantum circuits, we can turn what was once considered waste into a structured resource. This approach does not just improve the efficiency of current calculations but also suggests new possibilities for how quantum information can be stored, recovered, and protected. The work remains a theoretical proposal supported by simulations, but it offers a clear path for future experiments to see if these "junk" outcomes can indeed be harnessed to build more powerful and secure quantum technologies.

Technical Summary: Exploiting All Ancilla Outcomes in Linear Combinations of Unitaries

Problem Statement
The Linear Combination of Unitaries (LCU) is a fundamental primitive in quantum computing used to implement non-unitary operators $T = \sum \alpha_t U_t$ by embedding them into larger unitary systems via ancilla registers. In standard LCU implementations, the process relies on post-selection: only the ancilla outcome corresponding to the $|0\dots0\rangle$ state is retained, while all other measurement branches ("junk" outcomes) are discarded as overhead. The paper investigates the information contained within these discarded branches, questioning whether they possess exploitable structure that can be collectively processed rather than wasted.

Methodology
The author proposes a simplified model circuit that generalizes standard LCU designs to make the structure of all ancilla outcomes explicit.

Circuit Design: Instead of a complex coefficient-preparation unitary, the model uses an index register initialized with Hadamard gates (creating an equal superposition) and a single rotation qubit. The rotation qubit applies two-channel rotation gates $R_t$ controlled by the index, where the rotation angles are set such that the top-left entry equals the desired coefficient $\alpha_t$ (scaled to $\le 1$ ).
State Evolution: After controlled applications of $R_t \otimes U_t$ and a second round of Hadamard gates on the index register, the system is measured in the computational basis.
Matrix Factorization: The author demonstrates that collecting the unnormalized system states resulting from every computational-basis outcome of the ancilla (index and rotation) into a matrix $\Phi$ reveals a low-rank factorization:
$\Phi = CX$
Here, $C$ is a known $2K \times K$ coefficient matrix determined by the Hadamard signs and rotation weights ( $w_t, r_t$ ), and $X$ is a $K \times N$ matrix where the rows correspond to the states $U_t |\psi\rangle$ .
Algebraic Analysis: The paper analyzes the unitary matrix representation of the circuit, showing it can be permuted into a $2 \times 2$ block structure. It derives the eigenvalues and singular values of the resulting operators, noting that the diagonal blocks encode the target linear combination $D_w = \sum w_t U_t$ and a complementary combination $D_r = \sum r_t U_t$ .

Key Contributions

Structured "Junk" Outcomes: The paper establishes that for any LCU circuit, the discarded ancilla outcomes are not random noise but form a structured set of linear combinations. Specifically, the full output matrix $\Phi$ has a rank of at most $K$ , despite having dimensions $2K \times N$ .
Low-Rank Recovery: In an amplitude-access model (where complex amplitudes are available), the full output matrix $\Phi$ can be reconstructed from a subset of entries using classical low-rank matrix completion techniques (e.g., Singular Value Projection or Alternating Least Squares). If the coefficient matrix $C$ is known, the recovery problem simplifies to solving a linear least-squares problem for $X$ , requiring only $K$ observed entries per column.
Quantum Trapdoor Candidate: The author proposes an informal candidate for a quantum trapdoor function. If the coefficients $w_t$ $w_{t}$ (and thus matrix $C$ $C$ ) are kept secret, the factorization $\Phi = CX$ $Φ = C X$ suggests a one-way function.
- Vulnerability: If the mixing unitary is a public Hadamard matrix and an adversary has full complex amplitude information (via tomography), the secret key can be trivially recovered via linear algebra.
- Hardness: Under realistic computational-basis measurements, the adversary only observes squared magnitudes $|\Phi_{ij}|^2$ . Recovering the secret key then becomes a structured phase-retrieval problem (specifically, blind dictionary learning under magnitude constraints), which is computationally difficult but not formally proven to be hard for this specific family.
- Strengthening: The paper suggests replacing the public Hadamard matrix with a secret generic mixing unitary $W$ to increase security, though this remains an informal candidate.

Results

Numerical Simulations: The author presents simulations for $K=4$ $K = 4$ and $K=8$ $K = 8$ with varying system sizes ( $N=256, 1024$ $N = 256, 1024$ ).
- Recovery: The factorized recovery method (using known $C$ ) shows a sharp drop in error once the observation fraction exceeds the threshold where every column has at least $K$ entries. Generic Singular Value Projection (SVP) shows a smoother error reduction but requires more data to converge.
- Noise: Under additive complex Gaussian noise, SVP acts as a more effective global denoiser compared to the factorized method, which is more sensitive to noise in individual columns.
Success Probability: The simplified model circuit generally yields a lower post-selection probability for the specific "target" outcome compared to optimized standard LCU, but the trade-off is the explicit generation of the full structured output matrix.

Significance and Claims
The paper claims to turn the "junk" ancilla outcomes of LCU circuits into a structured resource. Its significance lies in two complementary avenues:

Algorithmic: It provides a framework for recovering full quantum state information from partial measurements using classical low-rank matrix completion, potentially applicable to recommendation systems (via matrix factorization analogies) and linear algebra primitives.
Cryptographic: It introduces a candidate quantum trapdoor function based on the difficulty of structured phase retrieval. The author is modest in their claims, explicitly stating that the security is "informal" and depends on the hardness of structured phase retrieval and dictionary learning. They do not claim to have proven the one-wayness or confidentiality of the scheme, noting that the basic Hadamard-based version is vulnerable to linear attacks if full tomography is possible.

The work suggests that the algebraic structure of LCU circuits extends beyond the standard post-selected subspace, offering new perspectives on quantum circuit design, state recovery, and potential cryptographic primitives, while acknowledging that formal security reductions and finite-shot recovery from counts remain future work.

Technical Summary: Exploiting All Ancilla Outcomes in Linear Combinations of Unitaries

More like this