VeloxQ: A Fast and Efficient QUBO Solver

The paper introduces VeloxQ, a fast and scalable classical solver for QUBO and HUBO problems that demonstrates competitive performance and superior scalability on large sparse instances compared to state-of-the-art quantum annealers, physics-inspired algorithms, and conventional optimization methods.

The Gist

The Big Picture: The "VeloxQ" Race Car

Imagine you have a massive, incredibly complex maze. Your goal is to find the single shortest path from the start to the finish. In the world of computer science, this is called a QUBO problem (Quadratic Unconstrained Binary Optimization). It's the mathematical engine behind everything from scheduling airline flights to managing stock portfolios.

The paper introduces VeloxQ, a new "race car" designed specifically to solve these mazes. Unlike other racers that need special, futuristic tracks (quantum computers) to run, VeloxQ is built to run on standard, off-the-shelf computer hardware that exists right now.

The authors tested VeloxQ against the best racers in the world, including:

• Quantum Annealers: Like D-Wave's super-cooled quantum computers (the "Ferraris" of the future).
• Digital Quantum Algorithms: New software running on current quantum chips.
• Classical Giants: Old-school, powerful math solvers like CPLEX.
• Physics-Inspired Algorithms: Methods that mimic how heat or light behaves to find solutions.

The Three Main Tests

The paper didn't just say "VeloxQ is fast." They put it through three specific challenges to see how it stacks up.

1. The "Native Track" Test (D-Wave Comparison)

The Analogy: Imagine a race where the track is built specifically for a certain type of car. D-Wave quantum computers have a very specific track layout (called Pegasus and Zephyr topologies). If your problem fits that layout perfectly, the quantum car zooms. If it doesn't, you have to build a detour (called "embedding"), which slows you down.

The Result:

• On the native track: VeloxQ was almost as fast as the quantum car and found just as good a solution.
• On the detour: When the problem didn't fit the quantum track and required a detour, the quantum car got bogged down. VeloxQ, however, didn't care about the track layout. It drove straight through, solving problems 100 to 1,000 times faster than the quantum hybrid systems could.
• The Scale: VeloxQ solved a maze with nearly 100 million variables. The authors estimate that a quantum computer capable of handling that size natively wouldn't exist for another 30 years.

2. The "Complex Puzzle" Test (HUBO & Kipu Quantum)

The Analogy: Some puzzles are so complex they have 3D pieces (Higher-Order problems). Most solvers have to smash these 3D pieces into flat 2D pieces to solve them, which creates a lot of extra "trash" (extra variables) to manage. A new company, Kipu Quantum, built a solver that handles the 3D pieces natively.

The Result:

• VeloxQ had to smash the 3D pieces into 2D first (adding extra variables).
• Despite this extra work, VeloxQ was still able to solve puzzles with 100 million variables.
• It beat the Kipu Quantum solver in both speed and the size of the puzzle it could handle, proving that even with the "smashing" overhead, VeloxQ's raw speed is unbeatable for now.

3. The "Perfect vs. Good Enough" Test (Certified Solvers)

The Analogy: Imagine you are looking for the absolute lowest point in a foggy valley.

• Certified Solvers (like Brute Force or BEIT): These are like hikers who check every single inch of the ground. They guarantee they found the absolute lowest point, but they take days or weeks to do it.
• VeloxQ: This is like a hiker with a high-tech drone. It doesn't check every inch, but it scans the whole valley in seconds and finds a spot that is so close to the bottom that it's practically the same.

The Result:

• On small puzzles, VeloxQ found the "perfect" answer just as fast as the hikers who checked every inch.
• On larger puzzles, the "perfect" hikers gave up because it took too long. VeloxQ kept going, finding excellent solutions in seconds where the others were still stuck in the fog.

The "Physics" Race (Parallel Annealing & Simulated Bifurcation)

The authors also raced VeloxQ against other methods that mimic physics, like "Parallel Annealing" (cooling metal to find strength) and "Simulated Bifurcation" (using chaotic waves to find paths).

• The Result: VeloxQ was competitive across the board. In some "easy" mazes, the physics methods were slightly faster. But in "hard" mazes (where the path is tricky and full of traps), VeloxQ consistently found better solutions and did it faster.

The Bottom Line

The paper concludes that VeloxQ is the most scalable tool available today.

• It doesn't need a quantum computer: It runs on standard servers with graphics cards (GPUs).
• It handles massive sizes: It solved problems with up to 100 million variables, a scale that current quantum computers cannot touch.
• It's a trade-off: VeloxQ is a "heuristic," meaning it doesn't guarantee the mathematically perfect answer every time (unlike the slow "hikers"). However, it finds answers that are so close to perfect, and so fast, that for most real-world problems, it is the superior choice.

In short: If you need to solve a massive optimization problem today and you don't want to wait 30 years for a quantum computer to catch up, VeloxQ is the tool that gets the job done.

Technical Summary

Technical Summary: VeloxQ: A Fast and Efficient QUBO Solver

Problem Statement

The paper addresses the challenge of solving Quadratic Unconstrained Binary Optimization (QUBO) problems, which are central to numerous real-world optimization tasks ranging from operations research to portfolio optimization. While QUBO problems are NP-hard, their increasing size and complexity in industrial applications are beginning to exceed the capabilities of established exact and heuristic approaches. Although emerging paradigms like quantum computing and physics-inspired algorithms offer new opportunities, many rely on hardware that is either not yet commercially viable at scale or requires specific topologies that necessitate costly embedding. The authors aim to introduce a solver that leverages conventional computing infrastructure to handle large-scale QUBO and Higher-Order Unconstrained Binary Optimization (HUBO) problems without the constraints of current quantum hardware limitations.

Methodology

The authors present VeloxQ, a QUBO solver based on a novel physics-inspired methodology designed to run on conventional hardware, specifically utilizing GPU acceleration. Unlike approaches dependent on future quantum hardware advances, VeloxQ is intended for immediate deployment on existing infrastructure.

The benchmarking methodology compares VeloxQ against a diverse spectrum of state-of-the-art solvers across six distinct regimes:

1. Quantum Annealers: D-Wave Advantage (Pegasus topology) and Advantage2 (Zephyr topology), including hybrid decomposition for large instances.
2. Digital-Quantum Algorithms: The BF-DCQO algorithm by Kipu Quantum, which solves HUBO problems natively.
3. Certified Solvers: Brute-force (BF), the BEIT solver (Chimera topology specific), and Tropical Tensor Networks (TTN).
4. Physics-Inspired Heuristics: Parallel Annealing (PA) and Simulated Bifurcation (SBM).
5. Modern Branch-and-Bound (B&B): Variants including standard Bbase and the PSD-based BPSD method.
6. Classical Solvers: CPLEX and Simulated Annealing (SA).

The benchmark suite includes native quantum-annealer topologies, embedded all-to-all instances, HUBO-derived instances (reduced to QUBO), planted-solution families (3-regular 3-XORSAT, Tile Planting, Wishart Planting), and dense pseudo-random instances. Performance is measured via solution quality (optimality or reference gap) and runtime, with careful accounting for cloud overheads and embedding costs where applicable.

Key Contributions

• Scalability: The primary distinction of VeloxQ is its ability to scale to problem sizes far beyond current quantum and classical capabilities. The authors report successfully running VeloxQ on sparse instances with up to $10^8$ variables (specifically a Z1750 instance with $\sim 9.8 \times 10^7$ variables), a scale that would require quantum hardware decades away from realization under current extrapolation trends.
• Native Topology Handling: VeloxQ handles arbitrary problem topologies natively, avoiding the "minor embedding" overhead required by quantum annealers for non-native graphs (e.g., all-to-all connectivity).
• HUBO Reduction: The paper demonstrates that despite the auxiliary variable overhead required to reduce HUBO problems to QUBO, VeloxQ remains effective and competitive, solving instances with up to $\sim 10^8$ QUBO variables derived from HUBO formulations.
• Performance Trade-offs: The solver offers configurable settings ("AutoTune" for quality vs. "Custom" for runtime), allowing users to adjust the trade-off between solution quality and execution time.

Results

Across the benchmark suite, VeloxQ demonstrates competitive solution quality and runtime compared to the diverse set of solvers:

• Against Quantum Annealers (D-Wave): On native Pegasus and Zephyr topologies, VeloxQ achieves solution quality comparable to the QPU. While D-Wave may be faster for small, native instances, VeloxQ matches or exceeds D-Wave performance when tuning parameters for runtime. Crucially, for large sparse instances (beyond P16/Z12) and all-to-all instances requiring embedding, VeloxQ significantly outperforms D-Wave and its hybrid Kerberos solver in both solution quality (lower reference gaps) and runtime, avoiding the embedding overhead entirely.
• Against Digital-Quantum (Kipu Quantum): On HUBO-derived instances (3-body Ising and MAX-3-SAT), VeloxQ remains competitive after reduction, solving instances substantially larger than those demonstrated on current gate-based quantum hardware.
• Against Certified Solvers: On modest-size instances where exact ground states are known (via brute force, BEIT, or TTN), VeloxQ often reaches the same energy levels faster than these exact solvers, though it does not provide an optimality certificate.
• Against Physics-Inspired Algorithms: On planted-solution families (3R3X, Tile Planting, Wishart), VeloxQ is competitive with Parallel Annealing and Simulated Bifurcation. It consistently finds ground states for smaller instances and maintains low optimality gaps (<5%) for larger, harder instances where other methods degrade.
• Against Branch-and-Bound: On dense pseudo-random instances, VeloxQ achieves comparable or better reference gaps than modern B&B variants (Bbase, BPSD) while being at least two orders of magnitude faster.

Significance and Claims

The paper positions VeloxQ as a practical and competitive tool for tackling large-scale QUBO and HUBO problems. The authors claim that VeloxQ bridges the gap between established classical methods and emerging quantum approaches by offering a solution that can be deployed on conventional hardware today.

Key claims regarding significance include:

1. Practical Alternative: VeloxQ offers a viable alternative to existing quantum and classical optimization methods, particularly for problems where topology flexibility and scalability are paramount.
2. Scalability Leader: It is the only method in the study capable of successfully running on the largest sparse instances considered (up to $10^8$ variables) within the computational budget.
3. Heuristic Nature: The authors are explicit that VeloxQ is a heuristic solver; it does not provide certificates of optimality. Its value lies in delivering high-quality solutions rapidly for problems where exact methods are intractable.
4. Hybrid Potential: While not the focus of this paper, the authors suggest VeloxQ could serve as a practical component in hybrid quantum-classical workflows.

The paper concludes that while VeloxQ does not guarantee optimality, its ability to handle ultra-large sparse regimes and its competitive performance on structured benchmarks make it a significant advancement in the landscape of QUBO solvers.