Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2605.02986

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

Ammar Daskin

quant-phSubmitted May 4, 2026• Announced May 5, 2026• 0 citations• Revised Oct 26, 2026 (v3)
v1 · May 4, 2026v2 · May 13, 2026v3 · Oct 26, 2026v4 · Oct 27, 2026
arXivHTMLPDF

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 $U_t|ψ\rangle$, so that $rank(Φ)\le K$. 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.

Comments
The simulation code is publicly available on GitHub at https://github.com/adaskin/lcu-full-output-recovery

Related papers

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

Daskin Ammar

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.

•May 4, 2026•0 citations

Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers

Shantanav Chakraborty

We develop three new methods to implement any Linear Combination of Unitaries (LCU), a powerful quantum algorithmic tool with diverse applications. While the standard LCU procedure requires several ancilla qubits and sophisticated multi-qubit controlled operations, our methods consume significantly fewer quantum resources. The first method ( Single-Ancilla LCU ) estimates expectation values of observables with respect to any quantum state prepared by an LCU procedure while requiring only a single ancilla qubit, and no multi-qubit controlled operations. The second approach ( Analog LCU ) is a simple, physically motivated, continuous-time analogue of LCU, tailored to hybrid qubit-qumode systems. The third method ( Ancilla-free LCU ) requires no ancilla qubit at all and is useful when we are interested in the projection of a quantum state (prepared by the LCU procedure) in some subspace of interest. We apply the first two techniques to develop new quantum algorithms for a wide range of practical problems, ranging from Hamiltonian simulation, ground state preparation and property estimation, and quantum linear systems. Remarkably, despite consuming fewer quantum resources they retain a provable quantum advantage. The third technique allows us to connect discrete and continuous-time quantum walks with their classical counterparts. It also unifies the recently developed optimal quantum spatial search algorithms in both these frameworks, and leads to the development of new ones that require fewer ancilla qubits. Overall, our results are quite generic and can be readily applied to other problems, even beyond those considered here.

arXiv:2302.13555•Quantum•Oct 10, 2024•34 citations

Trade-offs between Quantum and Classical Resources in the Linear Combination of Unitaries

Kaito Wada, Hiroyuki Harada, Yasunari Suzuki +3 more

The randomized linear combination of unitaries (LCU) method with many applications to early fault-tolerant quantum computing algorithms has been proposed. This quantum algorithm computes the same expectation values as the original, fully coherent LCU algorithm using a shallower quantum circuit with a single ancilla qubit, at the cost of a quadratically larger sampling overhead. In this work, we propose a quantum algorithm intermediate between the original and randomized LCU that manages the trade-off between the sampling overhead and circuit complexity. Our algorithm divides the set of unitary operators into several groups and then randomly samples LCU circuits from these groups to evaluate the target expectation value. Notably, we reveal that across all grouping strategies, the mechanism of the sampling overhead reduction can be solely characterized by a metric we call the reduction factor. Moreover, we analytically prove an underlying monotonicity of the reduction factor in the group size: larger group sizes entail smaller sampling overhead. Finally, our framework enables a more flexible algorithmic design by systematically yielding intermediate implementations of LCU-based algorithms; we provide intermediate implementations of non-Hermitian dynamics simulation, ground-state property estimation, and quantum error detection. Besides, we demonstrate this principle by deriving intermediate trade-off scaling in sample complexity and ancillary space for quantum linear system solver.

quant-pharXiv:2512.06260•Dec 9, 2025•0 citations

Efficient Application of the Factorized form of the Unitary Coupled-Cluster Ansatz for the Variational Quantum Eigensolver Algorithm by Using Linear Combination of Unitaries

Luogen Xu, James K. Freericks

The variational quantum eigensolver is one of the most promising algorithms for near-term quantum computers. It has the potential to solve quantum chemistry problems involving strongly correlated electrons with relatively low-depth circuits, which are otherwise difficult to solve on classical computers. The variational eigenstate is constructed from a number of factorized unitary coupled-cluster terms applied onto an initial (single-reference) state. Current algorithms for applying one of these operators to a quantum state require a number of operations that scale exponentially with the rank of the operator. We exploit a hidden SU(2) symmetry to allow us to employ the linear combination of unitaries approach, Our Prepare subroutine uses n+2 ancilla qubits for a rank-n operator. Our Select(U^) scheme uses O(n)Cnot gates. This results in a full algorithm that scales like the cube of the rank of the operator n3, a significant reduction in complexity for rank five or higher operators. This approach, when combined with other algorithms for lower-rank operators (when compared to the standard implementation), will make the factorized form of the unitary coupled-cluster approach much more efficient to implement on all types of quantum computers.

arXiv:2302.08679•Symmetry•Jul 16, 2023•3 citations

Asymmetric Linear-Combination-of-Unitaries Realization of Quantum Convolution via Modular Adders

Chen Yang, Kodai Kanemaru, Norio Yoshida +2 more

Discrete circular convolution over $\mathbb{Z}/N\mathbb{Z}$ is a linear operator and can be implemented on quantum hardware within the linear-combination-of-unitaries (LCU) framework. In this work, we make this connection explicit through an asymmetric-LCU formulation: circular convolution is the postselected block of a circuit whose controlled-shift unitary is modular addition on computational-basis states. The asymmetry is essential: fixing the postselection state to the uniform state $|u\rangle$ while supplying the kernel state $|\mathbf{b}\rangle$ as the input ancilla naturally preserves the complex coefficients $b_i$ within the block, whereas a symmetric overlap would yield $|b_i|^2$ weights and erase their phases. Accordingly, when $|\mathbf{a}\rangle$ and $|\mathbf{b}\rangle$ are supplied by upstream quantum routines, the convolution subroutine requires only the fixed uncompute $\mathrm{PREP}_u^\dagger$, completely avoiding the need for a kernel-dependent inverse preparation $\mathrm{PREP}_b^\dagger$. We then introduce a reversal matrix $J_n=X^{\otimes n}$ and define reflected shifts $\widetilde{L}_{i,n}=L_{i,n}J_n$. This symmetrization yields a recursive operator algebra for convolution that is natively compatible with LCU/block-encoding workflows. The resulting symmetrized operator differs from circular convolution only by one known input-side $J_n$ layer. Crucially, for real-valued kernels, the resulting operator $H_n(\mathbf{b})=\sum_i b_i\widetilde{L}_{i,n}$ is Hermitian, providing a direct Hermitian interface for quantum singular value transformation (QSVT) and related spectral transformations. Based on this framework, we present a transparent recursive construction, paired with an exactly equivalent optimized bitwise compilation of the same $\mathrm{SELECT}$ block. Finally, we evaluate implementation trade-offs and resource scaling under explicit cost-model conventions.

quant-pharXiv:2603.15214•Mar 17, 2026•0 citations

Lowering LCU Circuit Width through Maximum-Weight Birkhoff-von Neumann Decomposition

Ammar Daskin

Any square matrix can be transformed into a doubly stochastic matrix via Sinkhorn scaling with diagonal matrices or simply completing to a larger dimensional matrix. Standard Birkhoff-von~Neumann and Pauli decompositions represent such matrices as linear combinations of $O(N^2)$ permutation or Pauli terms, leading to a large ancilla overhead in a quantum Linear Combination of Unitaries (LCU) implementation. We prove that a bottleneck variant of Birkhoff's algorithm reduces the number of permutations to $O(N\log(1/\varepsilon))$, where $\varepsilon$ is the $\ell_1$-norm approximation error of the reconstructed matrix, and demonstrate empirically that a largest‑weight greedy variant requires only $\approx 2N$ terms for dense matrices (the exact average observed is $\approx 2.4N$). The quadratic reduction in term count directly shrinks the ancilla register from $2\log_2 N$ to $\log_2 N$ qubits, shortens the SELECT circuit, and is especially valuable in fixed‑Hadamard LCU architectures whose success probability scales with $1/K$. The approach enables compact quantum implementations of dense operators appearing in optimal transport, non‑Hermitian simulation, and other settings amenable to Sinkhorn preconditioning. Furthermore, because the decomposition is a convex combination, the LCU normalization constant is exactly $\alpha = 1$, and the uniform superposition is an eigenvector of the target matrix with eigenvalue~1. This structure can be exploited to achieve high success probability without amplitude amplification in many practical scenarios, including quantum walks and Markov chain simulations.

•May 19, 2026•0 citations
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Φ=CXΦ=CX, where CCC is determined by the ancilla preparation and the rows of XXX are the states Ut∣ψ⟩U_t|ψ\rangleUt​∣ψ⟩, so that rank(Φ)≤Krank(Φ)\le Krank(Φ)≤K. 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 CCC 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 CCC 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.
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…0⟩|0\dots0\rangle∣0…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×N2K\times N2K×N matrix reveals a factorization Φ=CX\Phi = C XΦ=CX, where CCC encodes the coefficients and XXX contains the action of each unitary on the input; this immediately shows rank⁡(Φ)≤K\operatorname{rank}(\Phi)\le Krank(Φ)≤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 CCC 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.
We develop three new methods to implement any Linear Combination of Unitaries (LCU), a powerful quantum algorithmic tool with diverse applications. While the standard LCU procedure requires several ancilla qubits and sophisticated multi-qubit controlled operations, our methods consume significantly fewer quantum resources. The first method ( Single-Ancilla LCU ) estimates expectation values of observables with respect to any quantum state prepared by an LCU procedure while requiring only a single ancilla qubit, and no multi-qubit controlled operations. The second approach ( Analog LCU ) is a simple, physically motivated, continuous-time analogue of LCU, tailored to hybrid qubit-qumode systems. The third method ( Ancilla-free LCU ) requires no ancilla qubit at all and is useful when we are interested in the projection of a quantum state (prepared by the LCU procedure) in some subspace of interest. We apply the first two techniques to develop new quantum algorithms for a wide range of practical problems, ranging from Hamiltonian simulation, ground state preparation and property estimation, and quantum linear systems. Remarkably, despite consuming fewer quantum resources they retain a provable quantum advantage. The third technique allows us to connect discrete and continuous-time quantum walks with their classical counterparts. It also unifies the recently developed optimal quantum spatial search algorithms in both these frameworks, and leads to the development of new ones that require fewer ancilla qubits. Overall, our results are quite generic and can be readily applied to other problems, even beyond those considered here.
The randomized linear combination of unitaries (LCU) method with many applications to early fault-tolerant quantum computing algorithms has been proposed. This quantum algorithm computes the same expectation values as the original, fully coherent LCU algorithm using a shallower quantum circuit with a single ancilla qubit, at the cost of a quadratically larger sampling overhead. In this work, we propose a quantum algorithm intermediate between the original and randomized LCU that manages the trade-off between the sampling overhead and circuit complexity. Our algorithm divides the set of unitary operators into several groups and then randomly samples LCU circuits from these groups to evaluate the target expectation value. Notably, we reveal that across all grouping strategies, the mechanism of the sampling overhead reduction can be solely characterized by a metric we call the reduction factor. Moreover, we analytically prove an underlying monotonicity of the reduction factor in the group size: larger group sizes entail smaller sampling overhead. Finally, our framework enables a more flexible algorithmic design by systematically yielding intermediate implementations of LCU-based algorithms; we provide intermediate implementations of non-Hermitian dynamics simulation, ground-state property estimation, and quantum error detection. Besides, we demonstrate this principle by deriving intermediate trade-off scaling in sample complexity and ancillary space for quantum linear system solver.
The variational quantum eigensolver is one of the most promising algorithms for near-term quantum computers. It has the potential to solve quantum chemistry problems involving strongly correlated electrons with relatively low-depth circuits, which are otherwise difficult to solve on classical computers. The variational eigenstate is constructed from a number of factorized unitary coupled-cluster terms applied onto an initial (single-reference) state. Current algorithms for applying one of these operators to a quantum state require a number of operations that scale exponentially with the rank of the operator. We exploit a hidden SU(2) symmetry to allow us to employ the linear combination of unitaries approach, Our Prepare subroutine uses n+2 ancilla qubits for a rank-n operator. Our Select(U^) scheme uses O(n)Cnot gates. This results in a full algorithm that scales like the cube of the rank of the operator n3, a significant reduction in complexity for rank five or higher operators. This approach, when combined with other algorithms for lower-rank operators (when compared to the standard implementation), will make the factorized form of the unitary coupled-cluster approach much more efficient to implement on all types of quantum computers.
Discrete circular convolution over Z/NZ\mathbb{Z}/N\mathbb{Z}Z/NZ is a linear operator and can be implemented on quantum hardware within the linear-combination-of-unitaries (LCU) framework. In this work, we make this connection explicit through an asymmetric-LCU formulation: circular convolution is the postselected block of a circuit whose controlled-shift unitary is modular addition on computational-basis states. The asymmetry is essential: fixing the postselection state to the uniform state ∣u⟩|u\rangle∣u⟩ while supplying the kernel state ∣b⟩|\mathbf{b}\rangle∣b⟩ as the input ancilla naturally preserves the complex coefficients bib_ibi​ within the block, whereas a symmetric overlap would yield ∣bi∣2|b_i|^2∣bi​∣2 weights and erase their phases. Accordingly, when ∣a⟩|\mathbf{a}\rangle∣a⟩ and ∣b⟩|\mathbf{b}\rangle∣b⟩ are supplied by upstream quantum routines, the convolution subroutine requires only the fixed uncompute PREPu†\mathrm{PREP}_u^\daggerPREPu†​, completely avoiding the need for a kernel-dependent inverse preparation PREPb†\mathrm{PREP}_b^\daggerPREPb†​. We then introduce a reversal matrix Jn=X⊗nJ_n=X^{\otimes n}Jn​=X⊗n and define reflected shifts L~i,n=Li,nJn\widetilde{L}_{i,n}=L_{i,n}J_nLi,n​=Li,n​Jn​. This symmetrization yields a recursive operator algebra for convolution that is natively compatible with LCU/block-encoding workflows. The resulting symmetrized operator differs from circular convolution only by one known input-side JnJ_nJn​ layer. Crucially, for real-valued kernels, the resulting operator Hn(b)=∑ibiL~i,nH_n(\mathbf{b})=\sum_i b_i\widetilde{L}_{i,n}Hn​(b)=∑i​bi​Li,n​ is Hermitian, providing a direct Hermitian interface for quantum singular value transformation (QSVT) and related spectral transformations. Based on this framework, we present a transparent recursive construction, paired with an exactly equivalent optimized bitwise compilation of the same SELECT\mathrm{SELECT}SELECT block. Finally, we evaluate implementation trade-offs and resource scaling under explicit cost-model conventions.
Any square matrix can be transformed into a doubly stochastic matrix via Sinkhorn scaling with diagonal matrices or simply completing to a larger dimensional matrix. Standard Birkhoff-von~Neumann and Pauli decompositions represent such matrices as linear combinations of O(N2)O(N^2)O(N2) permutation or Pauli terms, leading to a large ancilla overhead in a quantum Linear Combination of Unitaries (LCU) implementation. We prove that a bottleneck variant of Birkhoff's algorithm reduces the number of permutations to O(Nlog⁡(1/ε))O(N\log(1/\varepsilon))O(Nlog(1/ε)), where ε\varepsilonε is the ℓ1\ell_1ℓ1​-norm approximation error of the reconstructed matrix, and demonstrate empirically that a largest‑weight greedy variant requires only ≈2N\approx 2N≈2N terms for dense matrices (the exact average observed is ≈2.4N\approx 2.4N≈2.4N). The quadratic reduction in term count directly shrinks the ancilla register from 2log⁡2N2\log_2 N2log2​N to log⁡2N\log_2 Nlog2​N qubits, shortens the SELECT circuit, and is especially valuable in fixed‑Hadamard LCU architectures whose success probability scales with 1/K1/K1/K. The approach enables compact quantum implementations of dense operators appearing in optimal transport, non‑Hermitian simulation, and other settings amenable to Sinkhorn preconditioning. Furthermore, because the decomposition is a convex combination, the LCU normalization constant is exactly α=1\alpha = 1α=1, and the uniform superposition is an eigenvector of the target matrix with eigenvalue~1. This structure can be exploited to achieve high success probability without amplitude amplification in many practical scenarios, including quantum walks and Markov chain simulations.