ECE 1620 Assignment #7

ECE 1620 - Assignment #7 - Due: 22 March 2019

a7/p1.c - random integer array
Write a C program using a single array of 10 integers. In the main program:
1. Use rand() to fill the array with random integers in the range 0 ... 9, then print the array.
2. Fill the array with the integers from 0 to 9 in order, then print the array.
3. Put the array elements into random order, then print the array.
Use functions for printing and shuffling the array. You can use this shuffle function.
Initialize rand() using srand(time(0)) just once at the beginning of the main program.
Example output:
```
  3  6  0  4  0  4  1  5  8  5
  0  1  2  3  4  5  6  7  8  9
  1  3  7  2  8  6  4  5  9  0
```
Extra/optional
a7/p2.c - quantum computing simulation
Write a C program to compare classical and quantum computing solutions to the problem of determining if a hidden Boolean function is constant or balanced. The function is hidden in the sense that you cannot see inside the function and examine how it works, however you can call it and see the return value for any input. This problem was one of the first to demonstrate the speedup possible with a quantum computer, and it has been extended to practical applications such as database searching and breaking cryptography.
The classical hidden function is in the form: int fx( int x, int N);
where x is an n-bit integer in the range 0 to N-1 with N=2ⁿ. The function is either constant, i.e. it returns 0 for all values of x, or returns 1 for all values of x; or it is balanced, i.e. it returns 0 for half of the possible values of x and 1 for the other half.
A classical solution must call the function up to 1+N/2 times to determine if it is constant or balanced. For example, with n=3, N=2³=8, if you call the function for 4 different inputs and get return values of 0, 0, 0, 0, you can not say whether it is constant or balanced; the remaining 4 inputs might produce 0 or 1 return values. So you have to call it at least one more time to check. If 5 out of the 8 different inputs produce return values of 0 then we know it can not be balanced, so it must be constant.
Somewhat amazingly, the quantum computing solution to this problem can determine if the function is constant or balanced with just one function call, regardless of the size of n. If we had a physical quantum computer we could set it up using n+1 qubits to solve this problem, with n qubits representing the input values and the extra qubit for the function value [1]. Simulating the quantum computations on a classical computer requires use of an array of size 2ⁿ⁺¹ and is not efficient, but can demonstrate the effectiveness of the quantum algorithm. The array elements represent amplitudes of the quantum states, with the magnitude squared representing a probability [2].
The simulated quantum hidden function is in the form: void fq( double q[], int M);
where m=n+1 is the number of qubits and q is an array of size M=2^m.
fx() and fq() are declared in qc.h and defined in qc.c. To access these functions use:
```
  #include "qc.h"
```
Also provided is a quantum Hadamard transformation in the form: void H( double q[], int M);
This operation can be used to put the qubits in a superposition of states and is one of the keys to the power of quantum computing. Each qubit acts like a 0 and 1 at the same time, so m qubits can represent the possible 2^m values all at once.
Simulation Steps
1. Use scanf() to read a value for n, and use n=3 if that fails. Then initialize N, m, and M: N=2ⁿ, m=n+1, M=2^m.
2. Print a table of x and fx values for x from 0 to N-1. If all of the fx values are the same (all 0 or all 1), print "constant", otherwise print "balanced".
3. Create an array of M double, initialized to all 0's except q[1]=1. Write functions to initialize the array and print the array. Use something like the following code fragment to perform the quantum algorithm [1]:
```
  double q[M];

  init(q,M); print(q,M); // you have to write the init and print functions

  H(q,M); print(q,M);

  fq(q,M); print(q,M);

  H(q,M); print(q,M);
```
  Note that there is no loop in the quantum algorithm and fq() is only invoked once.
4. Compute and display the probability P₀ that the first n qubits are 0; that is simply the sum of the squares of q[0] and q[1]. Also display 1-P₀ to see how close it is to 1. If P₀ is less than 0.5, print "balanced", otherwise print "constant". Theoretically P₀ should be exactly 0 or exactly 1, but it might come out slightly different due to roundoff error.
Note that the hidden function is randomly chosen from an internal set of functions each time your program is run, so sometimes it will be constant and sometimes it will be balanced.
Sample Output
Extra/optional

References

[0] ex2 - partial algorithm analysis for n=2.

[1] The Deutsch-Jozsa Problem: De-quantisation and Entanglement, Alastair A. Abbott, 2010. Recommended: sections 1-4.

[2] An Introduction to Quantum Computing, Without the Physics, Giacomo Nannicini, Nov 2018. Recommended: sections 1-3; skip example 4 and the proofs.

[3] Quantum algorithms revisited, R. Cleve, A. Ekert, C. Macchiavello, M. Mosca, Proc. R. Soc. Lond. A (1998) 454, 339-354. This is reference #6 from [1]. Recommended: sections 1-3.