IP Library › Granted Patent US 12,664,230
Granted Patent B2
US 12,664,230 · App. 17/717,823 · Granted Jun 23, 2026

Hardware accelerated minor embedding for quantum annealing

Inventors: Andrew Dudash (Reston, VA); Gabrielle Olshan-Cantin (Reston, VA); Sarad Pant (Reston, VA)
Assignee: NOBLIS, INC.
G06F17/11G06N10/40
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,664,230
App. No.
17/717,823
Filed
Apr 11, 2022
Granted
Jun 23, 2026
Kind
B2
Art Unit
2151
USPC
708/446
Abstract

Methods for configuring a quantum annealer to solve a QUBO problem comprises receiving data representing an initial graph representing an embedding of a QUBO problem into a qubit architecture of the quantum annealer and causing one or more GPU thread blocks to create and store a best local current graph and update the best local current graph. Updating the best current local graph comprises copying the best local current graph, modifying the best local current graph copy to form a candidate local graph, computing an evaluation rating for the candidate local graph, and, in accordance with a determination that one or more replacement criteria are met, replacing the best local current graph with the candidate local graph. An updated best local current graph may be identified in a local results array as the best global graph. The quantum annealer may be configured based on the best local graph.

Claims (70)

1 . A method for configuring a quantum annealer to solve a quadratic unconstrained binary optimization (QUBO) problem, the method comprising:

receiving data representing an initial graph representing an embedding of the QUBO problem into a physical qubit architecture of the quantum annealer;

initializing one or more graphical processing unit (GPU) thread blocks;

for each of the one or more GPU thread blocks:

creating and storing a best local current graph, wherein an initial version of the best local current graph is based on the received data representing the initial graph; and

updating the best local current graph, wherein the updating comprises:

copying the best local current graph to form a best local current graph copy,

modifying the best local current graph copy to form a candidate local graph,

computing an evaluation rating for the candidate local graph, and

determining, based on the evaluation rating for the candidate local graph and an evaluation rating for the best local current graph, whether one or more replacement criteria are met;

in accordance with a determination that the one or more replacement criteria are met, replacing the best local current graph with the candidate local graph;

storing one or more updated best local current graphs associated respectively with each of the one or more GPU thread blocks in a local results array;

identifying an updated best local current graph of the one or more updated best local current graphs in the local results array as a best global graph; and

configuring the quantum annealer based on the best global graph.

2 . The method of claim 1 , wherein the data representing the initial graph comprises an adjacency matrix.

3 . The method of claim 1 , further comprising receiving an input indicating an iteration number, wherein the iteration number is an integer greater than or equal to one, wherein, for each of the one or more GPU thread blocks, updating the best local current graph is repeated a number of times equal to the iteration number.

4 . The method of claim 1 , wherein modifying the best local current graph copy to form the candidate local graph comprises:

selecting a logical qubit mapped to a first location in the best local current graph; and

mapping, in the candidate local graph, the logical qubit to a new placement representing one or more vacant physical qubits of the quantum annealer.

5 . The method of claim 4 , wherein the new placement representing the one or more vacant physical qubits is adjacent to an existing placement of the selected logical qubit.

6 . The method of claim 4 , wherein the new placement representing the one or more vacant physical qubits is selected randomly.

7 . The method of claim 1 , wherein modifying the best local current graph copy to form the candidate local graph comprises:

selecting a first logical qubit mapped to a first location in the best local current graph;

selecting a second logical qubit mapped to a second location in the best local current graph;

mapping, in the candidate local graph, the first logical qubit to the second location; and

mapping, in the candidate local graph, the second logical qubit to the first location.

8 . The method of claim 1 , wherein modifying the best local current graph copy to form the candidate local graph comprises:

selecting a set of logical qubits forming a subgraph in the best local current graph; and

mapping, in the candidate local graph, the set of logical qubits to a new set of placements representing one or more vacant physical qubits of the quantum annealer.

9 . The method of claim 8 , wherein the new set of placements is selected such that an arrangement of existing placements in the subgraph is preserved.

10 . The method of claim 1 , wherein the evaluation rating for the candidate local graph is based on a maximum chain length associated with the candidate local graph.

11 . The method of claim 1 , wherein the evaluation rating for the candidate local graph is based on a total weighted connection between one or more vertices in the candidate local graph.

12 . The method of claim 1 , wherein the evaluation rating for the candidate local graph is based on a total number of physical qubits of the quantum annealer required by the candidate local graph.

13 . The method of claim 1 , wherein the evaluation rating for the candidate local graph is based on a total number of physical qubits of the quantum annealer, required by the candidate local graph, that are detrimental to a quantum annealing process.

14 . The method of claim 1 , wherein determining whether the one or more replacement criteria are met comprises comparing the evaluation rating for the candidate local graph and the evaluation rating for the best local current graph.

15 . The method of claim 1 , wherein determining whether the one or more replacement criteria are met comprises:

determining whether the evaluation rating for the candidate local graph is lower than the evaluation rating for the best local current graph;

if the evaluation rating for the candidate local graph is lower than the evaluation rating for the best current local graph:

computing a probability of the candidate local graph replacing the best local current graph based on the evaluation rating of the candidate local graph and based on the evaluation rating of the best local current graph; and

determining whether the one or more replacement criteria are met based on the computed probability.

16 . The method of claim 15 , wherein the probability of the candidate local graph replacing the best local current graph is further based on an iteration number equal to a number of times a respective GPU thread block of the one or more GPU thread blocks has already updated the best local current graph.

17 . The method of claim 1 , wherein identifying the updated best local current graph in the local results array as the best global graph comprises selecting an updated best local current graph with a highest evaluation score as the best global graph.

18 . A system for configuring a quantum annealer to solve a quadratic unconstrained binary optimization (QUBO) problem, the system comprising one or more processors configured to:

receive data representing an initial graph representing an embedding of the QUBO problem into a physical qubit architecture of the quantum annealer;

initialize one or more graphical processing unit (GPU) thread blocks;

for each of the one or more GPU thread blocks:

create and store a best local current graph, wherein an initial version of the best local current graph is based on the received data representing the initial graph; and

update the best local current graph, wherein the updating comprises:

copying the best local current graph to form a best local current graph copy,

modifying the best local current graph copy to form a candidate local graph,

computing an evaluation rating for the candidate local graph, and

determining, based on the evaluation rating for the candidate local graph and an evaluation rating for the best local current graph, whether one or more replacement criteria are met;

in accordance with a determination that the one or more replacement criteria are met, replace the best local current graph with the candidate local graph;

store one or more updated best local current graphs associated respectively with each of the one or more GPU thread blocks in a local results array;

identify an updated best local current graph of the one or more updated best local current graphs in the local results array as a best global graph; and

configure the quantum annealer based on the best global graph.

19 . A non-transitory computer readable storage medium comprising instructions for configuring a quantum annealer to solve a quadratic unconstrained binary optimization (QUBO) problem that, when executed by one or more processors, cause the one or more processors to:

receive data representing an initial graph representing an embedding of the QUBO problem into a physical qubit architecture of the quantum annealer;

initialize one or more graphical processing unit (GPU) thread blocks;

for each of the one or more GPU thread blocks:

create and store a best local current graph, wherein an initial version of the best local current graph is based on the received data representing the initial graph; and

update the best local current graph, wherein the updating comprises:

copying the best local current graph to form a best local current graph copy,

modifying the best local current graph copy to form a candidate local graph,

computing an evaluation rating for the candidate local graph, and

determining, based on the evaluation rating for the candidate local graph and an evaluation rating for the best local current graph, whether one or more replacement criteria are met;

in accordance with a determination that the one or more replacement criteria are met, replace the best local current graph with the candidate local graph;

store one or more updated best local current graphs associated respectively with each of the one or more GPU thread blocks in a local results array;

identify an updated best local current graph of the one or more updated best local current graphs in the local results array as a best global graph; and

configure the quantum annealer based on the best global graph.

Assignments (2)
SECURITY INTEREST Recorded May 27, 2025
From: NOBLIS, INC.
To: PNC BANK, NATIONAL ASSOCIATION
Reel/Frame 071415/0887 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 9, 2022
From: DUDASH, ANDREW; OLSHAN-CANTIN, GABRIELLE; PANT, SARAD
To: NOBLIS, INC.
Reel/Frame 060148/0710 →
Continuity (1)
Related Publication 20230325461A1 · Oct 12, 2023
References Cited (52)
US 20080218519A1 · Coury · 2008 [cited by examiner]
US 20160055421A1 · Adachi · 2016 [cited by examiner]
Abhari. (2014) “ScaffCC: A Framework for Compilation and Analysis of Quantum Computing Programs,” Proceedings of the 11th ACM Conference on Computing Frontiers, May 20-22, 2014, Calgari, Italy, 10 pages. [cited by applicant]
Adedoyin. (Mar. 2018) “Quantum Algorithm Implementations for Beginners,” Los Alamos; arXiv:1804.03719v2; 94 pages. [cited by applicant]
Aho et al. (1986). Compilers: Principles, Techniques, and Tools, Michael Hirsch ed.; Pearson Education, Inc.; 1035 pages. [cited by applicant]
Amy et al. (2020). “staq—A Full-Stack Quantum Processing Toolkit,” arXiv:1912.06070v2; 21 pages. [cited by applicant]
Amy et al. (Oct. 2014) “Polynomial-Time T-Depth Optimization of Clifford+T Circuits Via Matroid Partitioning,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 33, No. 10.; pp. 1476-14… [cited by applicant]
Amy. (Aug. 2018) “On the controlled-NOT complexity of controlled-NOT-phase circuits,” Quantum Science and Technology, vol. 4; arXiv:1712.01859v2; 21 pages. [cited by applicant]
Appel. (2006). Compiling with Continuations, Cambridge University Press, New York; 8 pages. [cited by applicant]
Bar-Noy et al. (Feb. 1998) “On chromatic sums and distributed resource allocation,” Information and Computation, vol. 140, pp. 183-202. [cited by applicant]
Bertot et al. “A Structured Approach to Proving Compiler Optimizations Based on Dataflow Analysis”; 2004 International Conference on Types of Proofs and Programs, Dec. 15-18, 2004, Jouy-en-Josas, France, 16 pages. [cited by applicant]
Bian et al. (Mar. 2016) “Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis,” Frontiers in ICT; arXiv:1603.03111v1; 22 pages. [cited by applicant]
Bianchi et al. (Apr. 2020). “Knowledge Graph Embeddings andExplainable AI,” arXiv:2004.14843v1; 24 pages. [cited by applicant]
Booth et al. (2018) “Comparing and Integrating Constraint Programming and Temporal Planning for Quantum Circuit Compilation,” 28th International Conference on Automated Planning and Scheduling; Jun. 24, 2018, Delft, The… [cited by applicant]
Bunyk et al. (Aug. 2014) “Architectural Considerations in The Design of a Superconducting Quantum Annealing Processor,” arXiv:1401.5504v1; 9 pages. [cited by applicant]
Cai et al. (Jun. 2014) “A Practical Heuristic Finding Graph Minors,” arXiv:1406.2741v1; 16 pages. [cited by applicant]
Chaitin et al. (Jan. 1981) “Register Allocation via Coloring,” Computer Languages, vol. 6, pp. 47-57. [cited by applicant]
Svore et al. (2004) “Toward a software architecture for quantum computing design tools,” Proc. Quantum Physics and Logic, pp. 145-162. [cited by applicant]
Cuccaro et al. (Feb. 2008) “A New Quantum Ripple-Carry Addition Circuit,” arXiv:quant-ph/0410184v1; 9 pages. [cited by applicant]
Dill et al. (2012) “The Protein-Folding Problem, 50 Years On,” Science 338; pp. 1042-1046. [cited by applicant]
Etschmaier et al. (1985) “Airline Scheduling: An Overview,” Transportation Science, vol. 19, No. 2, 12 pages. [cited by applicant]
Facchetti et al. (Dec. 2011) “Computing Global Structural Balance in Large-Scale Signed Social Networks,” Proceedings of the National Academy of Sciences 108(52); 7 pages. [cited by applicant]
Gidney. (2019) “Asymptotically Efficient Quantum Karatsuba Multiplication,” arXiv:1904.07356v1; Santa Barbara, California; 11 pages. [cited by applicant]
Grants Notice. (Apr. 22, 2017) Located at <https://www.grants.gov/web/grants/view—opportunity.html?oppld=292877opportunity.html?oppld=292877> retrieved on Apr. 19, 2022; 2 pages. [cited by applicant]
Haner et al. (May 2016) , “A Software Methodology for Compiling Quantum Programs,” Zurich, Switzerland; 14 pages. [cited by applicant]
Hietala et al. (Dec. 2019) “Verified Optimization in a Quantum Intermediate Representation,” arXiv:1904.06319v4; 18 pages. [cited by applicant]
Iwama et al. (2002) “Transformation Rules for Designing CNOT-based Quantum Circuits,” Design Automation Conference, Jun. 10-14, 2002, New Orleans, Louisiana, USA, 6 pages. [cited by applicant]
James. “UAV Swarm Path Planning,” in 2020 Integrated Communications Navigation and Surveillance Conference (ICNS), Sep. 8-9, 2020, Herndon, VA, USA; 12 pages. [cited by applicant]
Kissinger et al. (2019) “PyZX: Large Scale Automated Diagramatic Reasoning,” in Quantum Physics and Logic; 13 pages. [cited by applicant]
Kunegis. (Feburary 2014) Applications of Structural Balance in Signed Social Networks; arXiv:1402.6865v1; 37 pages. [cited by applicant]
Lewis et al. (Sep. 2017) “Quadratic Unconstrained Binary Optimization Problem Preprocessing: Theory and Empirical Analysis,” Netw., 70(2); 31 pages. [cited by applicant]
Li et al. (Sep. 2009) “Genotype Imputation,” Annual Review of Genomics and Human Genetics, vol. 10, pp. 387-407. [cited by applicant]
Lomont. (Jul. 2003) “Quantum Circuit Identities,” arXiv:quant-ph/0307111v1; 6 pages. [cited by applicant]
Marx. (2004).“Graph colouring problems and their applications in scheduling,” Periodica Polytechnica Electrical Engineering, vol. 48; No. 1; 6 pages. [cited by applicant]
Maslov et al. (Mar. 2008) “Quantum Circuit Simplification and Level Compaction,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, No. 3, pp. 436-444. [cited by applicant]
McCaskey et al. (2019) “XACC: A System-Level Software Infrastructure for Heterogeneous Quantum-Classical Computing,” arXiv:1911.02452v1; 17 pages. [cited by applicant]
Nam et al. (Oct. 2017) “Automated Optimization of Large Quantum Circuits with Continuous Parameters,” arXiv:1710.07345v1, College Park, MD; 21 pages. [cited by applicant]
Neukart et al. (Aug. 2017) “Traffic Flow Optimization Using a Quantum Annealer,” Frontiers in ICT; arXiv:1708.01625v2; 12 pages. [cited by applicant]
Nielsen et al. (2011). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, USA, 704 pages. [cited by applicant]
Oskin et al. (Jan. 2002) “A Practical Architecture for Reliable Quantum Computers,” Quantum Computing, pp. 79-87. [cited by applicant]
Papalitsas. (Oct. 2019) “A QUBO Model for The Traveling Salesman Problem with Time Windows,” Algorithms, 12:224; 21 pages. [cited by applicant]
Perdomo-Ortiz et al. (Oct. 2014) “A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems,” arXiv:1406.7601v2; 12 pages. [cited by applicant]
Rieffel et al. (2011) “Quantum Computing: A Gentle Introduction,” The MIT Press, 1st edition; 386 pages. [cited by applicant]
Rieffel et al. (Jul. 2014) “A Case Study in Programming a Quantum Annealer for Hard Operational Planning Problems,” Quantum Information Processing, arXiv:1407.2887v1, 19 pages. [cited by applicant]
Selinger et al. (2010) “Quantum Lambda Calculus,” in Semantic Techniques in Quantum Computation, New York, Cambridge University Press, 46 pages. [cited by applicant]
Shmygelska et al. (Feb. 2005) “An Ant Colony Optimisation Algorithm for The 2d and 3d Hydrophobic Polar Protein Folding Problem,” BMC Bioinformatics 6:30; 22 pages. [cited by applicant]
Smith et al. (Mar. 2020) “An Open-Source, Industrial-Strength Optimizing Compiler for Quantum Programs,” arXiv:2003.13961v1; 29 pages. [cited by applicant]
Svore et al. (2006) “A layered software architecture for quantum computing design tools,” Computer, vol. 39, No. 1, 10 pages. [cited by applicant]
Venturelli et al. (2017) “Compiling Quantum Circuits to Realistic Hardware Architectures Using Temporal Planners,” NASA Ames Research Center; arXiv:1705.08927v2; 31 pages. [cited by applicant]
Yao. (1993) “Quantum Circuit Complexity,” Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science; Nov. 3-5, 1993, Washington, DC, USA, 10 pages. [cited by applicant]
Zheng et al. (Apr. 2020) “DGL-KE: Training Knowledge Graph Embeddings at Scale,” arXiv:2004.08532v1; 11 pages. [cited by applicant]
Zhu et al. (Mar. 2019) “GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding,” arXiv:1903.00757v1; 11 pages. [cited by applicant]