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.
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⟩ 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×N matrix reveals a factorization Φ=CX, where C encodes the coefficients and X contains the action of each unitary on the input; this immediately shows rank(Φ)≤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.
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.
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.
Discrete circular convolution over 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⟩ while supplying the kernel state ∣b⟩ as the input ancilla naturally preserves the complex coefficients bi within the block, whereas a symmetric overlap would yield ∣bi∣2 weights and erase their phases. Accordingly, when ∣a⟩ and ∣b⟩ are supplied by upstream quantum routines, the convolution subroutine requires only the fixed uncompute PREPu†, completely avoiding the need for a kernel-dependent inverse preparation PREPb†. We then introduce a reversal matrix Jn=X⊗n and define reflected shifts Li,n=Li,nJn. 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 Jn layer. Crucially, for real-valued kernels, the resulting operator Hn(b)=∑ibiLi,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 block. Finally, we evaluate implementation trade-offs and resource scaling under explicit cost-model conventions.
Linear combination of unitaries (LCU) is a fundamental primitive in quantum algorithms, whose cost is typically governed by the most expensive unitary appearing in the combination. We develop a transducer-based LCU framework that reduces this worst-case dependence to a weighted average query complexity, when the constituent unitaries share access to a common set of primitive oracles.
Consider A=∑jcjUj, where cj>0 and each unitary Uj can be implemented using Cj primitive queries. Given an upper bound a≥∥A∥, our algorithm implements a block-encoding of A/α with rescaling factor α=O(a), using O(Cmax+Cλ/a) primitive queries, where λ=∑jcj, Cmax=maxjCj, and C=∑jcjCj/λ. By comparison, the standard LCU construction requires O(Cmaxλ/a) primitive queries. The improvement can therefore be substantial when costly unitaries have small weights and λ/a is large. As applications, we obtain improved block-encodings of sparse matrices, leading to quantum algorithms for sparse Hamiltonian simulation and quantum linear systems with near-optimal query complexity up to polylogarithmic factors in all relevant parameters.
Our main technique is the transducer framework developed by Belovs, Jeffery, and Yolcu [Quantum, 8:1444 (2024)]. Here we develop a complementary operator-level theory tailored to block-encodings. We identify the resolvent norm K as a key complexity measure for transducer implementation besides the existing catalyst complexity. We show that the transducer action can be converted into an ε-approximate block-encoding using only O(Klog(1/ε)) queries to the transducer, improving the precision dependence from polynomial to logarithmic.
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.
While classical Sinkhorn scaling applies to nonnegative matrices, we show that any complex square matrix whose element-wise absolute value has total support can be mapped to a phased doubly stochastic matrix, or alternatively embedded into a larger doubly stochastic matrix via matrix completion.
Standard Birkhoff-von~Neumann and Pauli decompositions represent such matrices as linear combinations of 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(N/ε)), where ε is the ℓ1-norm approximation error of the reconstructed matrix, and demonstrate empirically that a largest-weight greedy variant requires only ≈2N terms for dense matrices (the exact average observed is ≈2.4N). The quadratic reduction in term count directly shrinks the ancilla register from 2log2N to log2N qubits, shortens the SELECT circuit, and is especially valuable in fixed-Hadamard LCU architectures, where---under the standard uniform-coefficient assumption---the success probability scales as 1/K; our convex decomposition achieves α=1 exactly and therefore avoids this penalty. 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 for the scaled matrix S is exactly αS=1, and the uniform superposition is an eigenvector of S 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.