This week I decided to cover Deutsch's algorithm. Deutsch's algorithm is a simple demonstration of quantum parallelism and interference. So first, let me explain quantum parallelism and interference.
Quantum parallelism
Quantum parallelism is the ability for quantum memory to exist in a superposition of states. So this means that any bit or qubit of memory can simultaneously be a 1 or a 0. This allows for faster calculations to complex problems since the entire range of variables can be tested at the same time. This, however, results in multiple outputs of what the solution could be. These outputs are attached to a probability of how correct the answer is. One of the main uses of Deutsch's algorithm is to simulate this issue and output an answer.
Quantum Interference
Quantum interference is a result of superposition. In quantum computers, this allows for a collapse of the multiple states into probabilities of the desired outcome. Then using an algorithm, similar to the one explained later in this article, the solution can easily be determined from these variables.
What is Deutsch's Algorithm
Deutsch's Algorithm was created by David Deutsch and Richard Jozsa in 1992 as a simple example of how quantum computers could easily outperform a standard computer. The algorithm determines whether a function is balanced or constant based on two separate inputs. If these inputs are the same the function returns a zero otherwise it returns a one. To solve this function using a classical computer both inputs must be examined separately but using a quantum computer this can be done simultaneously due to the properties explained in the first two sections.
Ok So How to Put this in code
To translate this into code first we must import random, cirq, and to make our lives easier directly import some of cirq's methods
import random
import cirq
from cirq import H, X, CNOT, measure
Then we must create two helper functions. The first function makes the oracle, which will determine what each number is and then return circuit moments based on this number. Then the other creates the circuit which we will use towards the end of the main function.
def make_oracle(q0, q1, secret_numbers):
if secret_numbers[0]:
yield[CNOT(q0,q1), X(q1)]
#if the first number is 1 yield
#CNOT gate and X gate moments
if secret_numbers[1]:
yield CNOT(q0, q1)
#if the second number
#is 1 yield CNOT gate
def make_circuit(q0, q1, oracle):
c = cirq.Circuit()
c.append([X(q1), H(q1), H(q0)])
#append X gate and
#two H gates to the circuit
c.append(oracle)
#append oracle to circuit
c.append([H(q0), measure(q0, key='result')])
#append H gate on first qubit
#and then a mesure function to determine the output.
return c
Now since this is done, all that is left is to create two LineQubits, create a list of random numbers, call our helper functions, and then run them through a simulator.
def main():
q0, q1 = cirq.LineQubit.range(2)
#create 2 qubits
secret_numbers = [random.randint(0,1) for i in range(2)]
#create list of two numbers
oracle = make_oracle(q0, q1, secret_numbers)
#create oracle moment to process
#the numbers in the list
print('Secret function:\nf(x) = <{}>'.format(', '.join(str(e) for e in secret_numbers)))
#print out list numbers
circuit = make_deutsch_circuit(q0,q1, oracle)
#create circuit
print("Circuit:")
print(circuit)
#print it out
simulator = cirq.Simulator()
#create simulator
result = simulator.run(circuit)
#run circuit through simulator
print('Result of f(0)⊕f(1):')
print(result) #print result
if __name__ == '__main__':
main()
This is a simple application of quantum computers and in the future, I will post some more complicated examples. I recommend you run this one a few times to see the different outputs and circuits that are created.
For some examples of more gates or to read on the ones listed here go to Gates.
Top comments (0)