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

Any square matrix can be transformed into a doubly stochastic matrix via Sinkhorn scaling with diagonal matrices or completing to a larger dimensional matrix. Standard Birkhoff-von Neumann and Pauli decompositions represent such matrices as linear combinations of O\(N²\) 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/varepsilon\)), where varepsilon is the ell₁-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 2log₂ N to log₂ 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 α= 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.