Quantum Computing
Brian S. Haney
Copyright Martian Technologies 2019
Quantum mechanics is the scientific discipline concerned with the motion and interaction of sub-atomic particles. The past 50 years have yielded exponential gains in the volume of software. Yet, arguably the greatest technical innovation in that period occurred during the early part of the twenty-first century in the evolution of computational hardware. Quantum computing refers to a machine modeling the principles of quantum mechanics during the computational process. In 2006, D-Wave, was awarded U.S. Patent № 7,418,283, Adiabatic quantum computation with superconducting qubits, which serves as the foundation of quantum computational architectures today.
Figure 15 represents a system allowing remote access to the quantum computer and its qubit control system. Eleanor Rieffel, the head of NASA’s Quantum AI Lab, argues the fundamental unit of computation is no longer the bit, but rather the quantum bit — qubit. The qubit is the fundemental innovation of the quantum computer. Rather than processing information in binary, as a 0 or 1, the quantum computer processes information in superposition, modeling quantum properties. In short, a qubit is a processing unit modeling a vector space as opposed to a Boolean value.
The qubit allows for faster computing and less electrical power consumption compared to its classical counterpart. The development and functioning of the qubit is dependent upon a novel hardware architecture.
Hardware
D-Wave machines are roughly eleven feet tall, with a door for scientists to enter. From the outside, the machines can be heard making a thumping sound, often described as eerily similar to a heartbeat.
The Machine uses liquid nitrogen and liquid helium to cool a specialized quantum chip to 0.015 Kelvin, a temperature 175x colder than interstellar space. Instead of using Silicon like traditional computer chips, the quantum chip uses a metal called Niobium.
The chip contains 2048 qubits in a 16x16 cell matrix, with 8 bits per cell. The Niobium is looped throughout the chip, connecting the qubits and acting as a superconducting metal where each loop models a quantum spin. This novel architecture supports a binary programming model. And, when cooled to the near zero Kelvin temperature at which it is stored, the chip becomes a superconductor, a metal with properties including zero electrical resistance and magnetic flux fields. This allows the chip to exhibit quantum mechanical effects and to eliminate noise during the computational process.
Ising Model
The D-Wave systems are based on the Ising Model. The Ising Model is traditionally used in statistical mechanics, where variables are binary and the relationship between variables is represented by couplings. Additionally, the Ising Model, uses a Hamiltonian energy measurement function to describe the total amount of energy is a quantum system. The input of the Hamiltonian function is the state of the system. And, the output is the energy measurement of the system.
The Ising Model is the foundation of the D-Wave system. In addition to the Ising Model, the second essential element of the D-Wave system is a traverse magnetic field, which can be manipulated to solve optimization problems.
During the annealing process, each qubit begins in a state of superposition encoded in a circular magnetic field. Then, a barrier is raised and a magnetic field is applied to the qubits. As the magnetic field is applied, each qubit moves toward a classical state, ending as a 0 or 1. The qubits minimize their energy in the presence of the magnetic field, according to a bias. Additionally, links between qubits, called couplers, allow for the resulting states of multiple qubits to effect one another. This article will proceed by explaining three specific types of problems the system can solve: Quadratic Unconstrained Binary Optimization (QUBO) Problems, Minimum Vertex Cover Problems, and Factoring Problems.
QUBO
QUBOs use binary variables to solve optimization problems. QUBO problems have state variables TRUE and FALSE, corresponding to 1 and 0 values. A QUBO problem is defined using an upper-diagonal matrix Q, which is an N x N upper-triangular matrix of real weights x, and a vector of binary variables, minimizing the function:
The diagonal terms are the linear coefficients and the non-zero off-diagonal terms are the quadratic coefficients. This can be expressed more concisely:
Underpinning the success of QUBO models is the concept of magnetism in materials, which stems from the near zero Kelvin state of the quantum chip.
Code
Dimod is a module for binary quadratic samplers. Dimod provides a binary quadratic model (BQM) class containing Ising and QUBO optimization models. The models are used to process information on the quantum computer. Additionally, Dimod also provides utilities for constructing quantum state samplers.
#Import dimodimport dimod#Exact solver finds energies for all states.exactsolver = dimod.ExactSolver()#Set up the QUBO.
#Embedding explicitly expressed, with chainstrength variable.#Chainstrength variablechainstrength = 1#Define Q-MatrixQ = {(0, 0): 2, (1, 1): chainstrength, (5, 5): chainstrength, (0, 4): -2, (1, 4): 2, (0, 5): -2, (1, 5): -2 * chainstrength}#Define results
results = exactsolver.sample_qubo(Q)#For loop to print results.for smpl, energy in results.data(['sample', 'energy']):
print(smpl, energy)Minimum Vertex Cover
The code returns the following:
The return represents the energies for all states, solving the BQM.
Vertex Cover
A vertex cover is a set of vertices such that each edge of a graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is an example of an NP-hard optimization problem.
The solution may be formatted onto the quantum computer such that nodes are points on the network and edges are paths by which information flows.
Code
D-Wave’s dwave_networkx is an extension of NetworkX — a Python language package for analysis of networks and network algorithms. The dwave_networkx package includes tools for working with Chimera graphs and implementations of graph-theory algorithms.
#Step one: Draw a single graph#Imports include numpy, matplotlib, and networkx
import networkx as nx
import matplotlib
import matplotlib.pyplot as plt
import numpy as np
import matplotlib.pyplot as plta5 = nx.star_graph(4)
plt.subplot(121)nx.draw(a5, with_labels=True, front_weight=’bold’)#Step two: Solve the graphs minimum vertex coverfrom dwave.system.samplers import DWaveSampler
from dwave.system.composites import EmbeddingComposite#Define sampler
sampler = EmbeddingComposite(DWaveSampler())
print(dnx.min_vertex_cover(a5, sampler))
The code outputs the following:
The model represents the minimum vertex cover of the graph.
Factoring
One of the most interesting utilities of the quantum computer is its ability to factor numbers. In short, integer factoring is the process of finding numbers that when multiplied provide a target number. For example, the factors of 21 are 3 and 7. Factoring large numbers can be extremely time consuming for computers.
Indeed, factoring serves as a basis for public-key cryptography systems, like RSA. Factoring is also the basis of the SHA-256 algorithm, which is used for cryptocurrencies like Bitcoin. The quantum computer is able to solve factoring problems faster than classical computers by processing the problem as a constraint satisfaction problem. Constraint satisfaction problems (CSPs) assign values to problem variables, resulting in the satisfaction of constraints.
A minimization function may then be defined:
The minimization function allows the machine to satisfy the problems constraints.
Code
Step one is to set an integer to factor. Here, the number is 21.
#Set an integer to factorP = 21#Binary representation of P bP = "{:06b}".format(P)
print(bP)
Next, the problem is converted to a Binary Quadratic Model (BQM).
#Convert the CSP into BQMcsp = dbc.factories.multiplication_circuit(3)
bqm = dbc.stitch(csp, min_classical_gap=.1)
The next two lines create a visualization of the BQM. Each node of the graph represents a variable and the multiplication circuits’ internal variables.
from helpers import draw
draw.circuit_from(bqm)
The D-Wave system factors integers by running a multiplication circuit in reverse. The next step modifies the BQM, removing known variables and updating neighboring values.
#Create variablesp_vars = ['p0', 'p1', 'p2', 'p3', 'p4', 'p5']#Convert P from decimal to binaryfixed_variables = dict(zip(reversed(p_vars), "{:06b}".format(P)))
fixed_variables = {var: int(x) for(var, x) in fixed_variables.items()}#Fix product variablesfor var, value in fixed_variables.items():
bqm.fix_variable(var, value)#Confirm that a P variable has been removed from the BQMprint("Variable p0 in BQM: ", 'p0' in bqm)
print("Variable a0 in BQM: ", 'a0' in bqm)
Then, the Quantum Computer solves the BQM, finding variable assignments that produce its lowest values. To accomplish this goal, a solver is used from D-Wave’s Ocean software stack.
from helpers.solvers import default_solver
my_solver, my_token = default_solver()from dwave.system.samplers import DWaveSampler#Samplersampler = DWaveSampler(solver={'qpu': True}) from dwave.embedding import embed_bqm, unembed_sampleset
from helpers.embedding import embeddings#Set a pre-calculated minor-embedingembedding = embeddings[sampler.solver.id]
bqm_embedded = embed_bqm(bqm, embedding, target_adjacency, 3.0)
The problem is embedded onto the QPU.
#Return num_reads solutionskwargs = {}
if 'num_reads' in sampler.parameters:
kwargs['num_reads'] = 50
if 'answer_mode' in sampler.parameters:
kwargs['answer_mode'] = 'histogram'
response = sampler.sample(bqm_embedded, **kwargs)
Finally, the solution is returned.
#Map back to the BQM's graphresponse = unembed_sampleset(response, embedding, source_bqm=bqm)from helpers.convert import to_base_ten#Select the first sample. sample = next(response.samples(n=1))
dict(sample)
a, b = to_base_ten(sample)print("Given integer P={}, found factors a={} and b={}".format(P, a, b))
Here, the quantum computer returns the factors of 21, 7 and 3.
Conclusion
The future for quantum computing appears bright. Indeed, in 2016 D-Wave was awarded U.S. Patent № 9,400,499, Systems and Methods for Real-Time Quantum Computer-Based Control of Mobile Systems.
The impacts of quantum computing for real world robotics control, cryptocurrency mining, and network security demonstrate its potential to have wide-spread economic impacts. Indeed, the potential for quantum speedup and more efficient computational consumption of electric power are both benefits of quantum computing.
Appendix A. Summary of Notation
Appendix B. References
[1] Eleanor Rieffel, Wolfgang Polak, Quantum Computing (The MIT Press 2014).
[2] Adiabatic Quantum Computation with Superconducting Qubits, U.S. Patent № 7,135,701 to Amin et al. (Nov. 14, 2006).
[3]Systems and Methods for Real-Time Quantum Computer-Based Control of Mobile Systems, U.S. Patent № 9,400,499 to Williams, et al. (Jul. 26, 2016).
[4] Factoring, D-Wave, Leap (2018) https://cloud.dwavesys.com/leap/demos/factoring/intro.
[5] D-Wave, System Documentation(2018) https://docs.dwavesys.com/docs/latest/index.html.
[6] Leonard Susskind & Art Friedman, Quantum Mechanics (Basic Books 2014).
[7] Murray Shanahan, The Technological Singularity (MIT Press 2015).
