Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling

This paper proposes an extrapolation method to optimize the two parameters of linear-ramp QAOA, demonstrating that this approach achieves superior runtime scaling compared to classical algorithms for portfolio optimization problems up to 28 qubits.

The Gist

Imagine you are trying to solve a massive, incredibly complex puzzle. You have a new, high-tech tool (a quantum computer) that might be able to solve it faster than the best human brain or supercomputer we have today. But there's a catch: to make this tool work, you have to tune its knobs perfectly. If you get the knobs wrong, the tool is useless.

This paper is about a clever shortcut to tune those knobs without having to do the hard work of testing every single setting from scratch.

Here is the breakdown of their journey, explained simply:

1. The Problem: Tuning the "Quantum Radio"

The tool they are using is called QAOA (Quantum Approximate Optimization Algorithm). Think of QAOA as a radio trying to find a specific, clear signal (the best solution to a problem) amidst a lot of static.

• The Standard Way: Usually, to get the signal clear, you have to twist dozens of knobs (parameters) and test them over and over again. As the puzzle gets bigger, the number of knobs explodes, and the tuning process takes forever. It's like trying to tune a radio with 100 knobs by hand; you'd never finish.
• The New Idea (Linear-Ramp): The researchers found a way to simplify this. Instead of 100 knobs, they realized they only really need to adjust two main settings (let's call them "Speed" and "Direction") and one "Depth" setting (how long you listen). This is called the Linear-Ramp method. It's like having a radio with just a volume knob and a tuning dial, making it much easier to use.

2. The Solution: The "Small Puzzle" Trick (Extrapolation)

Even with just two knobs, finding the perfect setting for a huge puzzle (say, 28 pieces) is still hard. You can't just guess.

The authors came up with a clever trick: Extrapolation.

• The Analogy: Imagine you want to know how fast a race car will go on a 100-mile track. Instead of driving the full 100 miles (which takes a long time and uses a lot of fuel), you drive the car on a 4-mile, 6-mile, and 8-mile section of the track. You measure the speed there.
• The Prediction: You then draw a line connecting those speeds and extend it to predict how fast the car will go on the full 100-mile track.
• In the Paper: They took their big, hard problems (up to 28 "bits" or puzzle pieces) and broke them down into tiny, easy versions (4, 6, 8, or 10 pieces). They found the perfect knob settings for these tiny versions. Then, they used math to "stretch" those settings up to predict the perfect settings for the big, 28-piece problems.

3. The Test: Can the Quantum Computer Win?

They tested this method on four different types of real-world puzzles:

1. Portfolio Optimization: Picking the best mix of stocks to maximize profit and minimize risk.
2. Feature Selection: Picking the most important data points for a machine learning model.
3. Clustering: Grouping similar items together (like sorting red and blue marbles).
4. MaxCut: Dividing a network into two groups so that the connections between the groups are as strong as possible.

They ran these puzzles on a simulated quantum computer (a perfect, noise-free version running on a supercomputer) and compared the time it took to find the answer against the best classical (normal) computer methods.

4. The Results: A Win for Stocks, But Not Everything

Here is what they found:

• The Stock Market Puzzle (Portfolio Optimization): This is where the magic happened. The quantum method, using their "small puzzle" prediction trick, got faster as the problem got bigger compared to the classical method. It showed a potential advantage. It's like the quantum car started pulling ahead of the human driver as the track got longer.
• The Other Puzzles: For the other three types of problems (picking data, grouping items, and dividing networks), the quantum method was actually slower or just as slow as the classical methods. The "prediction trick" worked, but the quantum tool didn't beat the human tools in these specific cases.

5. The "Universal" Shortcut

The researchers noticed that the "perfect" knob settings for the stock market puzzle followed a simple pattern. They realized they didn't even need to calculate the settings for every single new puzzle. They could just use a universal formula (a single rule that works for everyone).

• When they applied this universal rule, the quantum performance for the other three puzzles improved significantly, getting as good as the classical methods, though not better.

The Bottom Line

The paper claims that:

1. You can skip the expensive, slow process of tuning a quantum computer for big problems by testing small ones first and mathematically guessing the rest.
2. This method works well enough to show that, for Portfolio Optimization, a quantum computer might eventually solve these problems faster than a classical computer as the problems get huge.
3. For the other problems tested, the quantum computer didn't win yet, but the method made it competitive.

Important Note: The authors are careful to say this is a simulation on a perfect computer. They haven't proven this works on real, noisy quantum hardware yet, and they haven't solved problems bigger than 28 pieces. But the "small-to-big" prediction trick looks like a promising way to make quantum computers useful for the future.

Technical Summary

Technical Summary: Extrapolation Method to Optimize Linear-Ramp QAOA Parameters

Problem Statement
The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for solving combinatorial optimization problems, yet its standard variational form faces significant scalability challenges. The standard approach requires optimizing a large number of circuit parameters ($2p$ parameters for depth $p$) via classical routines, which is computationally expensive and prone to getting stuck in local minima. This optimization bottleneck hinders the demonstration of potential quantum runtime advantages. While fixed schedules, such as the linear-ramp QAOA (LR-QAOA), reduce the parameter space to just two free parameters ($\Delta\gamma, \Delta\beta$) plus the depth $p$, finding optimal values for these parameters for large problem sizes ($N$) remains a non-trivial task.

Methodology
The authors propose a method to determine suitable LR-QAOA parameters for large problem sizes by extrapolating from optimizations performed on smaller sub-problems. The methodology consists of three main components:

1. Problem Formulation: Four combinatorial optimization problems are formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems: Portfolio Optimization, Feature Selection, Clustering (using Moons and Blobs datasets), and weighted MaxCut.
2. Classical Benchmarking: The runtime scaling of classical solvers (CPLEX, Gurobi, Goemans-Williamson, and MQLib/Burer2002) is evaluated. The MQLib/Burer2002 heuristic is selected as the primary classical benchmark due to its low absolute runtime and consistent scaling behavior, avoiding the overhead of optimality bounds found in commercial solvers.
3. LR-QAOA and Extrapolation Scheme:
   • Linear-Ramp Ansatz: Instead of variational optimization, parameters are sampled from a linear ansatz: $\gamma_j = \Delta\gamma x_j$ and $\beta_j = \Delta\beta(1-x_j)$, where $x_j$ is a linear ramp variable.
   • Sub-problem Optimization: For a target problem size $N$ (up to 28 qubits), random sub-instances of smaller sizes ($\tilde{N} \in \{4, 6, 8, 10\}$) are generated. A grid search is performed on these small instances to find optimal $\Delta\gamma$ and $\Delta\beta$.
   • Fitting and Extrapolation: The optimal parameters found for $\tilde{N}$ are fitted using a multivariate skew Gaussian function to locate the center of the high-probability region. These centers are then extrapolated to the target size $N$ assuming a linear relationship on a log-log scale ($\log(\text{parameter})$ vs. $\log(N)$).
   • Depth Optimization: The QAOA depth $p$ is optimized to minimize the total quantum runtime, defined as the product of the circuit depth and the median number of shots required to find the optimal solution ($D = d \cdot N_{shots}$).
   • Universal Scaling: To improve stability and reduce outliers, the authors derive "universal" parameter scaling laws ($f(N) = a \cdot N^b$) based on the extrapolated data, applying these fixed laws to all instances of a given problem class rather than optimizing per instance.

Key Results
The study evaluates the quantum runtime scaling (expressed as total depth $D$) against classical scaling on a noiseless quantum emulator for problem sizes up to $N=28$.

• Portfolio Optimization: The LR-QAOA with extrapolated parameters demonstrates a scaling exponent of $\alpha \approx 0.219$ (where $D \propto 2^{\alpha N}$), which is significantly lower than the classical benchmark (MQLib/Burer2002) of $\alpha_{cl} \approx 0.323$. This indicates a potential quantum scaling advantage.
• Feature Selection, Clustering, and MaxCut: Initially, these problems showed quantum scaling exponents higher than their classical counterparts. However, when applying the "universal" parameter scaling derived from the extrapolation data, the quantum scaling improved significantly.
  • For Feature Selection and MaxCut, the quantum scaling achieved equality with the classical benchmarks ($\alpha \approx 0.202$ vs $0.197$ and $\alpha \approx 0.163$ vs $0.156$, respectively).
  • For Clustering (Moons), the classical benchmark ($\alpha_{cl} \approx 0.051$) remained superior to the quantum approach ($\alpha \approx 0.163$).
• Stability: The use of universal parameters significantly reduced the occurrence of extreme outliers (instances with very large depths) observed when parameters were determined individually for each instance.
• Probability Behavior: For Portfolio Optimization and MaxCut, the probability of measuring the optimal solution ($P_{opt}$) remained constant or slightly increased with $N$, while the circuit depth scaled algebraically. This suggests a potential for polynomial scaling of the median runtime for these specific problem classes.

Significance and Claims
The paper claims to present a scalable method for determining LR-QAOA parameters without the need for expensive variational optimization on large circuits. By leveraging extrapolation from small sub-problems, the authors demonstrate that:

1. Runtime Advantage: A quantum scaling advantage is observed for Portfolio Optimization compared to classical heuristics.
2. Scalability: The extrapolation method allows for the efficient estimation of parameters for larger systems ($N=28$) based on simulations of very small systems ($N \le 10$).
3. Universal Laws: The identification of algebraic scaling laws for parameters ($\Delta\gamma, \Delta\beta, p$) suggests that these parameters can be determined independently of specific problem instances, improving the robustness of the algorithm.

The authors modestly conclude that while their results suggest a potential for polynomial-time solutions for specific instances (indicated by constant $P_{opt}$ and algebraic depth scaling), further work is required to verify these findings on larger problem sizes ($N > 28$) and on fault-tolerant quantum hardware. They emphasize that their work addresses the general potential of LR-QAOA assuming parameters can be efficiently found, rather than solving the parameter optimization cost itself as a runtime component.