loading...
Cover image for Deutsch's algorithm

Deutsch's algorithm

dmarcr1997 profile image Damon Marc Rocha II ・3 min read

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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()
Enter fullscreen mode Exit fullscreen mode

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.

Discussion

pic
Editor guide