IP Library › Granted Patent US 12,475,401
Granted Patent B2
US 12,475,401 · App. 17/825,908 · Granted Nov 18, 2025

Quantum computer system and method for combinatorial optimization

Inventors: David Amaro (London, GB); Carlo Modica (London, GB); Marcello Benedetti (Vilnius, LT); Mattia Fiorentini (London, GB); Michael Lubasch (London, GB); Matthias Rosenkranz (London, GB)
Assignee: Quantinuum Ltd
G06N10/60G06N10/20G06N10/80
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,475,401
App. No.
17/825,908
Granted
Nov 18, 2025
Kind
B2
Abstract

A computing system including one or more classical binary computers coupled to one or more quantum computers. The computing system is configured to process the one or more computing tasks including at least one combinatorial optimization task using a Filtering Variational Quantum Eigensolver (F-VQE) algorithm implemented by using one or more Ansätze circuits and a cost function arrangement to generate one or more quantum circuits in the quantum computer. The computing system iteratively applies a filtering operator to a cost function arrangement to generate a corresponding filtered cost function arrangement that excludes energy states that exceed an energy threshold and uses the filtered cost function arrangement in the one or more quantum circuits to generate output results.

Claims (42)

1 . A computing system configured to perform at least one combinatorial optimization task, the computing system comprising:

one or more quantum computers; and

one or more classical binary computers coupled to the one or more quantum computers,

wherein the one or more classical binary computers are configured to:

receive one or more computing tasks including the at least one combinatorial optimization task, via an input port of the one or more classical binary computers;

generate a filtered cost function arrangement using a filtering operator;

configure the one or more quantum computers based at least in part on the one or more computing tasks and the filtered cost function arrangement;

generate computational results using output results received from the one or more quantum computers; and

output the computational results via an output port of the one or more classical binary computers;

wherein the one or more quantum computers are configured to execute one or more quantum circuits to generate the output results,

wherein the computing system is configured to generate and configure the one or more quantum circuits using a Filtering Variation Quantum Eigensolver (F-VQE) algorithm implemented based at least in part on one or more Ansätze circuits and the filtered cost function arrangement, and

wherein the computing system is configured to generate the computational results by applying the filtering operator to increase a probability of sampling of eigenstates having lower energies.

2 . The computing system of claim 1 , wherein the one or more classical binary computers are configured to compute one or more causal cones that are representative of one or more principal computation paths within the one or more quantum circuits that contribute to the output results, and wherein the one or more classical binary computers are configured to omit one or more parts of the one or more quantum circuit whose contribution to the output results are below a threshold value.

3 . The computing system of claim 2 , wherein omitting the one or more parts corresponds to a reduction in a number of qubits and gates required to implement the one or more quantum circuits.

4 . The computing system of claim 2 , wherein omitting the one or more parts corresponds to a reduction in circuit depth of the one or more quantum circuits.

5 . The computing system of claim 1 , wherein applying the filtering operator on an initial quantum state projects out corresponding high-energy eigenstates and generates a resulting quantum state having a larger overlap with a ground state, wherein the high-energy eigenstates correspond to sub-optimal solutions to the at least one combinatorial optimization task.

6 . The computing system of claim 1 , wherein applying the filtering operator computing a stochastic gradient descent.

7 . The computing system of claim 1 , wherein applying the filtering operator causes the filtered cost function arrangement to converge to a ground state using fewer optimization steps compared to applying a Variational Quantum Eigensolver (VQE) or applying a Quantum Approximate Optimization Algorithm (QAOA).

8 . The computing system of claim 1 , wherein at least a subset of the one or more quantum computers is implemented using trapped ion quantum processors.

9 . The computing system of claim 1 , wherein the filtered cost function is used to compute the smallest energy expectation value associated with the one or more quantum circuits.

10 . The computing system of claim 1 , wherein the Ansätze circuits comprise at least one parametrized quantum circuit.

11 . The computing system of claim 1 , wherein the filtering operator comprises a real-valued function (f) of a Hamiltonian associated with the combinatorial optimization task and a scalar parameter, and wherein the square of the real-valued function (f 2 ) strictly decreases with energy.

12 . The computing system of claim 11 , wherein the real-valued function (f) is selected from a group containing: inverse function, logarithm, exponential, power, cosine, or Chebyshev.

13 . The computing system of claim 10 , wherein an action of the filtering operator is approximated by successively optimizing variation parameters of a parameterized quantum circuit.

14 . A method for using a computing system including one or more classical binary computers coupled to one or more quantum computers to perform at least one combinatorial optimization task, the method comprising:

by a hardware processor of the one or more classical binary computers:

receiving one or more computing tasks via an input port of the one or more classical binary computers;

generate a filtered cost function arrangement using a filtering operator;

configuring the one or more quantum computers based at least in part on the one or more computing tasks by generating one or more quantum circuits based on a Filtering Variational Quantum Eigensolver (F-VQE) algorithm, wherein the F-VQE algorithm is implemented based at least in part on one or more Ansätze circuits and the filtered cost function arrangement;

executing the one or more quantum circuits to generate output results;

generating computational results using the output results received from the one or more quantum computers;

outputting the computational results via an output port of the one or more classical binary computers;

wherein executing the one or more quantum circuits comprises applying the filtering operator to increase a probability of sampling eigen states having lower energies, and

wherein the filtered cost function arrangement is used in the one or more quantum circuits to generate the output results.

15 . The method of claim 14 , further comprising configuring the one or more classical binary computers to compute one or more causal cones that are representative of one or more principal computation paths within the one or more quantum circuits that contribute to the output results, and wherein the one or more classical binary computers are configured to omit one or more parts of the one or more quantum circuit whose contribution to the output results are below a threshold value.

16 . The method of claim 15 , further comprising omitting the one or more parts corresponds to a reduction in a number of qubits required to implement the one or more quantum circuits.

17 . The method of claim 16 , wherein omitting the one or more parts corresponds to a reduction in circuit depth of the one or more quantum circuits.

18 . The method of claim 14 , wherein applying the filtering operator projects out corresponding high-energy eigenstates of a corresponding quantum state, wherein the high-energy eigenstates correspond to sub-optimal solutions to the at least one combinatorial optimization task.

19 . The method of claim 14 , wherein applying the filtering operator comprises computing a stochastic gradient descent.

20 . The method of claim 14 , wherein applying the filtering operator causes the filtered cost function arrangement to converge to a ground state using fewer optimization steps compared to Variational Quantum Eigensolver (VQE) Quantum or Approximate Optimization Algorithm (QAOA).

21 . The method of claim 14 , wherein at least a subset of the one or more quantum computers is implemented using trapped ion quantum processors.

22 . A machine-readable data storage medium comprising specific instructions that is executable on a data processing hardware of the computing system to implement the method of claim 14 .

Assignments (2)
CHANGE OF NAME Recorded Oct 30, 2023
From: CAMBRIDGE QUANTUM COMPUTING LIMITED
To: QUANTINUUM LTD
Reel/Frame 065396/0682 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 24, 2023
From: AMARO, DAVID; MODICA, CARLO; BENEDETTI, MARCELLO; FIORENTINI, MATTIA; LUBASCH, MICHAEL; ROSENKRANZ, MATTHIAS
To: CAMBRIDGE QUANTUM COMPUTING LTD.
Reel/Frame 063749/0092 →
Priority Claims (1)
GB 2107468 · May 26, 2021 · national
Continuity (1)
Related Publication 20220391742A1 · Dec 8, 2022
References Cited (82)
US 20180259559A1 · Humphrey · 2018 [cited by examiner]
US 20190164079A1 · Gambetta · 2019 [cited by examiner]
US 20200372094A1 · Shehab · 2020 [cited by examiner]
US 20220383177A1 · Alcazar · 2022 [cited by examiner]
US 20230237361A1 · Cowtan · 2023 [cited by examiner]
Amaro et al., Feb. 10, 2022, Filtering variational quantum algorithms for combinatorial optimization, arXiv:2106.10055v3, [quant-ph], 14 pp. [cited by applicant]
Alcazar J. et al., Enhancing Combinatorial Optimization with Quantum Generative Model, (2021), arXiv:2101.06250 [quant-ph]. [cited by applicant]
Bañuls, M.C. et al., Entanglement And Its Relation to Energy Variance for Local One-Dimensional Hamiltonians, Phys. Rev. B, vol. 101, 144305 (2020). [cited by applicant]
Barkoutsos, P. K. et al., Improving Variational Quantum Optimization Using CVaR, arXiv:1907.04769v3 (2020). (also published in Quantum, vol. 4, No. 256. 2020). [cited by applicant]
Benedetti, M. et a., Parameterized Quantum Circuits as Machine Learning Models, arXiv:1906.07682v2 (2019). (also published in Quantum Sci. Technol. 4, 043001, 2019). [cited by applicant]
Benedetti, M. et al., Hardware-Efficient Variational Quantum Algorithms for Time Evolution, Physical Review Research, vol. 3, 033083 (2021). [cited by applicant]
Berman, P. et al., On Some Tighter Inapproximability Results (Extended Abstract), In Automata, Languages and Programming, Edited by J. Wiedermann, P. Van Emde Boas, and M. Nielsen (Springer Berlin Heidelberg, Berlin, He… [cited by applicant]
Bharti, K. et al., Noisy Intermediate-Scale Quantum (NISQ) algorithms, (2021), arXiv:2101.08448 [quant-ph]. [cited by applicant]
Bravo-Prieto, C. et al., Quantum Singular Value Decomposer, arXiv:2002.06210v4 (2020). (also published in Physical Review A, vol. 101, 062310, 2020). [cited by applicant]
Bravo-Prieto, C. et al., Scaling of Variational Quantum Circuit Depth for Condensed Matter Systems, arXiv:2002.06210v4 (2020). (also published in Quantum, vol. 4, No. 272, 2020). [cited by applicant]
Cakan, A. et al., Approximating the Long Time Average of the Density Operator: Diagonal Ensemble, arXiv:2011.01257v1 (2021). (also published in Phys. Rev. B 103, 115113, 2021). [cited by applicant]
Cao, C. et al., Noise-Assisted Quantum Autoencoder, arXiv:2012.08331v2, (2021). (also published in Physical Review Applied, vol. 15, 054012, 2021). [cited by applicant]
Cerezo, M. et al., Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits, arXiv:2001.00550v3 (2021). (also published in Nature Communications, vol. 12, No. 1791, 2021). [cited by applicant]
Cerezo, M. et al., Variational Quantum Algorithms, arXiv:2012.09265v2 (2021). (also published in Nature Reviews Physics, vol. 3, No. 625, 2021). [cited by applicant]
Chertkov, E. et al., Holographic Dynamics Simulations with a Trapped Ion Quantum Computer, (2021), arXiv:2105.09324 [quant-ph]. [cited by applicant]
Cirac, J. I. et al., Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, Theorems, arXiv:2011.12127v2 (2021). (also published in Reviews of Modern Physics, vol. 93, 045003, 2021). [cited by applicant]
Dalgaard, M. et al., Hessian-Based Optimization of Constrained Quantum Control, Physical Review A, vol. 102, 042612 (2020). [cited by applicant]
Diez-Valle, P. et al., Quantum Variational Optimization: The Role of Entanglement and Problem Hardness, arXiv:2103.14479v2, (2021). (also published in Physical Review A, 104, 062426, 2021). [cited by applicant]
Du, Y. et al., Quantum Circuit Architecture Search: Error Mitigation and Trainability Enhancement for Variational Quantum Solvers, arXiv:2010.10217v2 [quant-ph] (2020). [cited by applicant]
Farhi E. et al., Quantum Supremacy Through the Quantum Approximate Optimization Algorithm, arXiv:1602.07674 v2 [quant-ph] (2019). [cited by applicant]
Farhi, E. et al., A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of An NP-Complete Problem, arXiv:quant-ph/0104129v1 (2021). (also published in Science, vol. 292, No. 472, 2001). [cited by applicant]
Farhi, E. et al., A Quantum Approximate Optimization Algorithm, (2014), arXiv:1411.4028 [quant-ph]. [cited by applicant]
Fernandez-Lorenzo, S. et al., Hybrid quantum—Classical Optimization with Cardinality Constraints and Applications to Finance, arXiv:2008.12050v2 (2021). (also published in Quantum Sci. Technol. 6 034010, 2021). [cited by applicant]
Foss-Feig, M. et al., Entanglement from Tensor Networks on a Trapped-Ion QCCD Quantum Computer, arXiv:2104.11235 [quant-ph] (2021). [cited by applicant]
Foss-Feig, M. et al., Holographic Quantum Algorithms for Simulating Correlated Spin Systems, Physical Review Research, vol. 3, 033002 (2021). [cited by applicant]
Garcia-Saez A. et al., Addressing Hard Classical Problems with Adiabatically Assisted Variational Quantum Eigensolvers, arXiv:1806.02287 [quant-ph] (2018). [cited by applicant]
Ge, Y. et al., Faster Ground State Preparation and High-Precision Ground Energy Estimation with Fewer qubits, arXiv:1712.03193v2 (2019). (also published in Journal of Mathematical Physics, vol. 60, 022202, 2019). [cited by applicant]
Glover, F. et al., Quantum Bridge Analytics I: A Tutorial on Formulating and using QUBO models, Computer Science, Data Structures and Algorithms, 4OR 17, 335 (2019). [cited by applicant]
Grimsley, H. R. et al., An Adaptive Variational Algorithm for Exact Molecular Simulations on a Quantum Computer, Nature Communications, vol. 10, 3007 (2019). [cited by applicant]
Hadfield, S. et al., From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz, arXiv:1709.03489v2 (2019). (also published in Algorithms, vol. 12, No. 34, 2019). [cited by applicant]
Harrigan, M. P. et al., Quantum Approximate Optimization of Non-Planar Graph Problems On A Planar Superconducting Processor, arXiv:2004.04197v3 (2021). (also published in Nature Physics, vol. 17, No. 332, 2021). [cited by applicant]
Hastad, J., Some Optimal Inapproximability Results, Journal of the ACM, vol. 48, No. 4., pp. 798-859 (2001). [cited by applicant]
Helmberg, C., Semidefinite Programming For Combinatorial Optimization, 2000. [cited by applicant]
Kadowaki T. et al., Quantum Annealing in the Transverse Ising Model, arXiv:cond-mat/9804280v1 (1998). (also published in Physical Review, vol. 58, 5355, 1998). [cited by applicant]
Kirkpatrick, S. et al., Optimization By Simulated Annealing, Science, vol. 220, No. 4598, 1983. [cited by applicant]
Kochenberger, G. et al., The Unconstrained Binary Quadratic Programming Problem: A Survey, Journal of Combinatorial Optimization, vol. 28, Issue 1, pp. 58-81, 2014. [cited by applicant]
Kolotouros I. et al., An Evolving Objective Function For Improved Variational Quantum Optimization, (2021), arXiv:2105.11766 [quant-ph]. [cited by applicant]
Korte B. et al., Combinatorial Optimization: Theory and Algorithms, 6th ed. (Springer Publishing Company, Incorporated, 2018). [cited by applicant]
Kyriienko, O. et al., Quantum Inverse Iteration Algorithm For Programmable Quantum Simulators, npj Quantum Information, vol. 6, No. 7 (2020). [cited by applicant]
Trefethen L.N. et al., Numerical Linear Algebra, SIAM (Society for Industrial and Applied Mathematics) Philadelphia, 1997. [cited by applicant]
LaRose, R. et al., Mixer-phaser Ansatze for Quantum Optimization with Hard Constraints, (2021), arXiv:2107.06651 [quant-ph]. [cited by applicant]
Liu, X. et al., Layer VQE: A Variational Approach For Combinatorial Optimization On Noisy Quantum Computers, (2021), arXiv:2102.05566v1 [quant-ph]. [cited by applicant]
Lu, S. et al., Algorithms For Quantum Simulation at Finite Energies, (2020), arXiv:2006.03032v2 [quant-ph]. [cited by applicant]
Lubasch, M. et al., Multigrid Renormalization, Journal of Computational Physics, vol. 372, 587,2018. [cited by applicant]
Lubasch, M. et al., Systematic Construction of Density Functionals Based on Matrix Product State Computations, New Journal of Physics, vol. 18, 083039 (2016). [cited by applicant]
Lucas, A., Ising Formulations of Many NP Problems, arXiv:1302.5843v3 (2014). (also published in Frontiers in Physics, vol. 2, No. 5, 2014). [cited by applicant]
Majumdar, R. et al., Depth Optimized Ansatz Circuit in QAOA for Max-Cut, (2021), arXiv:2110.04637 [quant-ph]. [cited by applicant]
Mari, A. et al., Estimating the Gradient and Higher-Order Derivatives on Quantum Hardware, arXiv:2008.06517v2 (2021. (also published in Physical Review A, vol. 103, 012405, 2021). [cited by applicant]
Mitarai, K. et al., Quantum Circuit Learning, [arXiv:1803.00745v3] (2018). (also published in Phys. Rev. A 98, 032309, 2018). [cited by applicant]
Moll, N. et al., Quantum Optimization Using Variational Algorithms on Near-Term Quantum Devices, [arXiv:1710.01022v2 (2018). (also published in Quantum Science and Technology, vol. 3, 030503, 2018). [cited by applicant]
Moussa, C. et al., To Quantum or Not to Quantum: Towards Algorithm Selection in Near-Term Quantum Optimization, arXiv:2001.08271v2 (2020). (also published in Quantum Science and Technology, vol. 5, 044009, 2005). [cited by applicant]
Noble, J. et al., Diagonalization of Complex Symmetric Matrices: Generalized Householder Reflections, Iterative Deflation and Implicit Shifts, Computational Physics Communication, vol. 221, No. 304 (2017). [cited by applicant]
Noble, J. et al., Generalized Householder Transformations for the Complex Symmetric Eigenvalue Problems, arXiv:1301.5758v3 (2012). (also published in The European Physical Journal Plus, vol. 128, No. 93, 2013). [cited by applicant]
Ostaszewski, M. et al., Structure optimization for parameterized quantum circuits, arXiv:1905.09692v3 (2012). (also published in Quantum, vol. 5, No. 391, 2021). [cited by applicant]
Ostaszewski, M. et al., Reinforcement learning for optimization of variational quantum circuit architectures, arXiv:2103.16089 [quant-ph] (2012). [cited by applicant]
Orus, R., A practical introduction to tensor networks: Matrix product states and projected entangled pair states, arXiv:1306.2164v2 (2014). (also published in Annals of Physics, vol. 349, No. 117, 2014). [cited by applicant]
Patti, T. L. et al., Variational Quantum Optimization with Multi-Basis Encodings, (2022), arXiv:2106.13304 [quant-ph]. [cited by applicant]
Peruzzo, A. et al., A Variational Eigenvalue Solver on a Photonic Quantum Processor, arXiv:1304.3061v1 (2013). (also published in Nature Communications, vol. 5, No. 4213, 2014). [cited by applicant]
Pino, J. M. et al., Demonstration of the Trapped-Ion Quantum CCD Computer Architecture, arXiv:2003.01293v4 (2021). (also published in Nature, vol. 592, No. 209, 2021). [cited by applicant]
Romero, J. et al., Quantum Autoencoders for Efficient Compression of Quantum Data, Quantum Science and Technology, vol. 2, 045001 (2017). [cited by applicant]
Rothman, D. H., Large Near-Surface Anomalies, Seismic Reflection Data, and Simulated Annealing. SEP-45, (Ph.D. thesis, Stanford University, 1985). [cited by applicant]
Saleem, Z. H. et al., Quantum Divide and Conquer for Combinatorial Optimization and Distributed Computing, arXiv:2107.07532 [quant-ph] (2021). [cited by applicant]
Schuld, M. et al., Evaluating Analytic Gradients on Quantum Hardware, Physical Review A, vol. 99, 032331 (2019). [cited by applicant]
Sivarajah, S. et al., t|ket>: A Retargetable Compiler for NISQ devices, arXiv:2003.10611v3 (2020). (also published in Quantum Science and Technology, vol. 6, 014003, 2020). [cited by applicant]
Skolik, A. et al., Layerwise Learning for Quantum Neural Networks, Quantum Machine Intelligence, vol. 3, No. 5 (2021). [cited by applicant]
Sweke, R. et al., Stochastic Gradient Descent For Hybrid Quantum-Classical Optimization, arXiv:1910.01155v3 (2020). (also published in Quantum, vol. 4, No. 314, 2020). [cited by applicant]
Vidal, G., Class of Quantum Many-Body States that can Be Efficiently Simulated, arXiv:quant-ph/0610099v1 (2008). (also published in Physical Review Letters, vol. 101, 110501, 2008). [cited by applicant]
Wecker, D. et al., Progress Towards Practical Quantum Variational Algorithms, Physical Review A, vol. 92, 042303 (2015). [cited by applicant]
Weiße, A. et al., The Kernel Polynomial Method, arXiv:cond-mat/0504627v2 (2006). (also published in Reviews of Modern Physics, vol. 78, No. 275, 2006). [cited by applicant]
Wiersema, R. et al., Exploring Entanglement and Optimization within The Hamiltonian Variational Ansatz, arXiv:2008.02941v2 (2020). (also published in PRX Quantum, vol. 1, 020319, 2020). [cited by applicant]
Yang, Y. et al., Probing Thermalization Through Spectral Analysis with Matrix Product Operators, arXiv:1909.01398v1 (2020). (also published in Phys. Rev. Lett. 124, 100602, 2020). [cited by applicant]
Zeng, P. et al., Universal quantum algorithmic cooling on a quantum computer, arXiv:2109.15304v1 [quant-ph] (2021). [cited by applicant]
Zhang, S. X. et al., Variational Quantum-Neural Hybrid Eigensolver, arXiv:2106.05105 [quant-ph] (2021). [cited by applicant]
Zhou, L. et al., Quantum Approximate Optimization Algorithm: Performance, Mechanism, And Implementation On Near-Term Devices, Physical Review X, vol. 10, 021067 (2020). [cited by applicant]
Zhu, L. et al., An Adaptive Quantum Approximate Optimization Algorithm for Solving Combinatorial Problems on a Quantum Computer, arXiv:2005.10258v3 [quant-ph] (2020). [cited by applicant]
Garcia-Ripoll, J. J., et al., Quantum-Inspired Algorithms for Multivariate Analysis: From Interpolation to Partial Differential Equations, arXiv:1909.06619v5 (2021) (also published in Quantum, vol. 5, p. 431, (2021). [cited by applicant]
Amaro, D. et al., A case study of variational quantum algorithms for a job shop scheduling problem arXiv:2109.03745v1 [quant-ph] (2021). [cited by applicant]