Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization

This paper proposes an ancilla-free, Fourier-based Linear Combination of Unitaries (LCU) framework that efficiently decomposes complex quantum circuits for optimization tasks by trading circuit complexity for polynomial sampling overhead, thereby enabling hardware-friendly implementations of algorithms like QAOA on near-term quantum devices while maintaining rigorous performance guarantees.

The Gist

Imagine you are trying to solve a massive, incredibly complex puzzle. In the world of quantum computing, this puzzle is often an optimization problem: finding the best possible arrangement of things (like the most efficient delivery route or the best investment portfolio).

The paper by Carrera Vazquez, Egger, and Woerner introduces a clever new way to tackle these puzzles using a quantum computer, specifically one that is still in its early, "noisy" stages of development.

Here is the breakdown of their idea using simple analogies:

The Problem: The "All-Hands-on-Deck" Circuit

Traditionally, to solve these puzzles on a quantum computer, you need to build a specific machine (a quantum circuit) where every single piece of the puzzle talks to every other piece simultaneously.

• The Analogy: Imagine trying to organize a party where 100 guests all need to shake hands with every other guest at the exact same time. In a real room, this is impossible; people would bump into each other, the room would be too crowded, and the event would fail.
• The Quantum Reality: In quantum terms, this requires "all-to-all connectivity" and very deep, complex circuits. Current quantum computers are like small rooms; they can't handle that many simultaneous handshakes without making mistakes (noise).

The Solution: The "Recipe Book" Approach (LCU)

The authors propose a new strategy called Linear Combination of Unitaries (LCU). Instead of trying to build the impossible "all-hands" machine, they break the complex task down into a list of much simpler, smaller tasks.

• The Analogy: Instead of trying to bake a giant, intricate wedding cake in one go (which might collapse), you bake 100 simple, small cupcakes.
  • Some cupcakes are vanilla, some are chocolate, some have sprinkles.
  • You don't need a giant oven; you can bake them one by one or in small batches.
  • Afterward, you mix the results together on a plate. If you mix them in the right proportions, the "flavor" of the plate tastes exactly like the giant wedding cake you wanted.

In the paper, these "cupcakes" are simple quantum circuits that only require single-qubit gates (one person shaking hands with one other person). The "mixing" happens classically (on a regular computer) after the quantum part is done.

The Secret Sauce: The Fourier Transform

How do they know which cupcakes to bake and how much of each to mix? They use a mathematical tool called the Fourier Transform.

• The Analogy: Think of a complex song. A Fourier transform breaks that song down into individual notes (frequencies). The authors use this to break down a complex quantum "song" (the circuit) into a series of simple, repetitive notes (single-qubit rotations).
• The Result: They can express a very difficult, complex quantum operation as a weighted sum of very easy operations.

The Trade-off: Quality vs. Quantity

There is a catch. Because you aren't building the giant machine directly, you have to do the "cupcake" experiment many more times to get a reliable answer.

• The Analogy: If you want to know the average height of a crowd, you could measure everyone once (hard to do if they are all moving). Or, you could measure 10 random people, then 10 more, then 10 more, and take the average. You get the same result, but you have to do more measurements.
• The Paper's Claim: The authors show that while you need to run the simple circuits more times (a "sampling overhead"), the number of extra runs is manageable (polynomial), not impossible. This trade-off allows them to run problems on current hardware that would otherwise be impossible.

Real-World Application: The "Densest Subgraph"

To prove this works, they tested it on a specific problem called the "Densest k-Subgraph" (finding the tightest-knit group of friends in a massive social network).

1. Small Scale: They simulated it on a 12-node graph (like a small neighborhood) to show the math works perfectly.
2. Large Scale: They ran it on a real IBM quantum computer with 106 qubits (a large neighborhood).
   • They successfully found high-quality solutions.
   • They compared two methods: one that used a "penalty" (like a fine for breaking rules) and one that used a special "mixer" (a rule-following dance).
   • The Finding: The "mixer" approach, combined with their new Fourier method, worked exceptionally well, finding solutions that were nearly as good as the theoretical best, even on real, noisy hardware.

The "No-Helper" Trick

Usually, to mix these "cupcakes" together, you need an extra helper qubit (an "ancilla") to keep track of the math.

• The Innovation: The authors developed a way to do this without the helper.
• The Analogy: Instead of needing a referee to tell you which team scored, you just let the players play randomly and then look at the scoreboard afterward to figure out the winner. This removes a huge amount of complexity from the quantum circuit, making it much friendlier for today's machines.

Summary

This paper presents a new way to run complex quantum optimization algorithms on today's imperfect hardware. Instead of trying to build a massive, fragile machine that connects everything to everything, they break the problem into many small, simple pieces, run those pieces, and combine the results classically.

They proved this works by solving a difficult graph problem on a 106-qubit quantum computer, showing that we can solve bigger, more complex problems today by trading "circuit complexity" (how hard the machine is to build) for "sampling overhead" (how many times we have to run the test).

Technical Summary

Technical Summary: Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization

Problem Statement
Quantum optimization algorithms, particularly the Quantum Approximate Optimization Algorithm (QAOA), face significant implementation barriers on near-term hardware. The mathematical structure of optimization problems, especially those involving constraints (e.g., cardinality constraints), often necessitates quantum circuits with high connectivity (all-to-all interactions), deep circuit depths, and numerous two-qubit gates. These requirements frequently exceed the capabilities of current superconducting quantum processors. While strategies like circuit cutting or approximating circuits exist, they often trade solution quality for complexity or require substantial sampling overhead without rigorous performance guarantees.

Methodology
The authors propose a Fourier-based Linear Combination of Unitaries (LCU) framework designed to approximate complex quantum circuits using ensembles of simpler, hardware-friendly circuits. The core methodology involves:

1. Ancilla-Free LCU for Sampling: Unlike standard LCU implementations that use an ancilla qubit to coherently implement a linear combination of unitaries (requiring controlled operations), this work focuses on sampling-based applications. By dropping the sign factors associated with the quasi-probability decomposition (QPD) and replacing the ancilla with classical randomness, the method eliminates the need for ancilla qubits and controlled gates. This transforms the implementation into a probabilistic mixture of simpler circuits, where the sampling overhead is quantified by a factor $\Gamma$.
2. Fourier Decomposition for Diagonal Unitaries: For diagonal unitaries (common in cost functions and penalty terms), the authors utilize the discrete Fourier transform. A target unitary $U_f(\gamma) = \sum_x e^{-i\gamma f(g(x))} |x\rangle\langle x|$ is decomposed into a linear combination of simpler unitaries $V(\theta_j)$, which are often just layers of single-qubit $R_Z$ gates. The coefficients are derived from the Fourier transform of the function defining the unitary. This approach replaces complex multi-qubit interactions (e.g., quadratic penalties requiring $O(n^2)$ gates) with single-qubit layers at the cost of a sampling overhead $\Gamma \le m+1$.
3. Extension to Non-Diagonal Permutation-Invariant Unitaries: The framework is generalized to non-diagonal unitaries, such as the fully connected XY-mixer used to preserve Hamming weight constraints. Leveraging Schur-Weyl duality and the representation theory of $SU(2)$, the authors express permutation-invariant unitaries as continuous linear combinations of collective single-qubit rotations $R(g)^{\otimes n}$. This allows the implementation of highly non-local mixers using only single-qubit gates, with a theoretical sampling overhead bounded by $O(n^3)$.
4. Connection to Lagrangian Relaxation: The paper establishes a formal link between Fourier-based quantum penalties and classical Lagrangian relaxation. Optimizing a single branch of the LCU decomposition is shown to be equivalent to optimizing a Lagrangian parameter, providing a unified perspective on constraint handling.

Key Contributions

• Framework Development: Introduction of an ancilla-free, Fourier-based LCU framework that decomposes broad classes of diagonal and non-diagonal unitaries into ensembles of single-qubit gate layers.
• Hardware Efficiency: Demonstration that complex, all-to-all connected operators (like cardinality penalties and XY-mixers) can be replaced by significantly simpler circuits, trading circuit depth and connectivity for a polynomial sampling overhead.
• Theoretical Guarantees: Provision of rigorous performance bounds, showing that the probability of sampling high-quality bitstrings in the LCU approach is lower-bounded by the coherent probability scaled by $1/\Gamma$. The paper also connects Conditional Value at Risk (CVaR) optimization to these bounds.
• Scalability Validation: Successful application of the framework to the densest $k$-subgraph problem on instances up to 106 qubits on real IBM Quantum hardware, a scale previously intractable for fully coherent implementations of such constraints.

Experimental Results
The authors validated their approach through exact statevector simulations on a 12-node instance and large-scale experiments on a 106-qubit device:

• 12-Node Simulation: Comparisons between fully coherent QAOA and the Fourier-based LCU approach showed that while the raw expectation values of the LCU circuits were lower (due to the sampling overhead), optimizing a single LCU basis circuit (a variational ansatz derived from the LCU) yielded the highest probability of sampling optimal solutions, outperforming the coherent baseline in specific metrics.
• 106-Node Hardware Experiment: On a 106-qubit heavy-hex graph (extended via SWAP layers), the penalty-based and XY-mixer-based LCU approaches were executed. The results demonstrated that the practical sampling overhead was significantly lower than the worst-case theoretical bounds ($\Gamma \approx 10^4$). The single-branch LCU ansatz successfully found high-quality solutions (up to 81 edges in the densest subgraph) with feasible probabilities ranging from 2.7% to 4.8%, indicating the method's viability for large-scale problems.
• XY-Mixer vs. Penalty: The XY-mixer-based LCU approach generally outperformed the penalty-based approach, particularly when using a single optimized basis circuit, suggesting that constraint-preserving mixers are more effective when combined with this decomposition.

Significance and Claims
The paper claims that the Fourier-based LCU framework offers a systematic route to extending the practical reach of near-term quantum optimization. By replacing complex coherent operations with weighted combinations of simpler circuits, the method broadens the range of problem instances (specifically those with global constraints) that can be executed on current hardware. The authors emphasize that this approach does not require exact reproduction of the target distribution but rather focuses on sampling high-quality solutions, a goal well-suited for optimization tasks. The work suggests that the trade-off between circuit complexity and sampling overhead is favorable, as theoretical bounds are often loose in practice, and the method enables the study of algorithms and problem instances that would otherwise be beyond hardware capabilities. The paper concludes that this provides a flexible design principle for more hardware-compatible quantum algorithms, particularly for constraint handling in QAOA.