ECE 8473 Assignment #2

ECE 8473 Assignment #2 - Due: 15 Feb. 2019

a2/p1.c - quantum computing simulation
Write a C program to compare classical and quantum computing solutions to the problem of determining the n-bit coefficient hidden inside a Boolean function (Bernstein & Vazirani problem [1]). This problem demonstrates the speedup possible with a quantum computer, and it has been extended to practical applications such as database searching and breaking cryptography. For background on quantum computing see [2]. For some recent news see [3].
The Boolean function is the bitwise dot product f(x) = a•x = a₀x₀ ⊕ a₁x₁ ⊕ ... ⊕ a_n-1x_n-1 where a is the hidden coefficient. a_i and x_i are bit i of a and x, and ⊕ means XOR. In other words f(x) is the modulo-2 sum of the bits in the bit-wise AND (a & x). a and x can also be written as sums of powers of 2: a = ∑ a_i 2ⁱ, x = ∑ x_i 2ⁱ, where each a_i and x_i is 0 or 1.
You cannot look inside the function to see a, however you can call the function and see the return value for any input. A classical solution must invoke f() n times to determine the hidden coefficient: one call for each bit of a, using powers of 2 for the x values. But the quantum computing solution to this problem can determine the hidden coefficient 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 do this, with n qubits representing the input values and the extra qubit for the function value [1, Figure 4].
Simulating the quantum computations on a classical computer requires an array of size 2ⁿ⁺¹ and is not efficient, but can demonstrate the effectiveness of the quantum algorithm. The array elements represent complex amplitudes of the quantum states, and the magnitude squared of an amplitude corresponds to the probability of measuring that state.
Simulation Library
The following routines are declared in qc.h and defined in qc.c:
```
// the hidden coefficient (for debugging)
//
unsigned long A( unsigned long N);

// the classical Boolean function
//
unsigned int fx( unsigned long x, unsigned long N); // 0 <= x <= N-1

// the quantum Boolean function
//
void fq( double _Complex q[], unsigned long M); // q[0]...q[M-1]

// perform Hadamard transformation on all qubits
//
void H( double _Complex q[], unsigned long M);
```
where x is an n-bit integer in the range 0 to N-1 with N=2ⁿ. The number of qubits is m=n+1, and q is an array of size M=2^m.
qc.h and qc.c are available in VECR a2/ and are used by the Makefile there.
To access these routines use: #include "qc.h"
Note that the hidden coefficient is randomly generated each time your program is run. For debugging you can access the coefficient by calling A(N).
The Hadamard transformation can be used to put qubits in a superposition of states and is one of the keys to the power of quantum computing. Each qubit can act 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. Include tgmath.h, which includes math.h and complex.h.
2. Initialize the pseudo-random number generator, just once at the beginning of main(): srand(time(0));
3. Use scanf() to read a value for n, and use n=3 if that fails. Then initialize N=2ⁿ, m=n+1, M=2^m.
4. Determine a classically by calling fx(x,N) for x = 1, 2, 4, 8, ... i.e. the powers of 2 less than N. For each x, if the function returns 1 then the corresponding a_i is 1, otherwise a_i is 0.
  Display a table of x and the function values.
5. Create an array of M double complex, initialized to all 0's except q[1] = e^jθ (complex exponential) where θ is a random phase in the range [-π,π). This global phase factor will not affect results.
  Write functions to initialize the array and print the array.
  Use something like the following code fragment to perform the quantum algorithm:
```
  double complex q[M]; init(q,M); print(q,M);

  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.
6. Determine the quantum estimate of a by finding argmax |q_i|, i = 0 ... M-1 (i.e. find which q is the largest in magnitude, and save the index i of that one), then a = i >> 1 (or i/2, the top n bits of i). This represents the most likely measured value.
In a physical quantum computer we can not see the amplitudes, and a measurement collapses the state to a value based on probability (magnitude squared of amplitude). In a simulation we could simulate measurements, but it is often more useful to work with the amplitudes directly.
a2/p2.c - quantum computing simulation with dephasing noise
Start with a copy of your program from part 1 and modify it to include dephasing noise after calling fq(), something like this:
```
  double complex q[M]; init(q,M); H(q,M); fq(q,M); R(q,M,phi); H(q,M); 
```
where you must implement R() to perform the R_φ transformation on all qubits:

R_φ =

1 0

0 e^jφ

The action of R_φ is: R_φ |0> = |0>, R_φ |1> = e^jφ|1>
In step 3, instead of using scanf() to read from standard input, set n=8 and get an angle in degrees from the command-line, for example:
```
int main( int argc, char *argv[])
{
  double ang = 0;  if( argc > 1) ang = atof(argv[1]);
  ...
```
Then φ = ang*π/180.
The only output must be a table with two columns of values suitable for plotting: i and |q_i|² (state probabilities), i = 0 ... M-1.
Results should show that with no noise (ang=0) as in part 1, the probability of measuring the correct value of the hidden coefficient is 1. But as ang increases this probability decreases and for ang=90 all possible measurement values are equally likely.

References

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

Figure 4. Network representation of Bernstein-Vazirani's algorithm

[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 leap, Don Monroe, CACM Jan. 2019. A new proof supports a 25-year-old claim of the unique power of quantum computing.