Quantum Fourier Transform

high-level simulation

  // quantum FFT
  //
  void qfft( int inv = 0) {

    fft<Complex,Real>( a, N, inv); // classical FFT, without scaling and bit reversal

   // scale values and bit-reverse the indices
   //
    Real s = 1/std::sqrt((Real)N);

    for( unsigned long i = 0, j = 0; i < N; ++i) {

      j = bitrev( i, n);

      if( i < j) { swap( i, j); a[i] *= s; a[j] *= s; }

      else if( i == j) a[i] *= s;
    }
  }