Quantinuum Researchers Demonstrate a new Optimization Algorithm that delivers solutions on H2 Quantum Computer
Algorithm reliably and consistently solves combinatorial optimization problems using minimal quantum resources
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.
Kaniah is Chief Legal Counsel and SVP of Government Relations for Quantinuum. In her previous role, she served as General Counsel, Honeywell Quantum Solutions. Prior to Honeywell, she was General Counsel, Honeywell Federal Manufacturing and Technologies, LLC, and Senior Attorney, U.S. Department of Energy. She was Lead Counsel before the Civilian Board of Contract Appeals, the Merit Systems Protection Board, and the Equal Employment Opportunity Commission. Kaniah holds a J.D. from American University, Washington College of Law and B.A., International Relations and Spanish from the College of William and Mary.
Jeff Miller is Chief Information Officer for Quantinuum. In his previous role, he served as CIO for Honeywell Quantum Solutions and led a cross-functional team responsible for Information Technology, Cybersecurity, and Physical Security. For Honeywell, Jeff has held numerous management and executive roles in Information Technology, Security, Integrated Supply Chain and Program Management. Jeff holds a B.S., Computer Science, University of Arizona. He is a veteran of the U.S. Navy, attaining the rank of Commander.
Matthew Bohne is the Vice President & Chief Product Security Officer for Honeywell Corporation. He is a passionate cybersecurity leader and executive with a proven track record of building and leading cybersecurity organizations securing energy, industrial, buildings, nuclear, pharmaceutical, and consumer sectors. He is a sought-after expert with deep experience in DevSecOps, critical infrastructure, software engineering, secure SDLC, supply chain security, privacy, and risk management.
Todd Moore is the Global Vice President of Data Encryption Products at Thales. He is responsible for setting the business line and go to market strategies for an industry leading cybersecurity business. He routinely helps enterprises build solutions for a wide range of complex data security problems and use cases. Todd holds several management and technical degrees from the University of Virginia, Rochester Institute of Technology, Cornell University and Ithaca College. He is active in his community, loves to travel and spends much of his free time supporting his family in pursuing their various passions.
Retired U.S. Army Major General John Davis is the Vice President, Public Sector for Palo Alto Networks, where he is responsible for expanding cybersecurity initiatives and global policy for the international public sector and assisting governments around the world to prevent successful cyber breaches. Prior to joining Palo Alto Networks, John served as the Senior Military Advisor for Cyber to the Under Secretary of Defense for Policy and served as the Acting Deputy Assistant Secretary of Defense for Cyber Policy. Prior to this assignment, he served in multiple leadership positions in special operations, cyber, and information operations.
