pith. sign in

arxiv: 2605.02986 · v2 · submitted 2026-05-04 · 🪐 quant-ph

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

Ammar Daskin This is my paper

Pith reviewed 2026-05-14 21:58 UTC · model grok-4.3

classification 🪐 quant-ph
keywords linear combination of unitariesLCUlow-rank matrix completionquantum trapdoor functionsancilla measurementspost-selectionquantum cryptographymatrix factorization
0
0 comments X

The pith

Redesigning the LCU circuit turns all ancilla outcomes into a low-rank matrix factorization that enables output reconstruction and quantum trapdoor functions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that an alternative LCU circuit, simplified with Hadamard gates and one rotation qubit, causes each ancilla measurement to project onto a unique linear combination of unitaries. Assembling these projections into a 2K by N matrix yields a factorization showing the rank is at most K. This low-rank structure permits classical matrix completion to recover the full output state from only a portion of the measured entries, converting every experimental shot into usable data. The coefficient matrix can additionally function as a secret key, enabling the construction of quantum trapdoor functions and symmetric encryption schemes that hide the input state. A reader would care because this repurposes previously discarded measurement outcomes as a structured resource for both computational efficiency and cryptographic applications in quantum computing.

Core claim

In the proposed alternative LCU circuit, 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×N matrix reveals a factorization Φ = C X, where C encodes the coefficients and X contains the action of each unitary on the input; this immediately shows rank(Φ)≤K. This structure enables classical low-rank matrix completion to reconstruct the full output from a fraction of its entries and treating C as a secret key to hide the input state for a candidate quantum trapdoor function and symmetric encryption.

What carries the argument

The low-rank factorization Φ = C X obtained by reshaping all ancilla outcome states into a matrix, with C as the coefficient matrix and X as the matrix of unitary actions on the input.

If this is right

  • The target linear combination output can be recovered using low-rank matrix completion from only a fraction of the ancilla measurement entries.
  • All ancilla outcomes contribute useful information rather than being discarded as junk.
  • The coefficient matrix C serves as a secret key for quantum trapdoor functions that obscure the input state.
  • Symmetric encryption schemes can be built around this structure for hiding quantum information.
  • The approach may lead to new applications by exploiting the structured nature of ancilla outcomes in LCU-based algorithms.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This could reduce the total number of quantum measurements needed for LCU-based algorithms by salvaging data from all shots.
  • The proposed trapdoor function invites further security analysis in the context of quantum cryptography.
  • Similar low-rank structures might be identifiable in the post-selected outcomes of other quantum algorithms.
  • Implementation on small-scale quantum devices could test whether matrix completion accurately reconstructs the expected LCU result.

Load-bearing premise

The alternative LCU circuit with Hadamard gates and a single rotation qubit correctly produces the claimed projections onto distinct linear combinations without introducing additional errors or violating unitarity.

What would settle it

If the assembled matrix of ancilla outcomes has rank higher than K, or if low-rank completion techniques fail to accurately recover the target output state from partial entries, the central claims would be falsified.

Figures

Figures reproduced from arXiv: 2605.02986 by Ammar Daskin.

Figure 1
Figure 1. Figure 1: Alternative circuit for LCU with K = 4 terms. The index register is placed in an equal superposition by Hadamard gates, then controls the application of Rt ⊗Ut on the rotation and system registers. After the controlled operations, a second set of Hadamard gates mixes the index states. Measurement of all ancilla qubits yields a collection of outcomes, each carrying a linear combination of the unitaries. the… view at source ↗
Figure 2
Figure 2. Figure 2: Success probabilities for K = 4, N = 16 with half the coefficients fixed to 1 and the other half varying from 0.1 to 1. The solid lines show simulation results; dashed lines are the analytic predictions. “With rotation qubit” corresponds to the strict post-selection on i = 0, r = 0 (probability p0,0). “Without rotation qubit” sums both rotation outcomes for index i = 0 (probability p0,0 + p0,1). Standard L… view at source ↗
Figure 3
Figure 3. Figure 3: Matrix completion of Φ (solid) and φ (dashed) for exact amplitudes. SVP (blue) shows a gradual improvement, while factorized recovery (red) drops to machine precision once the mask density guarantees ≥ K observed entries per column. Shaded bands: ±1 std. over 10 random instances and 5 masks. 10 5 10 4 10 3 10 2 Noise standard deviation ( ) 10 1 10 0 10 1 Relative error Shot noise recovery (obs. frac=0.7) K… view at source ↗
Figure 4
Figure 4. Figure 4: Recovery under additive complex Gaussian noise with observation fraction fixed at 70%. SVP (blue) view at source ↗
read the original 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\dots0\rangle$ 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 = C X$, where $C$ encodes the coefficients and $X$ contains the action of each unitary on the input; this immediately shows $\operatorname{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper introduces an alternative LCU circuit using Hadamard gates and a single rotation qubit on the ancilla. Every computational-basis ancilla outcome projects the system onto a distinct linear combination of the K target unitaries. Collecting the 2K outcome states and reshaping them into a 2K×N matrix Φ yields the factorization Φ = C X (C the coefficient matrix, X the action of each unitary), which immediately implies rank(Φ) ≤ K. The authors apply this structure to classical low-rank matrix completion for reconstructing the full output (including the desired LCU result) from a fraction of measured entries, and to a candidate quantum trapdoor function / symmetric encryption scheme in which C serves as the secret key that hides the input state.

Significance. If the circuit construction is correct, the result converts the usually discarded ancilla outcomes into a structured, low-rank resource. This could improve shot efficiency in LCU-based algorithms and supplies a concrete bridge between quantum measurement statistics and classical matrix-completion techniques. The trapdoor application, while preliminary, offers a new direction for quantum cryptography that exploits the same algebraic structure.

major comments (1)
  1. [Abstract and §3] Abstract and §3 (circuit construction): the central rank(Φ)≤K claim rests on the assertion that the proposed Hadamard-plus-rotation-qubit circuit produces exactly the claimed linear combinations without extra phases, normalization factors, or mixing that would enlarge the column space of X. No explicit circuit diagram, gate-by-gate derivation of the post-measurement states, or verification that the resulting 2K vectors lie in a K-dimensional subspace is supplied in the text; without this, the factorization Φ = C X cannot be confirmed and both applications are unsupported.
minor comments (2)
  1. [Abstract] The dimensions of Φ (2K×N) and the precise definition of the system dimension N should be stated explicitly when the matrix is first introduced, together with the relation between K (number of unitaries) and the ancilla register size.
  2. [§4] Notation for the coefficient matrix C and the unitary-action matrix X should be introduced with a short equation or diagram showing how each column of X is obtained from a single unitary applied to the input state.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback. We appreciate the positive assessment of the potential impact on shot efficiency and the bridge to classical matrix completion. We address the single major comment below and will revise the manuscript to incorporate the requested details.

read point-by-point responses

  1. Referee: [Abstract and §3] Abstract and §3 (circuit construction): the central rank(Φ)≤K claim rests on the assertion that the proposed Hadamard-plus-rotation-qubit circuit produces exactly the claimed linear combinations without extra phases, normalization factors, or mixing that would enlarge the column space of X. No explicit circuit diagram, gate-by-gate derivation of the post-measurement states, or verification that the resulting 2K vectors lie in a K-dimensional subspace is supplied in the text; without this, the factorization Φ = C X cannot be confirmed and both applications are unsupported.

    Authors: We agree that an explicit gate-by-gate derivation and circuit diagram are necessary to rigorously confirm the factorization Φ = C X and the rank bound. In the revised manuscript we will insert a detailed circuit diagram of the modified LCU (Hadamard-based coefficient preparation plus single rotation qubit) together with a step-by-step derivation of the post-measurement states for every computational-basis ancilla outcome. The derivation will explicitly track phases and normalization factors, demonstrate that each of the 2K states is a distinct linear combination of the K target unitaries, and verify that these 2K vectors span a subspace of dimension at most K, thereby establishing Φ = C X with rank(Φ) ≤ K. This addition will directly support the low-rank completion and trapdoor-function claims. revision: yes

Circularity Check

0 steps flagged

Rank bound follows directly from matrix construction; no circular reduction

full rationale

The central claim constructs the 2K×N matrix Φ explicitly from the ancilla outcome states, each defined as a distinct linear combination of the K unitaries. The factorization Φ = C X is therefore true by the definition of how the rows are assembled, making rank(Φ) ≤ K an immediate algebraic consequence rather than a nontrivial prediction or self-referential step. No equation reduces a claimed result to a fitted parameter, and the provided text contains no load-bearing self-citation whose validity depends on the present work. The circuit proposal itself is an external assumption whose correctness is independent of the subsequent matrix algebra.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard quantum circuit composition and linear-algebra rank properties once the modified LCU circuit is granted; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • standard math Standard properties of unitary operators and linear combinations in quantum mechanics
    The rank(Φ) ≤ K bound follows from the matrix factorization once the circuit is assumed to produce the stated projections.

pith-pipeline@v0.9.0 · 5533 in / 1276 out tokens · 47658 ms · 2026-05-14T21:58:05.743097+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · 1 internal anchor

  1. [1]

    Hamiltonian simulation using linear combinations of unitary op- erations.Quantum Information and Computation, 12(11&12):901–924, 2012

    Andrew M Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary op- erations.Quantum Information and Computation, 12(11&12):901–924, 2012

    work page 2012

  2. [2]

    Implementing any linear combination of unitaries on intermediate-term quan- tum computers.Quantum, 8:1496, 2024

    Shantanav Chakraborty. Implementing any linear combination of unitaries on intermediate-term quan- tum computers.Quantum, 8:1496, 2024

    work page 2024

  3. [3]

    Universal programmable quantum circuit schemes to emulate an operator.The Journal of chemical physics, 137(23), 2012

    Anmer Daskin, Ananth Grama, Giorgos Kollias, and Sabre Kais. Universal programmable quantum circuit schemes to emulate an operator.The Journal of chemical physics, 137(23), 2012

    work page 2012

  4. [4]

    Simulating hamiltonian dynamics with a truncated taylor se- ries.Physical review letters, 114(9):090502, 2015

    Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma. Simulating hamiltonian dynamics with a truncated taylor se- ries.Physical review letters, 114(9):090502, 2015

    work page 2015

  5. [5]

    Hamiltonian simulation and linear combination of unitary de- composition of structured matrices.arXiv preprint arXiv:2603.17816, 2026

    Robin Ollive and St´ ephane Louise. Hamiltonian simulation and linear combination of unitary de- composition of structured matrices.arXiv preprint arXiv:2603.17816, 2026

    work page arXiv 2026

  6. [6]

    A quantum compiler design method by using linear combinations of permutations.arXiv preprint arXiv:2404.18226, 2024

    Ammar Daskin. A quantum compiler design method by using linear combinations of permutations.arXiv preprint arXiv:2404.18226, 2024

    work page arXiv 2024

  7. [7]

    Hamiltonian simulation by qubitization.Quantum, 3:163, 2019

    Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization.Quantum, 3:163, 2019

    work page 2019

  8. [8]

    Quantum singular value transfor- mation and beyond: exponential improvements for quantum matrix arithmetics

    Andr´ as Gily´ en, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transfor- mation and beyond: exponential improvements for quantum matrix arithmetics. InProceedings of the 51st annual ACM SIGACT symposium on theory of computing, pages 193–204, 2019

    work page 2019

  9. [9]

    Low-rank matrix completion: A contempo- rary survey.IEEE Access, 7:94215–94237, 2019

    Luong Trung Nguyen, Junhan Kim, and Byonghyo Shim. Low-rank matrix completion: A contempo- rary survey.IEEE Access, 7:94215–94237, 2019

    work page 2019

  10. [10]

    Quantum circuits for general multiqubit gates.Physical review letters, 93(13):130502, 2004

    Mikko M¨ ott¨ onen, Juha J Vartiainen, Ville Bergholm, and Martti M Salomaa. Quantum circuits for general multiqubit gates.Physical review letters, 93(13):130502, 2004

    work page 2004

  11. [11]

    Synthesis of quantum cir- cuits for d-level systems by using cosine-sine decom- position.Quantum Information and Computation, 9(5&6):0423–0443, 2009

    Yumi Nakajima, Yasuhito Kawano, Hiroshi Seki- gawa, Masaki Nakanishi, Shigeru Yamashita, and Yasuhiko Nakashima. Synthesis of quantum cir- cuits for d-level systems by using cosine-sine decom- position.Quantum Information and Computation, 9(5&6):0423–0443, 2009

    work page 2009

  12. [12]

    Qcompiler: Quantum com- pilation with the csd method.Computer Physics Communications, 184(3):853–865, 2013

    YG Chen and JB Wang. Qcompiler: Quantum com- pilation with the csd method.Computer Physics Communications, 184(3):853–865, 2013

    work page 2013

  13. [13]

    Efficient quantum state tomogra- phy.Nature communications, 1(1):149, 2010

    Marcus Cramer, Martin B Plenio, Steven T Flam- mia, Rolando Somma, David Gross, Stephen D Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu. Efficient quantum state tomogra- phy.Nature communications, 1(1):149, 2010

    work page 2010

  14. [14]

    Quantum state to- mography via compressed sensing.Physical review letters, 105(15):150401, 2010

    David Gross, Yi-Kai Liu, Steven T Flammia, Stephen Becker, and Jens Eisert. Quantum state to- mography via compressed sensing.Physical review letters, 105(15):150401, 2010

    work page 2010

  15. [15]

    An overview of low-rank matrix recovery from incom- plete observations.IEEE Journal of Selected Topics in Signal Processing, 10(4):608–622, 2016

    Mark A Davenport and Justin Romberg. An overview of low-rank matrix recovery from incom- plete observations.IEEE Journal of Selected Topics in Signal Processing, 10(4):608–622, 2016

    work page 2016

  16. [16]

    Guaranteed rank minimization via singular value projection.Advances in Neural Information Pro- cessing Systems, 23, 2010

    Prateek Jain, Raghu Meka, and Inderjit Dhillon. Guaranteed rank minimization via singular value projection.Advances in Neural Information Pro- cessing Systems, 23, 2010

    work page 2010

  17. [17]

    Exact ma- trix completion via convex optimization.Commu- nications of the ACM, 55(6):111–119, 2012

    Emmanuel Candes and Benjamin Recht. Exact ma- trix completion via convex optimization.Commu- nications of the ACM, 55(6):111–119, 2012

    work page 2012

  18. [18]

    A singular value thresholding algorithm for matrix completion.SIAM Journal on optimization, 20(4):1956–1982, 2010

    Jian-Feng Cai, Emmanuel J Cand` es, and Zuowei Shen. A singular value thresholding algorithm for matrix completion.SIAM Journal on optimization, 20(4):1956–1982, 2010

    work page 1956

  19. [19]

    Matrix factorization techniques for recommender systems.Computer, 42(8):30–37, 2009

    Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems.Computer, 42(8):30–37, 2009

    work page 2009

  20. [20]

    A crypto- graphic test of quantumness and certifiable random- ness from a single quantum device.Journal of the ACM (JACM), 68(5):1–47, 2021

    Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. A crypto- graphic test of quantumness and certifiable random- ness from a single quantum device.Journal of the ACM (JACM), 68(5):1–47, 2021

    work page 2021

  21. [21]

    Quantum trapdoor functions from classical one-way functions.arXiv preprint arXiv:2302.12821, 2023

    Andrea Coladangelo. Quantum trapdoor functions from classical one-way functions.arXiv preprint arXiv:2302.12821, 2023. 12

    work page arXiv 2023

  22. [22]

    Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more.arXiv preprint arXiv:2201.13445, 2022

    Alexandru Gheorghiu, Tony Metger, and Alexan- der Poremba. Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more.arXiv preprint arXiv:2201.13445, 2022

    work page arXiv 2022

  23. [23]

    Quantum ho- momorphic encryption for circuits of low t-gate com- plexity

    Anne Broadbent and Stacey Jeffery. Quantum ho- momorphic encryption for circuits of low t-gate com- plexity. InAnnual Cryptology Conference, pages 609–629. Springer, 2015

    work page 2015

  24. [24]

    Experimental investigation of prac- tical unforgeable quantum money.npj Quantum In- formation, 4(1):5, 2018

    Mathieu Bozzio, Adeline Orieux, Luis Trigo Vi- darte, Isabelle Zaquine, Iordanis Kerenidis, and Eleni Diamanti. Experimental investigation of prac- tical unforgeable quantum money.npj Quantum In- formation, 4(1):5, 2018

    work page 2018

  25. [25]

    On Quantum Obfuscation

    Gorjan Alagic and Bill Fefferman. On quantum ob- fuscation.arXiv preprint arXiv:1602.01771, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  26. [26]

    Quantum state obfuscation from classical oracles

    James Bartusek, Zvika Brakerski, and Vinod Vaikuntanathan. Quantum state obfuscation from classical oracles. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1009–1017, 2024

    work page 2024

  27. [27]

    Pseudo- random quantum states

    Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudo- random quantum states. InAnnual International Cryptology Conference, pages 126–152. Springer, 2018

    work page 2018

  28. [28]

    (pseudo) ran- dom quantum states with binary phase

    Zvika Brakerski and Omri Shmueli. (pseudo) ran- dom quantum states with binary phase. InTheory of Cryptography Conference, pages 229–250. Springer, 2019

    work page 2019

  29. [29]

    On the complexity of nonneg- ative matrix factorization.SIAM journal on opti- mization, 20(3):1364–1377, 2010

    Stephen A Vavasis. On the complexity of nonneg- ative matrix factorization.SIAM journal on opti- mization, 20(3):1364–1377, 2010

    work page 2010

  30. [30]

    Exact recovery of sparsely-used dictionaries

    Daniel A Spielman, Huan Wang, and John Wright. Exact recovery of sparsely-used dictionaries. In Conference on Learning Theory, pages 37–1. JMLR Workshop and Conference Proceedings, 2012

    work page 2012

  31. [31]

    Phase retrieval via matrix completion.SIAM review, 57(2):225–251, 2015

    Emmanuel J Candes, Yonina C Eldar, Thomas Strohmer, and Vladislav Voroninski. Phase retrieval via matrix completion.SIAM review, 57(2):225–251, 2015

    work page 2015

  32. [32]

    Fast, sample- efficient algorithms for structured phase retrieval

    Gauri Jagatap and Chinmay Hegde. Fast, sample- efficient algorithms for structured phase retrieval. Advances in Neural Information Processing Sys- tems, 30, 2017

    work page 2017

  33. [33]

    Extended successive convex approxi- mation for phase retrieval with dictionary learning

    Andreas M Tillmann, Yonina C Eldar, Marius Pe- savento, et al. Extended successive convex approxi- mation for phase retrieval with dictionary learning. IEEE Transactions on Signal Processing, 70:6300– 6315, 2023

    work page 2023

  34. [34]

    New algorithms for learning incoherent and overcomplete dictionaries

    Sanjeev Arora, Rong Ge, and Ankur Moitra. New algorithms for learning incoherent and overcomplete dictionaries. InConference on Learning Theory, pages 779–806. PMLR, 2014

    work page 2014

  35. [35]

    Link analysis ranking: algorithms, theory, and experiments

    Allan Borodin, Gareth O Roberts, Jeffrey S Rosen- thal, and Panayiotis Tsaparas. Link analysis ranking: algorithms, theory, and experiments. ACM Transactions on Internet Technology (TOIT), 5(1):231–297, 2005. 13

    work page 2005