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

• URL: http://arxiv.org/abs/2605.27430v1
• Date: Fri, 22 May 2026 04:29:13 GMT
• Title: Lowering LCU Circuit Width through Maximum-Weight Birkhoff-von Neumann Decomposition
• Abstract summary: We show that a bottleneck variant of Birkhoff's algorithm reduces the number of permutations to $O(Nlog(varepsilon))$.<n>The quadratic reduction in term count directly shrinks the ancilla register from $2log N$ to $log N$ qubits.<n>This structure can be exploited to achieve high success probability without amplitude amplification.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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^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 $α= 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.

Related papers

• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  Matrix chain multiplication is a problem in scientific computing, machine learning, and graph analysis.<n>We present emphTwo-Tower Matrix, a quantum subroutine that encodes the product $mathcalW$ of the $K$ matrices into a quantum state in circuit depth.
  arXiv  Detail & Related papers  (2026-07-14T18:42:40Z)
• Efficient Complex-Valued State Preparation on Bucket Brigade QRAM [47.72095699729477]
  Efficient quantum state preparation is a critical component in quantum algorithms that process large classical data.<n>We present two improvements within the same architecture-aware framework.
  arXiv  Detail & Related papers  (2026-04-28T13:43:29Z)
• Reducing C-NOT Counts for State Preparation and Block Encoding via Diagonal Matrix Migration [10.184239233596562]
  We give algorithms with lower C-NOT counts for both the state preparation and block encoding.<n>For a general $n$-qubit state, we improve the C-NOT count from Plesch-Brukner algorithm.<n>For block encoding, our single-ancilla protocol for $2n-1times 2n-1$ matrices uses the spectral norm as subnormalization.
  arXiv  Detail & Related papers  (2026-03-17T13:20:46Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Matrix encoding method in variational quantum singular value decomposition [49.494595696663524]
  We propose the variational quantum singular value decomposition based on encoding the elements of the considered $Ntimes N$ matrix into the state of a quantum system of appropriate dimension.<n> Controlled measurement is involved to avoid small success in ancilla measurement.
  arXiv  Detail & Related papers  (2025-03-19T07:01:38Z)
• Optimal Quantization for Matrix Multiplication [29.75700570685703]
  Algorithmically, we construct a universal quantizer based on nested lattices with an explicit guarantee of approximation error.<n>A practical low-complexity version of our quantizer achieves performance quite close to optimal.
  arXiv  Detail & Related papers  (2024-10-17T17:19:48Z)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an $(N-1)times (N-1)$ matrix.<n>The basic idea is to encode each row of the matrix into a pure state of some quantum system.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• Improved quantum lower and upper bounds for matrix scaling [0.0]
  We investigate the possibilities for quantum speedups for classical second-order algorithms. We show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime. We give improved quantum algorithms in the low-precision regime.
  arXiv  Detail & Related papers  (2021-09-30T17:29:23Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.