Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization
Abstract
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.
Related
- Transducer-based linear combination of unitaries: theory and applications
- Efficient learning of Clifford disentanglers and typical t-doped unitaries with exponentially more T gates
- 𝒪(n) alternative to Quantum Fourier Transform with efficient neural net classical post-processing
- Efficient Quantum Fourier Transforms For Semisimple Algebras
- Communication-Efficient Distributed Inverse Quantum Fourier Transform
BibTeX
@misc{vazquez2026efficient,
title = {{Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization}},
author = {Almudena Carrera Vazquez and Daniel J. Egger and Stefan Woerner},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.18985},
eprint = {2605.18985},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.18985},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization
AU - Almudena Carrera Vazquez
AU - Daniel J. Egger
AU - Stefan Woerner
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2605.18985
UR - https://arxiv.org/abs/2605.18985
AB - 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.
ER -