Quantinuum Researchers Demonstrate a new Optimization Algorithm that delivers solutions on H2 Quantum Computer
In a meaningful advance in an important area of industrial and real-world relevance, Quantinuum researchers have demonstrated a quantum algorithm capable of solving complex combinatorial optimization problems while making the most of available quantum resources.
Results on the new H2 quantum computer evidenced a remarkable ability to solve combinatorial optimization problems with as few quantum resources as those employed by just one layer of the quantum approximate optimization algorithm (QAOA), the current and traditional workhorse of quantum heuristic algorithms.
Optimization problems are common in industry in contexts such as route planning, scheduling, cost optimization and logistics. However, as the number of variables increases and optimization problems grow larger and more complex, finding satisfactory solutions using classical algorithms becomes increasingly difficult.
Recent research suggests that certain quantum algorithms might be capable of solving combinatorial optimization problems better than classical algorithms. The realization of such quantum algorithms can therefore potentially increase the efficiency of industrial processes.
However, the effectiveness of these algorithms on near-term quantum devices and even on future generations of more capable quantum computers presents a technical challenge: quantum resources will need to be reduced as much as possible in order to protect the quantum algorithm from the unavoidable effects of quantum noise.
Sebastian Leontica and Dr. David Amaro, a senior research scientist at Quantinuum, explain their advances in a new paper, “Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits” published on arXiv. This is one of several papers published at the launch of Quantinuum’s H2, that highlight the unparalleled power of the newest generation of the H-Series, Powered by Honeywell.
“We should strive to use as few quantum resources as possible no matter how good a quantum computer we are operating on, which means using the smallest possible number of qubits that fit within the problem size and a circuit that is as shallow as possible,” Dr. Amaro said. “Our algorithm uses the fewest possible resources and still achieves good performance.”
The researchers use a parameterized instantaneous quantum polynomial (IQP) circuit of the same depth as the 1-layer QAOA to incorporate corrections that would otherwise require multiple layers. Another differentiating feature of the algorithm is that the parameters in the IQP circuit can be efficiently trained on a classical computer, avoiding some training issues of other algorithms like QAOA. Critically, the circuit takes full advantage of, and benefits from features available on Quantinuum’s devices, including parameterized two-qubit gates, all-to-all connectivity, and high-fidelity operations.
“Our numerical simulations and experiments on the new H2 quantum computer at small scale indicate that this heuristic algorithm, compared to 1-layer QAOA, is expected to amplify the probability of sampling good or even optimal solutions of large optimization problems,” Dr. Amaro said. “We now want to understand how the solution quality and runtime of our algorithm compares to the best classical algorithms.”
This algorithm will be useful for current quantum computers as well as larger machines farther along the Quantinuum hardware roadmap.
How the Experiment Worked
The goal of this project was to provide a quantum heuristic algorithm for combinatorial optimization that returns better solutions for optimization problems and uses fewer quantum resources than state of the art quantum heuristics. The researchers used a fully connected parameterized IQP, warm-started from 1-layer QAOA. For a problem with n binary variables the circuit contained up to n(n-1)/2 two-qubit gates and the researchers employed only 20.32n shots.
The algorithm showed improved performance on the Sherrington-Kirkpatrick (SK) optimization problem compared to the 1-layer QAOA. Numerical simulations showed an average speed up of 20.31n compared to 20.5n when looking for the optimal solution.
Experimental results on our new H2 quantum computer and emulator confirmed that the new optimization algorithm outperforms 1-layer QAOA and reliably solves complex optimization problems. The optimal solution was found for 136 out of 312 instances, four of which were for the maximum size of 32 qubits. A 30-qubit instance was solved optimally on the H2 device, which means, remarkably, that at least one of the 776 shots measured after performing 432 two-qubit gates corresponds to the unique optimal solution in the huge set of 230 > 109 candidate solutions.
These results indicate that the algorithm, in combination with H2 hardware, is capable of solving hard optimization problems using minimal quantum resources in the presence of real hardware noise.
Quantinuum researchers expect that these promising results at small scale will encourage the further study of new quantum heuristic algorithms at the relevant scale for real-world optimization problems, which requires a better understanding of their performance under realistic conditions.
Speedup of IQP over QAOA
Numerical simulations of 256 SK random instances for each problem size from 4 to 29 qubits. Graph A shows the probability of sampling the optimal solution in the IQP circuit, for which the average is 2-0.31n. Graph B shows the enhancement factor compared to 1-layer QAOA, for which the average is 20.23n. These results indicate that Quantinuum’s algorithm has significantly better runtime than 1-layer QAOA.
About Quantinuum
Quantinuum, the world’s largest integrated quantum company, pioneers powerful quantum computers and advanced software solutions. Quantinuum’s technology drives breakthroughs in materials discovery, cybersecurity, and next-gen quantum AI. With over 500 employees, including 370+ scientists and engineers, Quantinuum leads the quantum computing revolution across continents.
From September 16th – 18th, Quantum World Congress (QWC) will bring together visionaries, policymakers, researchers, investors, and students from across the globe to discuss the future of quantum computing in Tysons, Virginia.
Quantinuum is forging the path to universal, fully fault-tolerant quantum computing with our integrated full-stack. Join our quantum experts for the below sessions and at Booth #27 to discuss the latest on Quantinuum Systems, the world’s highest-performing, commercially available quantum computers, our new software stack featuring the key additions of Guppy and Selene, our path to error correction, and more.
Wednesday, September 17th
Keynote with Quantinuum's CEO, Dr. Rajeeb Hazra
9:00 – 9:20am ET | Main Stage
At QWC 2024, Quantinuum’s President & CEO, Dr. Rajeeb “Raj” Hazra, took the stage to showcase our commitment to advancing quantum technologies through the unveiling of our roadmap to universal, fully fault-tolerant quantum computing by the end of this decade. This year at QWC 2025, join Raj on the main stage to discover the progress we’ve made over the last year in advancing quantum computing on both commercial and technical fronts and be the first to hear exciting insights on what’s to come from Quantinuum.
Panel Session: Policy Priorities for Responsible Quantum and AI
1:00 – 1:30pm ET | Maplewood Hall
As part of the Track Sessions on Government & Security, Quantinuum’s Director of Government Relations, Ryan McKenney, will discuss “Policy Priorities for Responsible Quantum and AI” with Jim Cook from Actions to Impact Strategies and Paul Stimers from Quantum Industry Coalition.
Fireside Chat: Establishing a Pro-Innovation Regulatory Framework
4:00 – 4:30pm ET | Vault Theater
During the Track Session on Industry Advancement, Quantinuum’s Chief Legal Officer, Kaniah Konkoly-Thege, and Director of Government Relations, Ryan McKenney, will take the stage to discuss the importance of “Establishing a Pro-Innovation Regulatory Framework”.
In the world of physics, ideas can lie dormant for decades before revealing their true power. What begins as a quiet paper in an academic journal can eventually reshape our understanding of the universe itself.
In 1993, nestled deep in the halls of Yale University, physicist Subir Sachdev and his graduate student Jinwu Ye stumbled upon such an idea. Their work, originally aimed at unraveling the mysteries of “spin fluids”, would go on to ignite one of the most surprising and profound connections in modern physics—a bridge between the strange behavior of quantum materials and the warped spacetime of black holes.
Two decades after the paper was published, it would be pulled into the orbit of a radically different domain: quantum gravity. Thanks to work by renowned physicist Alexei Kitaev in 2015, the model found new life as a testing ground for the mind-bending theory of holography—the idea that the universe we live in might be a projection, from a lower-dimensional reality.
Holography is an exotic approach to understanding reality where scientists use holograms to describe higher dimensional systems in one less dimension. So, if our world is 3+1 dimensional (3 spatial directions plus time), there exists a 2+1, or 3-dimensional description of it. In the words of Leonard Susskind, a pioneer in quantum holography, "the three-dimensional world of ordinary experience—the universe filled with galaxies, stars, planets, houses, boulders, and people—is a hologram, an image of reality coded on a distant two-dimensional surface."
The “SYK” model, as it is known today, is now considered a quintessential framework for studying strongly correlated quantum phenomena, which occur in everything from superconductors to strange metals—and even in black holes. In fact, The SYK model has also been used to study one of physics’ true final frontiers, quantum gravity, with the authors of the paper calling it “a paradigmatic model for quantum gravity in the lab.”
The SYK model involves Majorana fermions, a type of particle that is its own antiparticle. A key feature of the model is that these fermions are all-to-all connected, leading to strong correlations. This connectivity makes the model particularly challenging to simulate on classical computers, where such correlations are difficult to capture. Our quantum computers, however, natively support all-to-all connectivity making them a natural fit for studying the SYK model.
Now, 10 years after Kitaev’s watershed lectures, we’ve made new progress in studying the SYK model. In a new paper, we’ve completed the largest ever SYK study on a quantum computer. By exploiting our system’s native high fidelity and all-to-all connectivity, as well as our scientific team’s deep expertise across many disciplines, we were able to study the SYK model at a scale three times larger than the previous best experimental attempt.
While this work does not exceed classical techniques, it is very close to the classical state-of-the-art. The biggest ever classical study was done on 64 fermions, while our recent result, run on our smallest processor (System Model H1), included 24 fermions. Modelling 24 fermions costs us only 12 qubits (plus one ancilla) making it clear that we can quickly scale these studies: our System Model H2 supports 56 qubits (or ~100 fermions), and Helios, which is coming online this year, will have over 90 qubits (or ~180 fermions).
However, working with the SYK model takes more than just qubits. The SYK model has a complex Hamiltonian that is difficult to work with when encoded on a computer—quantum or classical. Studying the real-time dynamics of the SYK model means first representing the initial state on the qubits, then evolving it properly in time according to an intricate set of rules that determine the outcome. This means deep circuits (many circuit operations), which demand very high fidelity, or else an error will occur before the computation finishes.
Our cross-disciplinary team worked to ensure that we could pull off such a large simulation on a relatively small quantum processor, laying the groundwork for quantum advantage in this field.
First, the team adopted a randomized quantum algorithm called TETRIS to run the simulation. By using random sampling, among other methods, the TETRIS algorithm allows one to compute the time evolution of a system without the pernicious discretization errors or sizable overheads that plague other approaches. TETRIS is particularly suited to simulating the SYK model because with a high level of disorder in the material, simulating the SYK Hamiltonian means averaging over many random Hamiltonians. With TETRIS, one generates random circuits to compute evolution (even with a deterministic Hamiltonian). Therefore, when applying TETRIS on SYK, for every shot one can just generate a random instance of the Hamiltonain, and generate a random circuit on TETRIS at the same time. This simple approach enables less gate counts required per shot, meaning users can run more shots, naturally mitigating noise.
In addition, the team “sparsified” the SYK model, which means “pruning” the fermion interactions to reduce the complexity while still maintaining its crucial features. By combining sparsification and the TETRIS algorithm, the team was able to significantly reduce the circuit complexity, allowing it to be run on our machine with high fidelity.
They didn’t stop there. The team also proposed two new noise mitigation techniques, ensuring that they could run circuits deep enough without devolving entirely into noise. The two techniques both worked quite well, and the team was able to show that their algorithm, combined with the noise mitigation, performed significantly better and delivered more accurate results. The perfect agreement between the circuit results and the true theoretical results is a remarkable feat coming from a co-design effort between algorithms and hardware.
As we scale to larger systems, we come closer than ever to realizing quantum gravity in the lab, and thus, answering some of science’s biggest questions.
At Quantinuum, we pay attention to every detail. From quantum gates to teleportation, we work hard every day to ensure our quantum computers operate as effectively as possible. This means not only building the most advanced hardware and software, but that we constantly innovate new ways to make the most of our systems.
A key step in any computation is preparing the initial state of the qubits. Like lining up dominoes, you first need a special setup to get meaningful results. This process, known as state preparation or “state prep,” is an open field of research that can mean the difference between realizing the next breakthrough or falling short. Done ineffectively, state prep can carry steep computational costs, scaling exponentially with the qubit number.
Recently, our algorithm teams have been tackling this challenge from all angles. We’ve published three new papers on state prep, covering state prep for chemistry, materials, and fault tolerance.
In the first paper, our team tackled the issue of preparing states for quantum chemistry. Representing chemical systems on gate-based quantum computers is a tricky task; partly because you often want to prepare multiconfigurational states, which are very complex. Preparing states like this can cost a lot of resources, so our team worked to ensure we can do it without breaking the (quantum) bank.
To do this, our team investigated two different state prep methods. The first method uses Givens rotations, implemented to save computational costs. The second method exploits the sparsity of the molecular wavefunction to maximize efficiency.
Once the team perfected the two methods, they implemented them in InQuanto to explore the benefits across a range of applications, including calculating the ground and excited states of a strongly correlated molecule (twisted C_2 H_4). The results showed that the “sparse state preparation” scheme performed especially well, requiring fewer gates and shorter runtimes than alternative methods.
In the second paper, our team focused on state prep for materials simulation. Generally, it’s much easier for computers to simulate materials that are at zero temperature, which is, obviously, unrealistic. Much more relevant to most scientists is what happens when a material is not at zero temperature. In this case, you have two options: when the material is steadily at a given temperature, which scientists call thermal equilibrium, or when the material is going through some change, also known as out of equilibrium. Both are much harder for classical computers to work with.
In this paper, our team looked to solve an outstanding problem: there is no standard protocol for preparing thermal states. In this work, our team only targeted equilibrium states but, interestingly, they used an out of equilibrium protocol to do the work. By slowly and gently evolving from a simple state that we know how to prepare, they were able to prepare the desired thermal states in a way that was remarkably insensitive to noise.
Ultimately, this work could prove crucial for studying materials like superconductors. After all, no practical superconductor will ever be used at zero temperature. In fact, we want to use them at room temperature – and approaches like this are what will allow us to perform the necessary studies to one day get us there.
Finally, as we advance toward the fault-tolerant era, we encounter a new set of challenges: making computations fault-tolerant at every step can be an expensive venture, eating up qubits and gates. In the third paper, our team made fault-tolerant state preparation—the critical first step in any fault-tolerant algorithm—roughly twice as efficient. With our new “flag at origin” technique, gate counts are significantly reduced, bringing fault-tolerant computation closer to an everyday reality.
The method our researchers developed is highly modular: in the past, to perform optimized state prep like this, developers needed to solve one big expensive optimization problem. In this new work, we’ve figured out how to break the problem up into smaller pieces, in the sense that one now needs to solve a set of much smaller problems. This means that now, for the first time, developers can prepare fault-tolerant states for much larger error correction codes, a crucial step forward in the early-fault-tolerant era.
On top of this, our new method is highly general: it applies to almost any QEC code one can imagine. Normally, fault-tolerant state prep techniques must be anchored to a single code (or a family of codes), making it so that when you want to use a different code, you need a new state prep method. Now, thanks to our team’s work, developers have a single, general-purpose, fault-tolerant state prep method that can be widely applied and ported between different error correction codes. Like the modularity, this is a huge advance for the whole ecosystem—and is quite timely given our recent advances into true fault-tolerance.
This generality isn’t just applicable to different codes, it’s also applicable to the states that you are preparing: while other methods are optimized for preparing only the |0> state, this method is useful for a wide variety of states that are needed to set up a fault tolerant computation. This “state diversity” is especially valuable when working with the best codes – codes that give you many logical qubits per physical qubit. This new approach to fault-tolerant state prep will likely be the method used for fault-tolerant computations across the industry, and if not, it will inform new approaches moving forward.
From the initial state preparation to the final readout, we are ensuring that not only is our hardware the best, but that every single operation is as close to perfect as we can get it.