Deutsch's algorithm 
Tags: python, cirq
Published: 2020-08-23 22:07:56

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](https://cirq.readthedocs.io/en/stable/gates.html).