Problem solving using quantum annealer, useful for example in sequencing, for instance nucleic acid sequencing
Quantum annealers as analog or quantum processors can find paths in problem graphs embedded in a hardware graph of the processor, for example finding valid paths, shortest paths or longest paths. A set of input, for example nucleic acid reads, can be used to set up a graph with edges between nodes denoting overlap (i.e., common base pairs) between the reads with constraints applied to perform sequence alignment or sequencing of a nucleic acid (e.g., DNA) strand or sequence, finding a solution that has a ground state energy. At least a portion of the described approaches can be applied to other problems, for instance resource allocations problems, e.g., job scheduling problems, traveling salesperson problems, and other NP-complete problems.
1. A method of problem solving via a quantum annealer, the method comprising:
for a set of a number N READS of nucleic acid reads r, for each nucleic acid read in the set of nucleic acid reads r, finding all other nucleic acid reads in the set of nucleic acid reads that have at least a defined number of base pairs at one end of the other nucleic acid read in common with the defined number of base pairs at one end of the nucleic acid read;
forming a problem graph having a number of rows equal to a defined sequence length l SEQ , each row having a total number of nodes equal to the defined number of base pairs, and where for each pair of nucleic acid reads r j,j that have the defined number of base pairs in common, the problem graph has a respective edge that extends from a node r i in one row to a node r j in a next row in the problem graph;
for each column of the problem graph, asserting a first constraint that either one node or zero nodes in the column are in a ground state;
for each row of the problem graph, asserting a second constraint that exactly one node in the row is in the ground state;
causing the problem graph to be embedded in a hardware graph of the quantum annealer along with the first and the second constraints; and
receiving a result from the quantum annealer after at least one evolution with the problem graph embedded in the hardware graph of the quantum annealer along with the first and the second constraints.
2. The method of claim 1 wherein forming a problem graph includes:
for each row of the problem graph except a last one of the rows in the problem graph, iterating over all pairs of nucleic acid reads r that have the defined number of base pairs in common, and
forming an edge relationship between a node r i in one row to a node r j in a next row in the problem graph.
3. The method of claim 1 wherein finding all other nucleic acid reads in the set of nucleic acid reads that have at least a defined number of base pairs at one end of the other nucleic acid read in common with the defined number of base pairs at one end of the nucleic acid read; includes: finding all other nucleic acid reads in the set of nucleic acid reads that have at least a defined number of base pairs at a first end of the other nucleic acid read in common with the defined number of base pairs at a second end of the nucleic acid read, the second end opposite the first end.
4. The method of claim 1 wherein causing the problem graph to be embedded in a hardware graph of the quantum annealer along with the first and the second constraints includes embedding the problem graph with the first and the second constraints in the hardware graph of an analog processor.
5. The method of claim 1 wherein causing the problem graph to be embedded in a hardware graph of the quantum annealer along with the first and the second constraints includes embedding the problem graph with the first and the second constraints in the hardware graph of a quantum processor.
6. The method of claim 1 wherein the quantum annealer is a quantum processor that comprises a plurality of quantum devices spatially arranged in an interconnected topology and a plurality of coupling devices between pairs of quantum devices, and wherein causing the problem graph to be embedded in a hardware graph of the quantum annealer along with the first and the second constraints includes programming at least a portion of the plurality of quantum devices and the plurality of coupling devices to set an energy function of the quantum processor.
7. The method of claim 6 , further comprising:
initializing the quantum processor to an initial state; and
evolving the quantum processor from the initial state to a final state.
8. The method of claim 7 wherein evolving the quantum processor from the initial state to a final state occurs a plurality of times via at least one of adiabatic evolution, quasi-adiabatic evolution, annealing by temperature, annealing by magnetic field, and annealing of barrier height, until a ground state energy is obtained.
9. The method of claim 1 wherein receiving a result from the quantum annealer includes receiving a result that represents an ordered sequence of nucleotides over a strand of deoxyribose nucleic acid (DNA) or ribose nucleic acid (RNA) of the defined sequence length l SEQ .
10. A system to problem solve, the system comprising:
at least one processor circuit; and
at least one processor-readable medium that stores at least one of processor-executable instructions or data which, when executed by the at least one processor causes the at least one processor to:
form a problem graph having a number of rows equal to a defined sequence length l, each row having a total number of nodes equal to a defined number of base pairs, and where for each pair of DNA reads r j,j that have the defined number of base pairs in common, the problem graph has a respective edge that extends from a node r i in one row to a node r j in a next row in the problem graph;
for each column of the problem graph, assert a first constraint that either one node or zero nodes in the column are in a ground state;
for each row of the problem graph, assert a second constraint that exactly one node in the row is in the ground state;
cause the problem graph to be embedded in a hardware graph of a quantum annealer along with the first and the second constraints; and
receive a result from the quantum annealer after at least one evolution with the problem graph embedded in the hardware graph of the quantum annealer along with the first and the second constraints.
11. A method of finding a path in a graph via a quantum annealer, the method comprising:
forming a problem graph having a number of rows equal to a defined sequence length l SEQ , each row having a total number of nodes equal to a defined number of sequential values, and where for each pair of subsequences r j,j that have the defined number of sequential values in common, the problem graph has a respective edge that extends from a node r i in one row to a node r j in a next row in the problem graph;
for each column of the problem graph, asserting a first constraint that either one node or zero nodes in the column are in a ground state;
for each row of the problem graph, asserting a second constraint that exactly one node in the row is in the ground state;
causing the problem graph to be embedded in a hardware graph of the quantum annealer along with the first and the second constraints; and
receiving a result from the quantum annealer after at least one evolution with the problem graph embedded in the hardware graph of the quantum annealer along with the first and the second constraints.
12. The method of claim 11 wherein forming a problem graph includes:
for each row of the problem graph, except a last one of the rows in the problem graph, iterating over all pairs of pair of subsequences r j,j that have the defined number of sequential values in common, and
forming an edge relationship between a node r i in one row to a node r j in a next row in the problem graph.
13. The method of claim 11 wherein causing the problem graph to be embedded in a hardware graph of the quantum annealer along with the first and the second constraints includes embedding the problem graph with the first and the second constraints in the hardware graph of a quantum processor.
14. The method of claim 11 wherein the quantum annealer is a quantum processor that comprises a plurality of quantum devices spatially arranged in an interconnected topology and a plurality of coupling devices between pairs of quantum devices, and wherein causing the problem graph to be embedded in a hardware graph of the quantum annealer along with the first and the second constraints includes programming at least a portion of the plurality of quantum devices and the plurality of coupling devices to set an energy function of the quantum processor.
15. The method of claim 14 , further comprising:
initializing the quantum processor to an initial state; and
evolving the quantum processor from the initial state to a final state.
16. The method of claim 15 wherein evolving the quantum processor from the initial state to a final state occurs a plurality of times via at least one of adiabatic evolution, quasi-adiabatic evolution, annealing by temperature, annealing by magnetic field, and annealing of barrier height, until a ground state energy is obtained.
17. The method of claim 16 , further comprising:
determining whether a ground state energy was obtained at the final state of the evolution.
18. The method of claim 11 wherein forming a problem graph includes forming the problem graph having a number of rows equal to a defined sequence length l SEQ of a strand of nucleic acid, each row having a total number of nodes equal to a defined number of sequential base pairs, and where for each pair of subsequences r j,j that have the defined number of sequential base pairs in common, the problem graph has a respective edge that extends from the node r i in one row to the node r j in the next row in the problem graph.
19. The method of claim 18 , further comprising:
finding all other nucleic acid reads in the set of nucleic acid reads that have at least a defined number of base pairs at one end of the other nucleic acid read in common with the defined number of base pairs at one end of the nucleic acid read.
20. The method of claim 19 wherein finding all other nucleic acid reads in the set of nucleic acid reads that have at least a defined number of base pairs at one end of the other nucleic acid read in common with the defined number of base pairs at one end of the nucleic acid read includes: finding all other nucleic acid reads in the set of nucleic acid reads that have at least a defined number of base pairs at a first end of the other nucleic acid read in common with the defined number of base pairs at a second end of the nucleic acid read, the second end opposite the first end.