/***************************************************************************** * * Grover's Search Algorithm * * Implements Grover's Search algorithm in the Scaffold programming language * * February 2013 * *****************************************************************************/ #include #define n 10 // problem size (log of database size) #define pi 3.141592653589793238462643383279502884197 // Module prototypes void diffuse(qbit q[n]); void Sqr(qbit a[n], qbit b[n]); void EQxMark(qbit b[n], qbit t[1], int tF); /*************************** Diffusion Module ***************************/ void diffuse(qbit q[n]) { int j; // local qbit x[n-1]; // scratch register // No local registers yet qbit x[n-1]; // scratch register // Hadamard applied to q // No forall yet // forall(j=0; j 0; j--) Toffoli(x[j-1], q[j+1], x[j]); Toffoli(q[1], q[0], x[0]); // Restore q for(j = 0; j < n; j++) X(q[j]); // Complete the diffusion // No forall yet // forall(j=0; j 0; j--) Toffoli(x[j-1], b[j+1], x[j]); Toffoli(b[1], b[0], x[0]); // Restore b for(j = 0; j < n; j++) if(j!=1) X(b[j]); } /*********************************************** Squaring a(x) = a0 + a1*x + ... + a_(n-1)*x^(n-1) over the ring GF(2)[x] mod (x^n + x + 1). Result placed in the n-qubit register b ************************************************/ void Sqr(qbit a[n], qbit b[n]) { int i; int k; // Using forall indicates the CNOT's are independent // So these instructions can be done in parallel // No forall yet // forall(i=0; i<=(n-1)/2; i++) { for(i=0; i<=(n-1)/2; i++) { k = 2*i; CNOT(a[i], b[k]); } // Would it make a difference to split this into two loops? // Maybe since deleaving would be two forall loops! // Or perhaps it is okay to just replace the for with a forall. for(i=(n+1)/2; i