This example solves a logic-circuit problem on a D-Wave quantum computer. It expands on the discussion in the and example about the effect of minor-embedding on performance, demonstrating different approaches to embedding.
To run the code in this example, the following is required.
- The requisite information for problem submission through SAPI, as described in
sapi_access - Ocean tools
dimod </docs_dimod/sdk_index>anddwave-system </docs_system/sdk_index>. For the optional graphics, you will also needproblem-inspector </docs_inspector/sdk_index>.
Other examples (not and and) show how a Boolean gate is represented as a constraint satisfaction problem (CSP) on a quantum computer. This example aggregates the resulting binary quadratic models (BQM) to do the same for multiple gates that constitute a circuit.
To start with, solve the circuit with 7 logic gates shown above.
The code below represents standard Boolean gates with BQMs provided by dimod </docs_dimod/sdk_index> BQM generators, represents the Boolean NOT operation by inverting the coefficients of the relevant variables, and sums the gate-level BQMs. The resulting aggregate BQM has its lowest value for variable assignments that satisfy all the constraints representing the circuit's Boolean gates.
>>> from dimod.generators import and_gate, or_gate ... >>> bqm_gate2 = or_gate('b', 'c', 'out2') >>> bqm_gate3 = and_gate('a', 'b', 'out3') >>> bqm_gate3.flip_variable('b') >>> bqm_gate4 = or_gate('out2', 'd', 'out4') >>> bqm_gate5 = and_gate('out3', 'out4', 'out5') >>> bqm_gate7 = or_gate('out5', 'out4', 'z') >>> bqm_gate7.flip_variable('out4') ... >>> bqm = bqm_gate2 + bqm_gate3 + bqm_gate4 + bqm_gate5 + bqm_gate7 >>> print(bqm.num_variables) 9
This circuit is small enough to solve with a brute-force algorithm such as that used by the ~dimod.reference.samplers.ExactSolver class. Solve and print all feasible solutions.
>>> from dimod import ExactSolver, drop_variables ... >>> solutions = ExactSolver().sample(bqm).lowest() >>> out_fields = [key for key in list(next(solutions.data(['sample'])))[0].keys() if 'out' in key] >>> print(drop_variables(solutions, out_fields)) a b c d z energy num_oc. 0 0 0 0 1 0 0.0 1 1 0 0 1 1 0 0.0 1 2 0 1 1 1 0 0.0 1 3 0 1 0 1 0 0.0 1 4 1 1 0 1 0 0.0 1 5 1 1 1 1 0 0.0 1 6 1 1 1 0 0 0.0 1 7 1 1 0 0 0 0.0 1 8 0 1 0 0 0 0.0 1 9 0 1 1 0 0 0.0 1 10 0 0 1 0 0 0.0 1 11 1 0 0 1 1 0.0 1 12 1 0 1 1 1 0.0 1 13 1 0 1 0 1 0.0 1 14 1 0 0 0 1 0.0 1 15 0 0 0 0 1 0.0 1 ['BINARY', 16 rows, 16 samples, 5 variables]
Brute-force algorithms are not effective for large problems.
In the figure below, the 7-gates circuit solved above is replicated with the outputs connected through a series of XOR gates.
The circuit_bqm function defined below replicates, for a specified number of circuits, the BQM developed above and connects the outputs through a cascade of XOR gates.
>>> from dimod import BinaryQuadraticModel, quicksum >>> from dimod.generators import and_gate, or_gate, xor_gate ... >>> def circuit_bqm(n: int = 3) -> BinaryQuadraticModel: ... "Create a BQM for n replications of the 7-gate circuit." ... ... if n < 2: ... raise ValueError("n must be at least 2") ... ... bqm_gate2 = [or_gate(f"b{c}", f"c{c}", f"out2{c}") for c in range(n)] ... bqm_gate3 = [and_gate(f"a{c}", f"b{c}", f"out3{c}") for c in range(n)] ... [bqm.flip_variable("b{}".format(indx)) for indx, bqm in enumerate(bqm_gate3)] ... bqm_gate4 = [or_gate(f"out2{c}", f"d{c}", f"out4{c}") for c in range(n)] ... bqm_gate5 = [and_gate(f"out3{c}", f"out4{c}", f"out5{c}") for c in range(n)] ... bqm_gate7 = [or_gate(f"out5{c}", f"out4{c}", f"z{c}") for c in range(n)] ... [bqm.flip_variable("out4{}".format(indx)) for indx, bqm in enumerate(bqm_gate7)] ... bqm_z = [xor_gate("z_0", "z_1", "zz0", "aux0")] + [ ... xor_gate(f"z{c}", f"zz{c-2}", f"zz{c-1}", f"aux{c-1}") for c in range(2, n)] ... return quicksum(bqm_gate2 + bqm_gate3 + bqm_gate4 + bqm_gate5 + bqm_gate7 + bqm_z)
Instantiate a BQM for six replications. The resulting circuit has 64 variables.
>>> bqm = circuit_bqm(6) >>> print(bqm.num_variables) 64
The and example used the ~dwave.system.composites.EmbeddingComposite composite to minor-embed its unstructured problem onto the topology of a quantum computer's qubits and couplers. That composite uses the minorminer algorithm <sdk_index_minorminer> to find a minor embedding for each problem you submit.
For some applications, the submitted problems might be related or limited in size in such a way that you can find a common minor embedding for the entire set of problems. For instance, you might wish to submit the circuit of this example multiple times with various configurations of fixed inputs (inputs set to zero or one).
One approach is to pre-calculate a minor embedding for a clique (a complete graph), a "clique embedding", of a size at least equal to the maximum number of variables (nodes) expected in your problem. Because any BQM of n variables maps to a subgraph of an n--node clique1, you can then use the clique embedding by assigning to all unused nodes and edges a value of zero.
Configure a quantum computer as a sampler using both the ~dwave.system.composites.EmbeddingComposite composed sampler, for standard embedding, and the ~dwave.system.samplers.DWaveCliqueSampler composed sampler, for clique embedding.
>>> from dwave.system import DWaveSampler, EmbeddingComposite, DWaveCliqueSampler ... >>> sampler1 = EmbeddingComposite(DWaveSampler(solver=dict(topology__type='pegasus'))) >>> sampler2 = DWaveCliqueSampler(solver=dict(name=sampler1.child.solver.name)) # doctest: +SKIP
The ~dwave.system.samplers.DWaveCliqueSampler composed sampler reduces the overhead of repeatedly finding minor embeddings for applications that submit a sequence of problems that are all sub-graphs of a clique that can be embedded on the QPU sampling the problems.
The table below shows the minor-embedding times2 for a series of random problems of increasing size3. Some interesting differences are bolded.
Note
The times below are for a particular development environment. Embedding times can be expected to vary for different CPUs, operating systems, etc as well as varying across problems and executions of the heuristic algorithm.
| Problem Size: Nodes (Edges/Node) | ~dwave.system.composites.EmbeddingComposite Time [sec] |
~dwave.system.samplers.DWaveCliqueSampler Time [sec] |
Notes |
|---|---|---|---|
| 10 (5) | 0.06 | 152.7 | ~dwave.system.samplers.DWaveCliqueSampler calculates all clique embeddings for the QPU. |
| 20 (10) | 0.41 | 0.11 | |
| 30 (15) | 1.39 | 0.11 | |
| 40 (20) | 3.88 | 0.13 | |
| 50 (25) | 9.7 | 0.14 | |
| 60 (30) | 17.91 | 0.16 | |
| 70 (35) | 22.02 | 0.19 | |
| 80 (40) | 73.74 | 0.25 | |
| 90 (45) | 65.05 | 0.22 | |
| 100 (50) | 28.92 | 0.25 | For this execution, ~dwave.system.composites.EmbeddingComposite found a good embedding quickly; other executions might not. |
You can see that while the first submission is slow for the ~dwave.system.samplers.DWaveCliqueSampler composed sampler, subsequent submissions are fast. For the ~dwave.system.composites.EmbeddingComposite composed sampler, the time depends on the size and complexity of each problem, can vary between submissions of the same problem, and each submission incurs the cost of finding an embedding anew.
For example, to submit a problem with two replications of the
>>> bqm1 = circuit_bqm(2) >>> bqm2 = bqm1.copy(bqm1) >>> bqm1.fix_variables([('b_0', 0), ('b_1', 0), ('a_0', 1)]) >>> bqm2.fix_variables([('b_0', 1), ('b_1', 1), ('a_0', 0)]) ... >>> bqms = [bqm1, bqm2] >>> times = {key: [] for key in samplers.keys()} # doctest: +SKIP >>> for name, sampler in samplers.items(): # doctest: +SKIP ... for i, bqm in enumerate(bqms): ... times[name].append(time.time()) ... sampler.sample(bqm, num_reads=5000) ... times[name][i] = time.time() - times[name][i] >>> times # doctest: +SKIP {'sampler1': [0.43480920791625977, 0.381976842880249], 'sampler2': [0.12912440299987793, 0.12194108963012695]}
If, however, you wish to submit a problem with ten replications repeatedly, with some subset of the variables fixed, the overhead cost of embedding can be minutes.
The ~dwave.system.composites.EmbeddingComposite composed sampler attempts to find a good embedding for any given problem while the ~dwave.system.samplers.DWaveCliqueSampler reuses a clique embedding found once. Typically the former results in an embedding with shorter chains than the latter, with the difference in length increasing for larger problems. Chain length can significantly affect solution quality.
The table below compares, for the two embedding methods, the ratio of ground states (solutions for which the value of the BQM is zero, meaning no constraint is violated or all assignments of values to the problem's variables match valid states of the circuit represented by the BQM) to total samples returned from the quantum computer when minor-embedding a sequence of problems of increasing size.
The results are for one particular code4 execution on problems that replicate the
| Problem Size: Circuit Replications | ~dwave.system.composites.EmbeddingComposite Ground-State Ratio [%] |
~dwave.system.samplers.DWaveCliqueSampler Ground-State Ratio [%] |
|---|---|---|
| 2 | 69.6 | 74.4 |
| 3 | 52.6 | 25.2 |
| 4 | 40.5 | 16.8 |
| 5 | 29.1 | 3.3 |
| 6 | 20.9 | 2.9 |
| 7 | 16.3 | 0.2 |
| 8 | 14.4 | 0.0 |
| 9 | 8.9 | 0.0 |
| 10 | 7.2 | 0.3 |
You can see that for small problems, using a clique embedding can produce high-quality solutions, and might be advantageously used when submitting a sequence of related problems.
Ocean's problem-inspector </docs_inspector/sdk_index> can illuminate differences in solution quality between alternative minor embeddings. You can use it to visualize sample sets returned from a quantum computer in your browser.
>>> import dwave.inspector >>> bqm = circuit_bqm(2) >>> sampleset1 = sampler1.sample(bqm, num_reads=5000) >>> dwave.inspector.show(sampleset1) # doctest: +SKIP
The figure below, constituted of snapshots from the problem inspector for submissions to the two samplers defined above, shows that for the BQM representing two replications of the
Short chains of a few qubits generally enable good quality solutions: as shown in the table above, for a two-replications circuit the ratio of ground states is similar for both embedding methods.
The BQM representing ten replications of the
>>> bqm = circuit_bqm(10) >>> for sampler in samplers.values(): # doctest: +SKIP ... sampleset = sampler.sample(bqm, num_reads=5000, return_embedding=True) ... chain_len = max(len(x) for x in sampleset.info["embedding_context"]["embedding"].values()) ... print("Maximum chain length: {}".format(chain_len)) # doctest: +SKIP ... dwave.inspector.show(sampleset) Maximum chain length: 2 Maximum chain length: 11
The inspector_graph_partitioning example demonstrates how the problem inspector can be used to analyze your problem submissions.
Algorithmic minor embedding is heuristic: solution results can vary significantly based on the minor embedding found.
The table below compares, for a single random ~dimod.generators.ran_r problem of a given size, the ratio of ground states to total samples returned from the quantum computer over several executions5 of minor embedding. The outlier results are bolded.
For each run, the ~dwave.system.composites.EmbeddingComposite composed sampler finds and returns a minor embedding for the problem. The returned embedding is then reused twice by a ~dwave.system.composites.FixedEmbeddingComposite composed sampler.
| Execution | Ground-State Ratio [%] | Chain Length |
|---|---|---|
| 1 | 10.1, 10.1, 8.9 | 4 |
| 2 | 25.8, 29.1, 28.4 | 4 |
| 3 | 24.9, 24.4, 27.9 | 3 |
| 4 | 14.0, 11.0, 13.6 | 3 |
| 5 | 38.5, 36.4, 34.5 | 4 |
| 6 | 15.4, 14.6, 14.5 | 4 |
| 7 | 43.8, 44.2, 45.1 | 3 |
| 8 | 15.9, 17.2, 15.3 | 4 |
| 9 | 31.1, 34.1, 27.1 | 3 |
| 10 | 15.3, 11.5, 12.1 | 3 |
You can see that each set of three submission of the problem using the same embedding have minor variations in the ground-state ratios. However, the variation across minor-embeddings of the same problem can be significant. Consequently, for some applications it can be beneficial to run the minor-embedding multiple times and select the best embedding.
The figure below illustrates such subgraphs. Two random
~networkx.generators.random_graphs.random_regular_graphgraphs with four and three nodes, respectively, each with two edges per node, are plotted on a background of a 5-node clique.The times are approximate: the code measures the blocking time when submitting problems, of which minor-embedding is the major element.↩
The code below can take several minutes to run. Uncommenting the print statement lets you view the execution's progress. Note that if you have already used
~dwave.system.samplers.DWaveCliqueSampler, your cache might need to be cleared with theminorminer.busclique.busgraph_cache.clear_all_cachesfunction to measure the initial calculation time.>>> import time >>> import networkx as nx ... >>> samplers = {"sampler1": sampler1, "sampler2": sampler2} # doctest: +SKIP >>> times = {key: [] for key in samplers.keys()} # doctest: +SKIP >>> for name, sampler in samplers.items(): # doctest: +SKIP ... for i in range(10): ... nodes = 10 + 10*i ... edges = 5 + 5*i ... G = nx.random_regular_graph(n=nodes, d=edges) ... # print("Submitting problem of {} nodes and {} edges to sampler {}".format(nodes, edges, name)) ... times[name].append(time.time()) ... sampler.sample_ising({}, {edge: 1 for edge in G.edges}) ... times[name][i] = time.time() - times[name][i]↩
The code below can take minutes to run. Uncommenting the print statements lets you view the execution's progress.
>>> samplers = {"sampler1": sampler1, "sampler2": sampler2} # doctest: +SKIP >>> samplesets = {key: [] for key in samplers.keys()} # doctest: +SKIP >>> for num_circuits in range(2, 11): ... bqm = circuit_bqm(num_circuits) ... for name, sampler in samplers.items(): # doctest: +SKIP ... # print("Submitting problem of {} circuits to sampler {}".format(num_circuits, name)) ... sampleset = sampler.sample(bqm, num_reads=5000) ... if sampleset.first.energy > 0: ... samplesets[name].append(0) ... else: ... samplesets[name].append(sum(sampleset.lowest().record.num_occurrences))↩
The code below can take minutes to run. Uncommenting the print statements lets you view the execution's progress.
>>> from dimod.generators import ran_r >>> from dwave.system import DWaveSampler, EmbeddingComposite, FixedEmbeddingComposite ... >>> problem_size = 20 >>> num_problems = 10 >>> submission_repeats = 2 >>> qpu = DWaveSampler(solver=dict(topology__type='pegasus')) >>> sampler1 = EmbeddingComposite(qpu) >>> bqm = ran_r(10, problem_size) ... >>> samplesets = {} >>> chain_len = [] >>> for runs in range(num_problems): ... samplesets[runs] = [] ... print("Run {}".format(runs)) ... sampleset = sampler1.sample(bqm, num_reads=5000, return_embedding=True) ... if sampleset.first.energy > 0: ... samplesets[runs].append(0) ... else: ... samplesets[runs].append(sum(sampleset.lowest().record.num_occurrences)) ... embedding = sampleset.info["embedding_context"]["embedding"] # doctest: +SKIP ... chain_len.append(max(len(x) for x in embedding.values())) # doctest: +SKIP ... sampler2 = FixedEmbeddingComposite(qpu, embedding=embedding) # doctest: +SKIP ... ... for i in range(submission_repeats): ... print("tSubmitting {}--{}".format(runs, i)) ... sampleset = sampler2.sample(bqm, num_reads=5000, return_embedding=True) # doctest: +SKIP ... if sampleset.first.energy > 0: # doctest: +SKIP ... samplesets[runs].append(0) ... else: ... samplesets[runs].append(sum(sampleset.lowest().record.num_occurrences))↩
