Processing relational database problems using analog processors

• US 8,032,474 B2
• Filed: 11/15/2010
• Issued: 10/04/2011
• Est. Priority Date: 11/02/2006
• Status: Active Grant

• Current Assignee: D-Wave Systems Inc. (D-Wave Quantum, Inc.)
• Original Assignee: D-Wave Systems Inc. (D-Wave Quantum, Inc.)
• Inventors: Macready, William G., Coury, Michael D., Sham, Ivan King Yu
• Primary Examiner(s): Holmes; Michael B
• Application Number:
  US12/946,643
• Publication Number:
  US 20110060711A1
• Time in Patent Office: 323 Days
• Field of Search: 706/46
• US Class Current: 706/46
• CPC Class Codes: B82Y 10/00 Nanotechnology for information processing, storage or transmission, e.g. quantum computing or single electron logic
• CPC Class Codes: G06N 10/00 Quantum computing, i.e. information processing based on quantum-mechanical phenomena

Abstract

Systems, methods and articles solve queries or database problems through the use of graphs. An association graph may be formed based on a query graph and a database graph. The association graph may be solved for a clique, providing the results to a query or problem and/or an indication of a level of responsiveness of the results. Thus, unlimited relaxation of constraint may be achieved. Analog processors such as quantum processors may be used to solve for the clique.

Claims

1. A method of obtaining an answer to a query from a database, the method comprising:

determining a query graph representative of the query via at least one processor;

determining a first database graph representative of a first portion of information stored in the database via at least one processor;

determining a first association graph based on the query graph and the first database graph via at least one processor;

determining at least one characteristic of the first association graph via a quantum processor;

storing information relating to the at least one characteristic of the first association graph in a computer-readable medium;

determining a second database graph representative of a second portion of information stored in the database via at least one processor;

determining a second association graph based on the query graph and the second database graph via at least one processor;

determining at least one characteristic of the second association graph via the quantum processor;

storing information relating to the at least one characteristic of the second association graph in the computer-readable medium; and

ranking the at least one characteristic of the second association graph with respect to the at least one characteristic of the first association graph via a digital processor.

2. The method of claim 1 wherein determining at least one characteristic of the first association graph via a quantum processor includes determining a clique of the first association graph via the quantum processor, and wherein determining at least one characteristic of the second association graph via the quantum processor includes determining a clique of the second association graph via the quantum processor.

3. The method of claim 2 wherein determining a clique of the first association graph via the quantum processor includes determining a maximum clique of the first association graph via the quantum processor, and wherein determining a clique of the second association graph via the quantum processor includes determining a maximum clique of the second association graph via the quantum processor.

4. The method of claim 2, further comprising:

returning an answer to the query from the digital processor based on ranking a size of the clique of the second association graph with respect to a size of the clique of the first association graph.

5. The method of claim 1 wherein determining at least one characteristic of the first association graph via a quantum processor includes determining an independent set of the first association graph via the quantum processor, and wherein determining at least one characteristic of the second association graph via the quantum processor includes determining an independent set of the second association graph via the quantum processor.

6. The method of claim 5 wherein determining an independent set of the first association graph via the quantum processor includes determining a maximum independent set of the first association graph via the quantum processor, and wherein determining an independent set of the second association graph via the quantum processor includes determining a maximum independent set of the second association graph via the quantum processor.

7. The method of claim 5, further comprising:

returning an answer to the query from the digital processor based on ranking a size of the independent set of the second association graph with respect to a size of the independent set of the first association graph.

8. The method of claim 1 wherein determining at least one characteristic of the first association graph via a quantum processor includes embedding the first association graph into the quantum processor, and wherein determining at least one characteristic of the second association graph via the quantum processor includes embedding the second association graph into the quantum processor.

9. The method of claim 8 wherein determining at least one characteristic of the first association graph via a quantum processor includes evolving the quantum processor to a final state representative of at least one characteristic of the first association graph, and wherein determining at least one characteristic of the second association graph via the quantum processor includes evolving the quantum processor to a final state representative of at least one characteristic of the second association graph.

10. The method of claim 1 wherein determining a query graph representative of the query via at least one processor includes converting a number of elements of information into a number of labeled nodes of a graph by the at least one processor, and converting a number of relations between the elements of information into a number of labeled edges between pairs of nodes of the graph by the at least one processor.

11. The method of claim 10 wherein converting a number of relations between the elements of information into a number of labeled edges between pairs of the nodes of the graph by the at least one processor includes converting the number of relations between the elements of information into a number of directed edges between pairs of nodes of the graph by the at least one processor.

12. The method of claim 1 wherein determining a first association graph based on the query graph and the first database graph via at least one processor includes, for all of a number of pairwise combinations of association vertices in the first association graph, forming an edge between the association vertices in the first association graph by the at least one processor only if a respective pair of vertices in the query graph that the association vertices represent exhibit a same relation as a corresponding pair of vertices in the first database graph that the association vertices represent, and wherein determining a second association graph based on the query graph and the second database graph via at least one processor includes, for all of a number of pairwise combinations of association vertices in the second association graph, forming an edge between the association vertices in the second association graph by the at least one processor only if a respective pair of vertices in the query graph that the association vertices represent exhibit a same relation as a corresponding pair of vertices in the second database graph that the association vertices represent.

13. The method of claim 1 wherein determining at least one characteristic of the first association graph via a quantum processor includes using the quantum processor to solve a first optimization problem, and wherein determining at least one characteristic of the second association graph via the quantum processor includes using the quantum processor to solve a second optimization problem.

14. The method of claim 1, further comprising:

determining at least one additional database graph representative of at least one additional portion of information stored in the database via at least one processor;

determining at least one additional association graph based on the query graph and the at least one additional database graph via at least one processor;

determining at least one characteristic of the at least one additional association graph via the quantum processor;

storing information relating to the at least one characteristic of the at least one additional association graph in the computer-readable medium; and

ranking the at least one characteristic of the at least one additional association graph with respect to the at least one characteristic of the second association graph and the at least one characteristic of the first association graph via a digital processor.

15. The method of claim 14, further comprising:

returning an answer to the query from the digital processor based on ranking the at least one characteristic of the at least one additional association graph with respect to the at least one characteristic of the second association graph and the at least one characteristic of the first association graph via the digital processor.