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.
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-vonNeumann 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(1/ε)), 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 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 α=1, and the uniform superposition is an eigenvector of the target matrix with eigenvalue1. This structure can be exploited to achieve high success probability without amplitude amplification in many practical scenarios, including quantum walks and Markov chain simulations.
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.
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.
Estimating the expectation value of an observable O for a quantum state evolved under a general, possibly non-unitary, operator A is a fundamental task in quantum simulation, chemistry, and variational algorithms. Existing linear-combination-of-unitaries (LCU) approaches implement A on hardware, requiring ancilla qubits, controlled unitaries and, in randomized variants, fresh circuit executions for every Monte Carlo sample. These costs are prohibitive on NISQ and early fault-tolerant devices. We propose HERMES (Hardware-Efficient Reusable Measurements for Estimating LCU-based expectation valueS), which moves the processing of A entirely to the classical domain. Expanding A and O in the Pauli basis and sampling pairs of Pauli terms classically, HERMES rewrites μ=Tr(OAρA†)/Tr(AρA†) as a ratio of weighted sums of Pauli expectation values on the unmodified state ρ, with no ancillas, controlled unitaries, or quantum implementation of A. A two-level measurement reduction scheme (Pauli deduplication and commuting-group partitioning) bounds the number of distinct measurement settings independently of the sample count, unlike randomized LCU methods whose circuit executions grow linearly with it. On ground-state energy estimation of H2 and LiH via imaginary-time evolution, HERMES matches or beats Pauli single-ancilla LCU baseline using shallow circuits with no two-qubit gates beyond state preparation under qubit-wise commuting grouping. It is also more robust to noise and completes a noisy LiH simulation infeasible for the baseline, at the cost of classical overhead growing with the number of Pauli terms in A.
We investigate ancilla-free linear combination of unitaries (LCU) as a framework for approximating complex quantum circuits. This is particularly effective for quantum optimization algorithms, where candidate solutions can be evaluated classically and the task is to sample high-quality bitstrings rather than reproduce the full output distribution. We show that Fourier-based LCU constructions efficiently decompose broad classes of diagonal and non-diagonal unitaries, replacing highly connected qubit interactions with single-qubit gate layers or significantly simpler structures at the cost of a polynomial sampling overhead. Applied to algorithms such as QAOA, this yields efficient, hardware-friendly decompositions of, for instance, cardinality-constraint penalties and the fully connected XY-mixer, while maintaining rigorous performance guarantees compared to fully coherent implementations. Furthermore, we establish a formal connection between Fourier-based quantum penalties and Lagrangian relaxation, offering a unified perspective on constraint handling. We validate our approach using exact statevector simulations of 12-qubit circuits and large-scale experiments on 106 superconducting qubits. Our results illustrate how approximate sampling via an LCU systematically trades circuit complexity for sampling overhead, extending the practical reach of near-term quantum optimization.
Block encodings are a basic interface between quantum algorithms and linear algebra. Standard LCU constructions achieve optimal circuit depth but typically require logarithmically many ancilla qubits. We ask how much quantum workspace can be reduced without sacrificing circuit depth, and study this tradeoff from both algorithmic and lower-bound perspectives.
For a Hermitian decomposition A=∑j=1LαjHj, with ∥Hj∥=1 and α=∑j∣αj∣, we give two coherent ε-approximate block-encoding constructions. The first uses one ancilla qubit and has depth O(L(α/ε)o(1)), while the second uses O(loglog(α/ε)) ancillas and achieves depth O(L).
For a broad Suzuki-based coherent simulation architecture, we prove an ancilla-depth tradeoff. In the polynomial-resource regime and for a constant number of coherent rounds, log(1/ε)≤O((logQ)2+2alogQ), where Q is depth normalized by the number of Hamiltonian terms and a is the ancilla count. Thus polylogarithmic dependence on 1/ε requires more than constantly many ancillas within this architecture. In a separate repeated-query LCU model, for balanced coefficients 1/L and error ε=η/L with fixed 0<η<1, we prove 2a=Ωη(L2/(T+L)), where T is the number of oracle queries. Hence a=Ω(logL) when T=O(Lα) for some α<2. Moreover, in the exact case, a≥logL regardless of T. We also extend this tradeoff to arbitrary nonnegative coefficients.
Finally, we apply our low-ancilla constructions to normalized trace estimation in DQC1, obtaining an optimal algorithm linear in the approximate degree together with a matching query lower bound. Together, these results establish quantitative space-depth and space-query tradeoffs in two natural circuit models.
The Variational Quantum Linear Solver (VQLS), a hybrid quantum-classical algorithm for solving linear systems, faces a practical scalability bottleneck: the Linear Combination of Unitaries (LCU) decomposition requires O(L2) circuit evaluations per optimizer iteration, where L can grow to 4n in the worst case for an n-qubit system. We address this computational bottleneck through two complementary strategies. First, we present a distributed VQLS (D-VQLS) framework (https://code.ornl.gov/olcf-qcfd/DVQLS.git), built on NVIDIA CUDA-Q, that enables asynchronous, scalable distribution of the O(L2) cost evaluations. Second, a fast Walsh--Hadamard transform (FWHT)-based Pauli decomposition with coefficient-amplitude pruning threshold τ=0.01 curbs LCU growth for the structured Toeplitz family, reducing L from O(2n) to 64 for n>6 and compressing the circuit complexity per optimizer iteration from O(n4n) to O(n). We derive the exact top-L Frobenius error and connect it to worst-case solution error. For a 10-qubit tridiagonal Toeplitz system, the L=64 pruning yields a 256× reduction---from 23 million to 90k circuits per optimizer iteration.
The D-VQLS framework is validated on the NERSC Perlmutter supercomputer using multi-node, multi-GPU ideal state-vector simulations, achieving over 99.99% fidelity against classical solutions on tridiagonal Toeplitz and Hele--Shaw flow benchmarks, with near-ideal strong scaling up to 24 GPUs and 95.3% weak scaling efficiency at 96 GPUs processing more than 360k circuits per optimizer iteration (from larger-L pruning) for the 10-qubit system. Systematic profiling identifies the optimal resource allocation for distributed quantum circuit workloads, yielding a 2.52× speedup for the configurations studied.