// quantum computing emulation routines
//
// Bernstein & Vazirani problem: determine the hidden coefficient of a Boolean function
//
// R. Perry, Jan. 2019
//
#include <tgmath.h>
#include <stdlib.h>
#include "qc.h"

//------------------------------ private ------------------------------
//
//  s2	  sqrt(2)/2
//  swap  swap two states
//  Hk	  perform Hadamard transformation on qubit k
//
static double s2 = 0;
//
static void swap( double complex q[], unsigned long i, unsigned long j)
{
  double complex t = q[i];  q[i] = q[j];  q[j] = t;
}
//
static void Hk( double complex q[], unsigned long M, unsigned int k)
{
  if( s2 == 0) s2 = sqrt(2)/2;

  unsigned long i = 0, j, k1 = 1LU << k; // k1 = 0...010...0, k'th bit = 1

  while( i < M) // i will have k'th bit = 0, j will have k'th bit = 1
  {
    j = i | k1;  double complex t0 = q[i], t1 = q[j];

    q[i] = s2*(t0+t1);  q[j] = s2*(t0-t1);

    ++i;  i += (i & k1); // skip i values with k'th bit = 1
  }
}

//------------------------------ public ------------------------------
//
//  A	the hidden coefficient
//  fx	the classical Boolean function
//  fq	the quantum Boolean function
//  H	perform Hadamard transformation on all qubits
//
unsigned long A( unsigned long N)
{
  static unsigned long coeff = 0;  if( coeff == 0) { coeff = 1 + rand()%(N-1); }

  return coeff;
}
//
unsigned int fx( unsigned long x, unsigned long N) // 0 <= x <= N-1
{
  unsigned int r = 0;  unsigned long t = x & A(N);

  while( t) { r ^= (t & 1); t >>= 1; }

  return r;
}
//
void fq( double complex q[], unsigned long M) // state (x,y) -> (x,y+f(x))
{
  unsigned long N = M >> 1;

  for( unsigned long i = 0; i < M; i += 2) if( fx(i>>1,N) ) swap( q, i, i|1);
}
//
void H( double complex q[], unsigned long M)
{
  unsigned long mask = M >> 1;

  for( unsigned int k = 0; mask; ++k) { Hk( q, M, k); mask >>= 1; }
}