https://github.com/epiqc/ScaffCC
Tip revision: 66a79944ee4cd116b27bc1a69137276885461db8 authored by Andrew Litteken on 28 September 2021, 15:30:02 UTC
Merge pull request #49 from AndrewLitteken/master
Merge pull request #49 from AndrewLitteken/master
Tip revision: 66a7994
TFP_Oracle.scaffold
/****************************************************************************************
* Description: Oracle for Triangle Finding Problem
*
* Author: Chen-Fu Chiang @ USherbrooke
*
* Implementation of the Oracle for the triangle finding algorithm specified in the
* Quantum Computer Science Program @ Government Furnished Information document
*
* GFI Document date: June 20, 2011
* GFI Document Version: 1.0.0
* GFI Document Reversion number: 188
* Recent Update: Based on https://qcs.ornl.gov/trac/qcs-scaffold/ticket/3
*****************************************************************************************/
// FIXME: placeholder for now
/***********************************************
* 4-Qubit Toffoli
************************************************/
scaff_module C_Toffoli (qbit target, qbit ctrl1, qbit ctrl2, qbit ctrl3)
{
CNOT ( ctrl2,ctrl1);
Toffoli ( ctrl3, ctrl1,target);
}
// FIXME: placeholder for now
/***********************************************
* 5-Qubit Toffoli
************************************************/
scaff_module C_C_Toffoli (qbit target, qbit ctrl1, qbit ctrl2, qbit ctrl3, qbit ctrl4)
{
CNOT ( ctrl2,ctrl1);
Toffoli ( ctrl3, ctrl1,target);
X(ctrl4);
}
/***********************************************
* Controlled Version of the C_EvaluateOR scaff_module
************************************************/
scaff_module C_EvaluateOR(qbit target, qbit ctr2, qbit ctr1, qbit ctrl)
{
CNOT( ctrl,ctr1);
CNOT( ctrl,ctr2);
C_Toffoli(target, ctr2, ctr1, ctrl);
CNOT( ctrl,target);
}
/*************************************************
* Controlled Version of the C_InvEvaluateOR scaff_module
**************************************************/
scaff_module C_InvEvaluateOR(qbit target, qbit ctr2, qbit ctr1, qbit ctrl)
{
CNOT( ctrl,target);
C_Toffoli(target, ctr2, ctr1, ctrl);
CNOT( ctrl,ctr2);
CNOT( ctrl,ctr1);
}
/***********************************************
* Controlled Version of the C_EvaluateOR scaff_module
************************************************/
scaff_module C_C_EvaluateOR(qbit target, qbit ctr2, qbit ctr1, qbit ctrl1, qbit ctrl2)
{
Toffoli( ctrl2, ctrl1,ctr1);
Toffoli( ctrl2, ctrl1,ctr2);
C_C_Toffoli(target, ctr2, ctr1, ctrl1, ctrl2);
Toffoli( ctrl2, ctrl1,target);
}
/***********************************************
* Controlled Version of the C_EvaluateOR scaff_module
************************************************/
scaff_module C_C_InvEvaluateOR(qbit target, qbit ctr2, qbit ctr1, qbit ctrl1, qbit ctrl2)
{
Toffoli( ctrl2, ctrl1,target);
C_C_Toffoli(target, ctr2, ctr1, ctrl1, ctrl2);
Toffoli( ctrl2, ctrl1,ctr2);
Toffoli( ctrl2, ctrl1,ctr1);
}
/***********************************************
* Controlled version of the ADD scaff_module
************************************************/
scaff_module C_ADD (qbit x[cn], qbit y[cn], qbit s[cn], qbit ctrl)
{
// workspace registers
qbit c1[cn+1];
qbit c2[cn+1];
qbit tmp[2];
qbit s1[cn];
int j = 0;
PrepZ(c1[0],0);
/*************************************
* Bit-wise OR is just CNOT
* Bit-wise AND is just Toffoli
**************************************/
/**********************************
* c1[0] is fresh, hence it is a 0
**********************************/
for(j = 0; j < cn; j++)
{
/***********************************************
* OK to do so since c1[j+1] always starts with 0
************************************************/
C_Toffoli(c1[j+1], x[j], y[j], ctrl);
C_Toffoli(tmp[0], x[j], c1[j], ctrl);
Toffoli( ctrl, tmp[0],c1[j+1]);
// uncompute tmp[0]
C_Toffoli(tmp[0], x[j], c1[j], ctrl);
C_Toffoli(tmp[0], y[j], c1[j], ctrl);
Toffoli( ctrl, tmp[0],c1[j+1]);
// uncompute tmp[0]
C_Toffoli(tmp[0], y[j], c1[j], ctrl);
C_EvaluateOR(tmp[0], y[j], c1[j], ctrl);
C_EvaluateOR(tmp[1], tmp[0], x[j], ctrl);
/***********************************************
* OK to do so since s1[j] always starts with 0
************************************************/
Toffoli( ctrl, tmp[1],s1[j]);
/**************************************************************************************
* uncompute tmp[0], tmp[1]; also offset the "NOT" operation during EvaluateOR operation
***************************************************************************************/
C_InvEvaluateOR(tmp[1], tmp[0], x[j], ctrl);
C_InvEvaluateOR(tmp[0], y[j], c1[j], ctrl);
}
Toffoli( ctrl, c1[cn],c2[0]);
for(j = 0; j < cn; j++)
{
/***********************************************
* OK to do so since c2[j+1] always starts with 0
************************************************/
C_Toffoli(c2[j+1], s1[j], c2[j], ctrl);
/*******************************************************************************
* if s register is passed in as a clean register; can do cnot to assign value
* if s register is passed in as a dirty register, then this step uncompte s[j]
********************************************************************************/
C_EvaluateOR(tmp[0], s1[j], c2[j], ctrl);
Toffoli( ctrl, tmp[0],s[j]);
// uncompute tmp[0] and offset the "NOT" operation during EvaluateOR operation
C_InvEvaluateOR(tmp[0], s1[j], c2[j], ctrl);
}
/*******************************************************************************
* if s register is passed in as a clean register; can do cnot to assign value
* if s register is passed in as a dirty register, then this step uncompte s[j]
********************************************************************************/
Toffoli( ctrl, c2[cn],s[1]);
/********************************
* Uncompute process: c2 register
********************************/
for(j = cn-1; j > -1; j--)
{
C_Toffoli(c2[j+1], s1[j], c2[j], ctrl);
}
Toffoli( ctrl, c1[cn],c2[0]);
/****************************************
* Uncompute process: c1 register and s1
* Run the process backward to uncompute
****************************************/
for(j = cn-1; j > -1; j--)
{
C_EvaluateOR(tmp[0], y[j], c1[j], ctrl);
C_EvaluateOR(tmp[1], tmp[0], x[j], ctrl);
// uncompute s1[j]
Toffoli( ctrl, tmp[1],s1[j]);
// uncompute tmp[0], tmp[1] and offset NOT operation imposed by EvaluateOR
C_InvEvaluateOR(tmp[1], tmp[0], x[j], ctrl);
C_InvEvaluateOR(tmp[0], y[j], c1[j], ctrl);
C_Toffoli(tmp[0], y[j], c1[j], ctrl);
Toffoli( ctrl, tmp[0],c1[j+1]);
// uncompute tmp[0]
C_Toffoli(tmp[0], y[j], c1[j], ctrl);
C_Toffoli(tmp[0], x[j], c1[j], ctrl);
Toffoli( ctrl, tmp[0],c1[j+1]);
// uncompute tmp[0]
C_Toffoli(tmp[0], x[j], c1[j], ctrl);
// c1[j+1] uncomputed; no need to worry about c1[0] because it has never been changed
C_Toffoli(c1[j+1], x[j], y[j], ctrl);
}
}
/***********************************************
* Controlled version of the C_ADD scaff_module
************************************************/
scaff_module C_C_ADD (qbit x[cn], qbit y[cn], qbit s[cn], qbit ctrl1, qbit ctrl2)
{
// workspace registers
qbit c1[cn+1];
qbit c2[cn+1];
qbit tmp[2];
qbit s1[cn];
int j = 0;
PrepZ(c1[0],0);
/*************************************
* Bit-wise OR is just CNOT
* Bit-wise AND is just Toffoli
**************************************/
/**********************************
* c1[0] is fresh, hence it is a 0
**********************************/
for(j = 0; j < cn; j++)
{
/***********************************************
* OK to do so since c1[j+1] always starts with 0
************************************************/
C_C_Toffoli(c1[j+1], x[j], y[j], ctrl1, ctrl2);
C_C_Toffoli(tmp[0], x[j], c1[j], ctrl1, ctrl2);
C_Toffoli(c1[j+1], tmp[0], ctrl1, ctrl2);
// uncompute tmp[0]
C_C_Toffoli(tmp[0], x[j], c1[j], ctrl1, ctrl2);
C_C_Toffoli(tmp[0], y[j], c1[j], ctrl1, ctrl2);
C_Toffoli(c1[j+1], tmp[0], ctrl1, ctrl2);
// uncompute tmp[0]
C_C_Toffoli(tmp[0], y[j], c1[j], ctrl1, ctrl2);
C_C_EvaluateOR(tmp[0], y[j], c1[j], ctrl1, ctrl2);
C_C_EvaluateOR(tmp[1], tmp[0], x[j], ctrl1, ctrl2);
/***********************************************
* OK to do so since s1[j] always starts with 0
************************************************/
C_Toffoli(s1[j], tmp[1], ctrl1, ctrl2);
/**************************************************************************************
* uncompute tmp[0], tmp[1]; also offset the "NOT" operation during EvaluateOR operation
***************************************************************************************/
C_C_InvEvaluateOR(tmp[1], tmp[0], x[j], ctrl1, ctrl2);
C_C_InvEvaluateOR(tmp[0], y[j], c1[j], ctrl1, ctrl2);
}
C_Toffoli(c2[0], c1[cn], ctrl1, ctrl2);
for(j = 0; j < cn; j++)
{
/***********************************************
* OK to do so since c2[j+1] always starts with 0
************************************************/
C_C_Toffoli(c2[j+1], s1[j], c2[j], ctrl1, ctrl2);
/*******************************************************************************
* if s register is passed in as a clean register; can do cnot to assign value
* if s register is passed in as a dirty register, then this step uncompte s[j]
********************************************************************************/
C_C_EvaluateOR(tmp[0], s1[j], c2[j], ctrl1, ctrl2);
C_Toffoli(s[j], tmp[0], ctrl1, ctrl2);
// uncompute tmp[0] and offset the "NOT" operation during EvaluateOR operation
C_C_InvEvaluateOR(tmp[0], s1[j], c2[j], ctrl1, ctrl2);
}
/*******************************************************************************
* if s register is passed in as a clean register; can do cnot to assign value
* if s register is passed in as a dirty register, then this step uncompte s[j]
********************************************************************************/
C_Toffoli(s[1], c2[cn], ctrl1, ctrl2);
/********************************
* Uncompute process: c2 register
********************************/
for(j = cn-1; j > -1; j--)
{
C_C_Toffoli(c2[j+1], s1[j], c2[j], ctrl1, ctrl2);
}
C_Toffoli(c2[0], c1[cn], ctrl1, ctrl2);
/****************************************
* Uncompute process: c1 register and s1
* Run the process backward to uncompute
****************************************/
for(j = cn-1; j > -1; j--)
{
C_C_EvaluateOR(tmp[0], y[j], c1[j], ctrl1, ctrl2);
C_C_EvaluateOR(tmp[1], tmp[0], x[j], ctrl1, ctrl2);
// uncompute s1[j]
C_Toffoli(s1[j], tmp[1], ctrl1, ctrl2);
// uncompute tmp[0], tmp[1] and offset NOT operation imposed by EvaluateOR
C_C_InvEvaluateOR(tmp[1], tmp[0], x[j], ctrl1, ctrl2);
C_C_InvEvaluateOR(tmp[0], y[j], c1[j], ctrl1, ctrl2);
C_C_Toffoli(tmp[0], y[j], c1[j], ctrl1, ctrl2);
C_Toffoli(c1[j+1], tmp[0], ctrl1, ctrl2);
// uncompute tmp[0]
C_C_Toffoli(tmp[0], y[j], c1[j], ctrl1, ctrl2);
C_C_Toffoli(tmp[0], x[j], c1[j], ctrl1, ctrl2);
C_Toffoli(c1[j+1], tmp[0], ctrl1, ctrl2);
// uncompute tmp[0]
C_C_Toffoli(tmp[0], x[j], c1[j], ctrl1, ctrl2);
// c1[j+1] uncomputed; no need to worry about c1[0] because it has never been changed
C_C_Toffoli(c1[j+1], x[j], y[j], ctrl1, ctrl2);
}
}
/***********************************************
* Controlled Version of the MUL scaff_module
************************************************/
scaff_module C_MUL (qbit x[cn], qbit y[cn], qbit p[cn], qbit ctrl)
{
qbit tmp[cn];
qbit wrk[cn];
qbit wrk2[cn];
int i = 0;
int j = 0;
int k = 0;
for(j = 0; j < cn; j++)
{
/**************************************************************************************************************************
* In my case, I always pass in clean p array to do the computation, hence, do not need to worry about setting bits to zero
***************************************************************************************************************************/
PrepZ(p[j],0);
Toffoli( ctrl, y[j],tmp[j]);
}
for(k = 0; k < cn; k++)
{
/************************************************
* Use the if, else if, else: provided by Scaffold
************************************************/
//if(x[k]==1) // ajavadia: converted controlled circuit to controlled unitaries
//{
C_C_ADD(p, tmp, wrk, x[k], ctrl);
/**************************************************************************************************************
* uncompute p back to all 0 register
* wrk2 remains as all 0 throughout the whole process
* Idea (at the checkpoint): because when k = 0, we have p = 0, wrk = 0;
* when k = 1; p = tmp, wrk = 2tmp; so, do ADD(wrk2, tmp, p) to clean up p
* when k = 2, p = 2tmp, wrk = 3tmp, so do ADD(wrk2, tmp, p) two times to clean up p (logically this should work)
****************************************************************************************************************/
for(i = 0; i < k; i++)
{
C_C_ADD(wrk2, tmp, p, x[k], ctrl);
}
for(j = 0; j < cn; j++)
{
/************************************************
* swap to assign the computed value to p
* also have wrk back to all 0
*************************************************/
C_Toffoli(p[j], wrk[j], x[k], ctrl);
C_Toffoli(wrk[j], p[j], x[k], ctrl);
C_Toffoli(p[j], wrk[j], x[k], ctrl);
}
//}
for(j = 0; j < cn-1; j++)
{
/***********************************************************
* 3 CNOT is a swap
************************************************************/
Toffoli( ctrl, tmp[j],tmp[cn-1]);
Toffoli( ctrl, tmp[cn-1],tmp[j]);
Toffoli( ctrl, tmp[j],tmp[cn-1]);
}
}
/**************************************************************************
* Uncompute Process: roll back tmp register as wrk was already uncomputed
***************************************************************************/
for(k = cn-1; k > -1 ; k--)
{
for(j = cn-2; j > -1; j--)
{
/******************************************
* swap again to be back to original value
*******************************************/
Toffoli( ctrl, tmp[j],tmp[cn-1]);
Toffoli( ctrl, tmp[cn-1],tmp[j]);
Toffoli( ctrl, tmp[j],tmp[cn-1]);
}
}
for(j = cn-1; j > -1; j--)
{
Toffoli( ctrl, y[j],tmp[j]);
}
}
/***********************************************
* Controlled Version of the unMul scaff_module
************************************************/
scaff_module C_unMUL (qbit x[cn], qbit y[cn], qbit p[cn], qbit ctrl)
{
qbit tmp[cn];
qbit wrk[cn];
qbit tp[cn];
qbit wrk2[cn];
int i = 0;
int j = 0;
int k = 0;
for(j = 0; j < cn; j++)
{
Toffoli( ctrl, y[j],tmp[j]);
}
for(k = 0; k < cn; k++)
{
/************************************************
* Use the if, else if, else: provided by Scaffold
************************************************/
// if(x[k]==1) // ajavadia: converted controlled circuit to controlled unitaries
// {
C_C_ADD(tp, tmp, wrk, x[k], ctrl);
if(k!= cn-1)
{
/****************************************************
* uncompute tp back to all 0 register
* same reasoning as given in MUL scaff_module
****************************************************/
for(i = 0; i < k; i++)
{
C_C_ADD(wrk2, tmp, tp, x[k], ctrl);
}
for(j = 0; j < cn; j++)
{
/************************************************
* swap to assign the computed value to tp
* also have wrk back to all 0
*************************************************/
C_Toffoli(tp[j], wrk[j], x[k], ctrl);
C_Toffoli(wrk[j], tp[j], x[k], ctrl);
C_Toffoli(tp[j], wrk[j], x[k], ctrl);
/**********************************************
* Now we can use tp to reset p
* tp can be used and then cleaned up in next iteration
***********************************************/
C_Toffoli(p[j], tp[j], x[k], ctrl);
}
}
/**********************************************************************************************************
* Uncomputation process is a bit different in the order where the blocks of code appear
* at the final bit such that we can get every register back to all zero state
***********************************************************************************************************/
else
{
for(j = 0; j < cn; j++)
{
/*********************************************
* Now we can directly use wrk to reset p since
* we do not need tp register after this iteration
*********************************************/
C_Toffoli(p[j], wrk[j], x[k], ctrl);
}
/************************************
* uncompute wrk back to all 0
************************************/
C_C_ADD(tp, tmp, wrk, x[k], ctrl);
/****************************************************
* uncompute tp back to all 0 register
* same reasoning as given in MUL scaff_module
****************************************************/
for(i = 0; i < k; i++)
{
C_C_ADD(wrk2, tmp, tp, x[k], ctrl);
}
}
// }
for(j = 0; j < cn-1; j++)
{
/***********************************************************
* 3 CNOT is a swap
************************************************************/
Toffoli( ctrl, tmp[j],tmp[cn-1]);
Toffoli( ctrl, tmp[cn-1],tmp[j]);
Toffoli( ctrl, tmp[j],tmp[cn-1]);
}
}
/**************************************************************************
* Uncompute Process: roll back : tmp register as wrk was already uncomputed
***************************************************************************/
for(k = cn-1; k > -1 ; k--)
{
for(j = cn-2; j > -1; j--)
{
/******************************************
* swap again to be back to original value
*******************************************/
Toffoli( ctrl, tmp[j],tmp[cn-1]);
Toffoli( ctrl, tmp[cn-1],tmp[j]);
Toffoli( ctrl, tmp[j],tmp[cn-1]);
}
}
for(j = cn-1; j > -1; j--)
{
Toffoli( ctrl, y[j],tmp[j]);
}
}
/**************************************************************
* Useful Ancillary scaff_modules (used by Oracle and Algorithm)
***************************************************************/
scaff_module Swap(qbit q1, qbit q2)
{
CNOT(q1,q2);
CNOT(q2,q1);
CNOT(q1,q2);
}
scaff_module ctrSwap(qbit q1,qbit q2, qbit q3)
{
Toffoli( q3,q1,q2);
Toffoli( q3,q2,q1);
Toffoli( q3,q1,q2);
}
/***********************************************************
* target[0] = OR(ctr2[0] , ctr1[0])
************************************************************/
scaff_module EvaluateOR(qbit target, qbit ctr2, qbit ctr1)
{
X(ctr1);
X(ctr2);
Toffoli( ctr1, ctr2,target);
X(target);
}
scaff_module InvEvaluateOR(qbit target, qbit ctr2, qbit ctr1)
{
X(target);
Toffoli( ctr1, ctr2,target);
X(ctr2);
X(ctr1);
}
/*******************************************************
* The following auxillary scaff_module(s) are used in Oracle
********************************************************/
scaff_module equalquInt2(qbit x[2], qbit y[2], qbit equal)
{
int i = 0;
qbit dum[2];
for(i = 0; i < 2; i++)
{
Toffoli( y[i], x[i],dum[i]);
}
Toffoli( dum[0], dum[1],equal);
//uncompute
for(i = 1; i > -1; i--)
{
Toffoli( y[i], x[i],dum[i]);
}
}
/*********************************************************************
* The following scaff_module(s) listed in the GFI document
* They are summoned by the main oracle function EdgeOracle
* The apperance order is 6, 2, 3, 7, 8, 4, 5, and 1 (the EdgeOracle).
***********************************************************************/
/**************************************************************
* Algorithm O-6: SUB(qbit x[cn], int y, qbit d[cn])
* Para: x: qbit[cn]
* y: int
* d: qbit[cn]
* It is clear to see that y's presentation in terms of the
* sum of 2 to different power. This function is summoned
* by ConvertNODE and y is hn, which is 2^(n-1). Hence,
* all y_i are all 0 except at y_(n-1).
**************************************************************/
scaff_module SUB(qbit x[cn], int y, qbit d[cn])
{
qbit c1[cn+1];
qbit c2[cn+1];
/*********************************
* yi cofficient; yes, just one bit
**********************************/
qbit yi[1];
qbit tmp[2];
qbit d1[cn];
int j = 0;
PrepZ(c1[0],0);
/************************
* cn is defined globally
*************************/
for(j = 0; j < cn; j++)
{
/********************************************
* n is defined globally
* when j=n-1, the coefficient should be 1
* when j!= n -1, the coefficients should be 0
*********************************************/
if(j == n-1)
{
// set yi to 1
X(yi[0]);
}
if(j == n)
{
// reset to 0; hence we don't care about uncomputation as yi[0] is restored back to 0
X(yi[0]);
}
/********************************
* doing the 1 xor yi onto tmp[0]
*********************************/
CNOT( yi[0],tmp[0]);
X(tmp[0]);
/***********************************************************
* assign value; ok to do so as c1 is instantiated with all 0
************************************************************/
Toffoli( x[j], tmp[0],c1[j+1]);
// uncompute tmp array
X(tmp[0]);
CNOT( yi[0],tmp[0]);
Toffoli( x[j], c1[j],tmp[0]);
CNOT( tmp[0],c1[j+1]);
// uncompute
Toffoli( x[j], c1[j],tmp[0]);
CNOT( yi[0],tmp[0]);
X(tmp[0]);
Toffoli( c1[j], tmp[0],tmp[1]);
CNOT( tmp[1],c1[j+1]);
// uncompute tmp[1]; do not uncompute tmp[0] as we still need it
Toffoli( c1[j], tmp[0],tmp[1]);
CNOT( c1[j],tmp[0]);
CNOT( x[j],tmp[0]);
/*********************************************************************
* Assign value to d1[j]; OK to do so as d1 is all 0 when instantiated
*********************************************************************/
CNOT( tmp[0],d1[j]);
// uncompute tmp[0]
CNOT( x[j],tmp[0]);
CNOT( c1[j],tmp[0]);
X(tmp[0]);
CNOT( yi[0],tmp[0]);
}
CNOT( c1[cn],c2[0]);
for(j = 0; j < cn; j++)
{
/************************************************************************************************
* (a) If value assigning to d[j]; OK to do so because of all 0 of d (run for the first time)
* (b) Uncomputation purpose: When SUB is run for the 2nd time with the same parameters (x and y)
* then the value of d[j] is then reset to 0.
*************************************************************************************************/
Toffoli( c2[j], d1[j],c2[j+1]);
CNOT( c2[j],tmp[0]);
CNOT( d1[j],tmp[0]);
CNOT( tmp[0],d[j]);
// uncompute tmp[0]
CNOT( d1[j],tmp[0]);
CNOT( c2[j],tmp[0]);
}
/**************************************************
* Same reason as given above in (a) and (b)
***************************************************/
//CNOT( c2[31],d[0]); //spatil
CNOT( c2[cn],d[0]);
/*********************************
* Uncompute Process: c2 register
*********************************/
for(j = cn - 1; j > -1; j--)
{
Toffoli( c2[j], d1[j],c2[j+1]);
}
CNOT( c1[cn],c2[0]);
/***********************************************
* Uncompute Process: c1 register and d1 register
***********************************************/
for(j = cn-1; j > -1; j--)
{
/************************
* n is defined globally
*************************/
if(j == n-1)
{
// set yi to 1
X(yi[0]);
}
if(j == n-2)
{
// reset to 0
X(yi[0]);
}
CNOT( yi[0],tmp[0]);
X(tmp[0]);
CNOT( c1[j],tmp[0]);
CNOT( x[j],tmp[0]);
// restore d1
CNOT( tmp[0],d1[j]);
// restore tmp[0] to the value of NOT(yi)
CNOT( c1[j],tmp[0]);
CNOT( x[j],tmp[0]);
Toffoli( c1[j], tmp[0],tmp[1]);
CNOT( tmp[1],c1[j+1]);
// make tmp[1] clean for reuse
Toffoli( c1[j], tmp[0],tmp[1]);
Toffoli( x[j], c1[j],tmp[1]);
CNOT( tmp[1],c1[j+1]);
// make tmp[1] clean
Toffoli( x[j], c1[j],tmp[1]);
Toffoli( tmp[0], x[j],c1[j+1]);
// uncompute tmp[0]
X(tmp[0]);
CNOT( yi[0],tmp[0]);
}
}
/**************************************************************
* Algorithm O-2: ConvertNODE
* Para: u: an qbit array of size n
* uint: qbit[cn]
* int: hn
**************************************************************/
scaff_module ConvertNode(qbit u[], int uoffset, qbit uint[cn], int hn)
{
qbit w[cn];
int i = 0;
// Just copying and initializing the values of array w
for( i = 0; i < cn; i++)
{
/************************************
* Initialize local register; all 0s
************************************/
PrepZ(w[i],0);
if(i < n)
{
CNOT( u[uoffset+i],w[i]);
}
}
/*********************************
* Do SUB and store result in unit
**********************************/
SUB(w, hn, uint);
/***********************************************************************
* Uncomputation process: w register
* just need to run the loop again because w is not modify by SUB scaff_module
************************************************************************/
for( i = 0; i < cn; i++)
{
/************************************
* Initialize local register; all 0s
************************************/
PrepZ(w[i],0);
if(i < n)
{
CNOT( u[i],w[i]);
}
}
}
/**************************************************************
* Algorithm O-3: TestEqual(qbit x[cn], qbit y[cn], qbit t[1])
* Para: x: qbit[cn]
* y: qbit[cn]
* t: qbit
**************************************************************/
scaff_module TestEqual(qbit x[cn], qbit y[cn], qbit t)
{
qbit dum[cn];
qbit dum2[cn];
int i = 0;
int j = 0;
for(i = 0; i < cn; i ++)
{
Toffoli( y[i], x[i],dum[i]);
}
Toffoli( dum[0], dum[1],dum2[0]);
for(j = 1; j < cn-1; j++)
{
Toffoli( dum[j+1], dum2[j-1],dum2[j]);
}
// store the retore in t[0]
CNOT( dum2[cn-2],t);
/********************************
* uncompute process: dum2 array
********************************/
for(j = cn-2; j > 0; j--)
{
Toffoli( dum[j+1], dum2[j-1],dum2[j]);
}
Toffoli( dum[0], dum[1],dum2[0]);
/***********************
* Uncompute dum array
***********************/
for(i = 0; i < cn; i ++)
{
Toffoli( y[i], x[i],dum[i]);
}
}
/*************************************************************************
* Algorithm O-7: ADD(qbit x[cn], qbit y[cn], qbit s[cn])
* Para: x: qbit[cn]
* y: qbit[cn]
* s: qbit[cn]
* The idea here is that when we want to (compute) uncompute s
* If s is clean, then it computes x+y mode 2^31 - 1
* If s is dirty (got dirty from previous ADD(x, y, clean s), then
* the doing process again would undo the assignment done in ADD(x, y, clean s).
**************************************************************************/
scaff_module ADD(qbit x[cn], qbit y[cn], qbit s[cn])
{
// workspace registers
qbit c1[cn+1];
qbit c2[cn+1];
qbit tmp[2];
qbit s1[cn];
int j = 0;
PrepZ(c1[0],0);
/*************************************
* Bit-wise OR is just CNOT
* Bit-wise AND is just Toffoli
**************************************/
/**********************************
* c1[0] is fresh, hence it is a 0
**********************************/
for(j = 0; j < cn; j++)
{
/***********************************************
* OK to do so since c1[j+1] always starts with 0
************************************************/
Toffoli( y[j], x[j],c1[j+1]);
Toffoli( c1[j], x[j],tmp[0]);
CNOT( tmp[0],c1[j+1]);
// uncompute tmp[0]
Toffoli( c1[j], x[j],tmp[0]);
Toffoli( c1[j], y[j],tmp[0]);
CNOT( tmp[0],c1[j+1]);
// uncompute tmp[0]
Toffoli( c1[j], y[j],tmp[0]);
EvaluateOR(tmp[0], y[j], c1[j]);
EvaluateOR(tmp[1], tmp[0], x[j]);
/***********************************************
* OK to do so since s1[j] always starts with 0
************************************************/
CNOT( tmp[1],s1[j]);
/**************************************************************************************
* uncompute tmp[0], tmp[1]; also offset the "NOT" operation during EvaluateOR operation
***************************************************************************************/
InvEvaluateOR(tmp[1], tmp[0], x[j]);
InvEvaluateOR(tmp[0], y[j], c1[j]);
}
CNOT( c1[cn],c2[0]);
for(j = 0; j < cn; j++)
{
/***********************************************
* OK to do so since c2[j+1] always starts with 0
************************************************/
Toffoli( c2[j],s1[j],c2[j+1]);
/*******************************************************************************
* if s register is passed in as a clean register; can do cnot to assign value
* if s register is passed in as a dirty register, then this step uncompte s[j]
********************************************************************************/
EvaluateOR(tmp[0], s1[j], c2[j]);
CNOT( tmp[0],s[j]);
// uncompute tmp[0] and offset the "NOT" operation during EvaluateOR operation
InvEvaluateOR(tmp[0], s1[j], c2[j]);
}
/*******************************************************************************
* if s register is passed in as a clean register; can do cnot to assign value
* if s register is passed in as a dirty register, then this step uncompte s[j]
********************************************************************************/
CNOT( c2[cn],s[1]);
/********************************
* Uncompute process: c2 register
********************************/
for(j = cn; j > 0; j--)
{
Toffoli( c2[j],s1[j],c2[j+1]);
}
CNOT( c1[cn],c2[0]);
/****************************************
* Uncompute process: c1 register and s1
* Run the process backward to uncompute
****************************************/
for(j = cn-1; j > -1; j--)
{
EvaluateOR(tmp[0], y[j], c1[j]);
EvaluateOR(tmp[1], tmp[0], x[j]);
// uncompute s1[j]
CNOT( tmp[1],s1[j]);
// uncompute tmp[0], tmp[1] and offset NOT operation imposed by EvaluateOR
InvEvaluateOR(tmp[1], tmp[0], x[j]);
InvEvaluateOR(tmp[0], y[j], c1[j]);
Toffoli( c1[j], y[j],tmp[0]);
CNOT( tmp[0],c1[j+1]);
// uncompute tmp[0]
Toffoli( c1[j], y[j],tmp[0]);
Toffoli( c1[j], x[j],tmp[0]);
CNOT( tmp[0],c1[j+1]);
// uncompute tmp[0]
Toffoli( c1[j], x[j],tmp[0]);
// c1[j+1] uncomputed; no need to worry about c1[0] because it has never been changed
Toffoli( y[j], x[j],c1[j+1]);
}
}
/**************************************************************
* Algorithm O-8: MUL(qbit x[cn], qbit y[cn], qbit p[cn])
* Para: x: qbit[cn]
* y: qbit[cn]
* p: qbit[cn] (suppose to be clean to be passed in)
* notice that cn and n are defined globally
**************************************************************/
scaff_module MUL(qbit x[cn], qbit y[cn], qbit p[cn])
{
qbit tmp[cn];
qbit wrk[cn];
qbit wrk2[cn];
int i = 0;
int j = 0;
int k = 0;
for(j = 0; j < cn; j++)
{
/**************************************************************************************************************************
* In my case, I always pass in clean p array to do the computation, hence, do not need to worry about setting bits to zero
***************************************************************************************************************************/
PrepZ(p[j],0);
CNOT( y[j],tmp[j]);
}
for(k = 0; k < cn; k++)
{
/************************************************
* Use the if, else if, else: provided by Scaffold
************************************************/
//if(x[k]==1) // ajavadia: converted controlled circuit to controlled unitaries
//{
C_ADD(p, tmp, wrk, x[k]);
/**************************************************************************************************************
* uncompute p back to all 0 register
* wrk2 remains as all 0 throughout the whole process
* Idea (at the checkpoint): because when k = 0, we have p = 0, wrk = 0;
* when k = 1; p = tmp, wrk = 2tmp; so, do ADD(wrk2, tmp, p) to clean up p
* when k = 2, p = 2tmp, wrk = 3tmp, so do ADD(wrk2, tmp, p) two times to clean up p (logically this should work)
****************************************************************************************************************/
for(i = 0; i < k; i++)
{
C_ADD(wrk2, tmp, p, x[k]);
}
for(j = 0; j < cn; j++)
{
/************************************************
* swap to assign the computed value to p
* also have wrk back to all 0
*************************************************/
Toffoli( x[k], wrk[j],p[j]);
Toffoli( x[k], p[j],wrk[j]);
Toffoli( x[k], wrk[j],p[j]);
}
//}
for(j = 0; j < cn-1; j++)
{
/***********************************************************
* 3 CNOT is a swap
************************************************************/
CNOT( tmp[j],tmp[cn-1]);
CNOT( tmp[cn-1],tmp[j]);
CNOT( tmp[j],tmp[cn-1]);
}
}
/**************************************************************************
* Uncompute Process: roll back tmp register as wrk was already uncomputed
***************************************************************************/
for(k = cn-1; k > -1 ; k--)
{
for(j = cn-2; j > -1; j--)
{
/******************************************
* swap again to be back to original value
*******************************************/
CNOT( tmp[j],tmp[cn-1]);
CNOT( tmp[cn-1],tmp[j]);
CNOT( tmp[j],tmp[cn-1]);
}
}
for(j = cn-1; j > -1; j--)
{
CNOT( y[j],tmp[j]);
}
}
/*******************************************************************************
* Algorithm O-8: unMUL(qbit x[cn], qbit y[cn], qbit p[cn])
* Para: x: qbit[cn]
* y: qbit[cn]
* p: qbit[cn] (suppose to be dirty to be passed in)
* notice that cn and n are defined globally
* The idea is similar to ADD in a sense that if we do this process again
* we can reset the dirty bits of p back to 0. However, we need to
* have an extra local register tp to behave as the clean p in MUL scaff_module
* then use the result in tp to reset p. And the final stage of the iteration
* needs to be a bit different in order to uncompute all registers.
*********************************************************************************/
scaff_module unMUL(qbit x[cn], qbit y[cn], qbit p[cn])
{
qbit tmp[cn];
qbit wrk[cn];
qbit tp[cn];
qbit wrk2[cn];
int i = 0;
int j = 0;
int k = 0;
for(j = 0; j < cn; j++)
{
CNOT( y[j],tmp[j]);
}
for(k = 0; k < cn; k++)
{
/************************************************
* Use the if, else if, else: provided by Scaffold
************************************************/
// if(x[k]==1) // ajavadia: converted controlled circuit to controlled unitaries
// {
C_ADD(tp, tmp, wrk, x[k]);
if(k!= cn-1)
{
/****************************************************
* uncompute tp back to all 0 register
* same reasoning as given in MUL scaff_module
****************************************************/
for(i = 0; i < k; i++)
{
C_ADD(wrk2, tmp, tp, x[k]);
}
for(j = 0; j < cn; j++)
{
/************************************************
* swap to assign the computed value to tp
* also have wrk back to all 0
*************************************************/
Toffoli( x[k], wrk[j],tp[j]);
Toffoli( x[k], tp[j],wrk[j]);
Toffoli( x[k], wrk[j],tp[j]);
/**********************************************
* Now we can use tp to reset p
* tp can be used and then cleaned up in next iteration
***********************************************/
Toffoli( x[k], tp[j],p[j]);
}
}
/**********************************************************************************************************
* Uncomputation process is a bit different in the order where the blocks of code appear
* at the final bit such that we can get every register back to all zero state
***********************************************************************************************************/
else
{
for(j = 0; j < cn; j++)
{
/*********************************************
* Now we can directly use wrk to reset p since
* we do not need tp register after this iteration
*********************************************/
Toffoli( x[k], wrk[j],p[j]);
}
/************************************
* uncompute wrk back to all 0
************************************/
C_ADD(tp, tmp, wrk, x[k]);
/****************************************************
* uncompute tp back to all 0 register
* same reasoning as given in MUL scaff_module
****************************************************/
for(i = 0; i < k; i++)
{
C_ADD(wrk2, tmp, tp, x[k]);
}
}
// }
for(j = 0; j < cn-1; j++)
{
/***********************************************************
* 3 CNOT is a swap
************************************************************/
CNOT( tmp[j],tmp[cn-1]);
CNOT( tmp[cn-1],tmp[j]);
CNOT( tmp[j],tmp[cn-1]);
}
}
/**************************************************************************
* Uncompute Process: roll back : tmp register as wrk was already uncomputed
***************************************************************************/
for(k = cn-1; k > -1 ; k--)
{
for(j = cn-2; j > -1; j--)
{
/******************************************
* swap again to be back to original value
*******************************************/
CNOT( tmp[j],tmp[cn-1]);
CNOT( tmp[cn-1],tmp[j]);
CNOT( tmp[j],tmp[cn-1]);
}
}
for(j = cn-1; j > -1; j--)
{
CNOT( y[j],tmp[j]);
}
}
/**************************************************************
* Algorithm O-4: Pow17(qbit x[cn], qbit x17[cn], qbit flg[1])
* Para: x: qbit[cn]
* y: qbit[cn]
* flg[1]: qbit of size 1 used for determing for computing or uncomputing
**************************************************************/
scaff_module Pow17(qbit x[cn], qbit x17[cn], qbit flg)
{
/************************************************************************
* Clean registers to be passed to MUL for computation when flg[0] is 0.
* By doing so, we do not have to force setting dirty registers
* back to 0 in MUL, which is important because if we do the enforcement,
* entanglement might occur and it might result in irreversible scaff_modules
**************************************************************************/
qbit w[cn];
qbit alpha[cn];
qbit beta[cn];
qbit gamma[cn];
/***************************************************************************
* x17 is clean when Pow17 is summoned in EdgeORACLE scaff_module with flg[0] = 0
* But we want it to remain clean till the very last function call
* in Pow17. The reason for this is because
* at MUL, the first prcoess is forcing the 3rd parameter to 0. We do
* not want to lose information or cause un-necessary entanglement.
* When flg[0] = 1, it means we want to uncompute x17 (as it is dirty when passed in).
****************************************************************************/
MUL(x,x,alpha);
// w is clean
MUL(alpha, alpha, w);
// beta is clean
MUL(w,w,beta);
// gamma is clean
MUL(beta, beta, gamma);
/*****************************************************************
* Use the if , else if and else flow control provided by Scaffold
******************************************************************/
//if(flg[0] == 0)
//{
// finally got the value back to x17 ; x17 is clean
C_MUL(gamma,x,x17,flg);
//}
X(flg);
//else
//{
// x17 needs to be uncomputed
C_unMUL(gamma,x,x17,flg);
//}
/*******************************************************
* Uncompute process: gamma, beta, w and alpha registers
********************************************************/
unMUL(beta, beta, gamma);
unMUL(w,w,beta);
unMUL(alpha, alpha, w);
unMUL(x,x,alpha);
}
/**************************************************************
* Algorithm O-5: MOD3(qbit x[cn], qbit m[2])
* Para: x: qbit[cn] (array of size cn)
* m: qbit[2] (array of size 2)
* Return:
**************************************************************/
scaff_module MOD3(qbit x[cn], qbit m[2])
{
/***********************
* workspace registers
***********************/
int j = 0;
qbit s3[3];
qbit s5[5];
qbit tmp[3];
/******************************************************************
* Initialize s5; assume when array is instantiated, all values are 0
* s5[4] does not need to be changed
*******************************************************************/
for(j = 0; j < 4; j++)
{
X(s5[j]);
}
/************************************************************
* 2^i = (-1)^i mod 3 add or subtract 1 from s5
************************************************************/
for(j = 0; j< cn-1; j++)
{
/*****************************************************************
* Use the if , else if and else flow control provided by Scaffold
******************************************************************/
// if(x[j]==1)
// {
// I think it would be nice to write a scaff_module to do this repetitive procedure
// compute s5[4]
C_Toffoli(tmp[0], s5[2], s5[3], x[j]);
C_Toffoli(tmp[1], s5[1], tmp[0], x[j]);
C_Toffoli(tmp[2], s5[0], tmp[1], x[j]);
Toffoli( x[j], tmp[2],s5[4]);
//uncompute tmp array
C_Toffoli(tmp[2], s5[0], tmp[1], x[j]);
C_Toffoli(tmp[1], s5[1], tmp[0], x[j]);
C_Toffoli(tmp[0], s5[2], s5[3], x[j]);
// compute s5[3]
C_Toffoli(tmp[0], s5[1], s5[2], x[j]);
C_Toffoli(tmp[1], s5[0], tmp[0], x[j]);
Toffoli( x[j], tmp[1],s5[3]);
//uncompute tmp array
C_Toffoli(tmp[1], s5[0], tmp[0], x[j]);
C_Toffoli(tmp[0], s5[1], s5[2], x[j]);
// compute s5[2]
C_Toffoli(tmp[0], s5[0], s5[1], x[j]);
Toffoli( x[j], tmp[0],s5[2]);
// uncompute tmp array
C_Toffoli(tmp[0], s5[0], s5[1], x[j]);
Toffoli( x[j], s5[0],s5[1]);
CNOT( x[j],s5[0]);
// }
//if(x[j+1] == 1)
//{
CNOT( x[j+1],s5[0]);
Toffoli( x[j+1], s5[0],s5[1]);
// compute s5[2]
C_Toffoli(tmp[0], s5[0], s5[1], x[j+1]);
Toffoli( x[j+1], tmp[0],s5[2]);
// uncompute tmp array
C_Toffoli(tmp[0], s5[0], s5[1], x[j+1]);
// compute s5[3]
C_Toffoli(tmp[0], s5[1], s5[2], x[j+1]);
C_Toffoli(tmp[1], s5[0], tmp[0], x[j+1]);
Toffoli( x[j+1], tmp[1],s5[3]);
//uncompute tmp array
C_Toffoli(tmp[1], s5[0], tmp[0], x[j+1]);
C_Toffoli(tmp[0], s5[1], s5[2], x[j+1]);
// compute s5[4]
C_Toffoli(tmp[0], s5[2], s5[3], x[j+1]);
C_Toffoli(tmp[1], s5[1], tmp[0], x[j+1]);
C_Toffoli(tmp[2], s5[0], tmp[1], x[j+1]);
Toffoli( x[j+1], tmp[2],s5[4]);
//uncompute tmp array
C_Toffoli(tmp[2], s5[0], tmp[1], x[j+1]);
C_Toffoli(tmp[1], s5[1], tmp[0], x[j+1]);
C_Toffoli(tmp[0], s5[2], s5[3], x[j+1]);
//}
j++;
}
// 0 <= s5<= 30; m = s5 mod 3
// set s3 to 3 and similary reduce s5
/******************************************************************
* Initialize s3; assume when array is instantiated, all values are 0
* s3[2] does not need to be changed
*******************************************************************/
for(j = 0; j < 2; j++)
{
X(s3[j]);
}
for(j = 0; j < 4; j++)
{
/***********************************************
* Use if else if and else provided by scaffold
************************************************/
//if(s5[j] == 1)
//{
C_Toffoli(tmp[0], s3[0], s3[1], s5[j]);
Toffoli( s5[j], tmp[0],s3[2]);
// uncompute tmp[0]
C_Toffoli(tmp[0], s3[0], s3[1], s5[j]);
Toffoli( s5[j], s3[0],s3[1]);
CNOT( s5[j],s3[0]);
//}
/**********************************************************************
* ASK: GFI used s3[j+1] == 1, is it a typo? If s3, out of bound easily
* I used s5
***********************************************************************/
//if(s5[j+1] == 1)
//{
CNOT( s5[j+1],s3[0]);
Toffoli( s5[j+1], s3[0],s3[1]);
C_Toffoli(tmp[0], s3[0], s3[1], s5[j+1]);
Toffoli( s5[j+1], tmp[0],s3[2]);
// uncompute tmp[0]
C_Toffoli(tmp[0], s3[0], s3[1], s5[j+1]);
//}
j++;
}
/******************************************
* s3 = s3 + 1
******************************************/
//if(s5[4] == 1)
//{
C_Toffoli(tmp[0], s3[0], s3[1], s5[4]);
Toffoli( s5[4], tmp[0],s3[2]);
// uncompute tmp[0]
C_Toffoli(tmp[0], s3[0], s3[1], s5[4]);
Toffoli( s5[4], s3[0],s3[1]);
CNOT( s5[4],s3[0]);
//}
/******************************************
* m = s3 mod 3
******************************************/
//if(s3[2] == 1)
//{
/**********************************************************************************
* ASK: (s3[1] bitadd s3[1] bitadd 1) in GFI
* It seems the formula is not working. eg. use 111
* Answer should be 100 but the code in GFI would be 110
* I think it should be (remember in this case s3[2] is 1 to begin with)
* s3[1] = s3[1] bitadd s3[0]
* s3[0] = s3[0] bitadd 1
************************************************************************************/
Toffoli( s3[2], s3[0],s3[1]);
CNOT( s3[2],s3[0]);
//}
/*****************************************************************************************
* m is of type qbit[2] and when it is passed into this scaff_module, it is either u3 or v3
* their value (at the moment of being passed in) is still the instantiated value (i.e. 00)
* Hence, it is ok to assign via cnot for assignment.
* However, if the values of v3, u3 are dirty, doing this would reset the dirty bits back to 00
******************************************************************************************/
CNOT( s3[0],m[0]);
CNOT( s3[1],m[1]);
/******************************************************
* Uncompute Process:
* In general, it is Just running the circuit backward
*******************************************************/
/******************************************
* m = s3 mod 3 reverse
******************************************/
//if(s3[2] == 1)
//{
CNOT( s3[2],s3[0]);
Toffoli( s3[2], s3[0],s3[1]);
//}
/******************************************
* s3 = s3 + 1 reverse
******************************************/
//if(s5[4] == 1)
//{
CNOT( s5[4],s3[0]);
Toffoli( s5[4], s3[0],s3[1]);
C_Toffoli(tmp[0], s3[0], s3[1], s5[4]);
Toffoli( s5[4], tmp[0],s3[2]);
// uncompute tmp[0]
C_Toffoli(tmp[0], s3[0], s3[1], s5[4]);
//}
/*********************************
* reverse process
**********************j************/
for(j = 3; j > -1; j--)
{
/***********************************************
* Use if else if and else provided by scaffold
************************************************/
/**********************************************************************
* ASK: GFI used s3[j+1] == 1, is it a typo? If s3, out of bound easily
* I used s5
***********************************************************************/
//if(s5[j+1] == 1)
//{
C_Toffoli(tmp[0], s3[0], s3[1], s5[j+1]);
Toffoli( s5[j+1], tmp[0],s3[2]);
// uncompute tmp[0]
C_Toffoli(tmp[0], s3[0], s3[1], s5[j+1]);
Toffoli( s5[j+1], s3[0],s3[1]);
CNOT( s5[j+1],s3[0]);
//}
//if(s5[j] == 1)
//{
CNOT( s5[j],s3[0]);
Toffoli( s5[j], s3[0],s3[1]);
C_Toffoli(tmp[0], s3[0], s3[1], s5[j]);
Toffoli( s5[j], tmp[0],s3[2]);
// uncompute tmp[0]
C_Toffoli(tmp[0], s3[0], s3[1], s5[j]);
//}
j--;
}
/******************************************************************
* reverse the assignment for s3 @ line 25-27 in GFI
*******************************************************************/
for(j = 0; j < 2; j++)
{
X(s3[j]);
}
/************************************************************
* uncompute for line 8-20 in GFI
************************************************************/
for(j = cn-2; j>-1; j--)
{
/*****************************************************************
* Use the if , else if and else flow control provided by Scaffold
******************************************************************/
//if(x[j+1] == 1)
//{
// compute s5[4]
C_Toffoli(tmp[0], s5[2], s5[3], x[j+1]);
C_Toffoli(tmp[1], s5[1], tmp[0], x[j+1]);
C_Toffoli(tmp[2], s5[0], tmp[1], x[j+1]);
Toffoli( x[j+1], tmp[2],s5[4]);
//uncompute tmp array
C_Toffoli(tmp[2], s5[0], tmp[1], x[j+1]);
C_Toffoli(tmp[1], s5[1], tmp[0], x[j+1]);
C_Toffoli(tmp[0], s5[2], s5[3], x[j+1]);
// compute s5[3]
C_Toffoli(tmp[0], s5[1], s5[2], x[j+1]);
C_Toffoli(tmp[1], s5[0], tmp[0], x[j+1]);
Toffoli( x[j+1], tmp[1],s5[3]);
//uncompute tmp array
C_Toffoli(tmp[1], s5[0], tmp[0], x[j+1]);
C_Toffoli(tmp[0], s5[1], s5[2], x[j+1]);
// compute s5[2]
C_Toffoli(tmp[0], s5[0], s5[1], x[j+1]);
Toffoli( x[j+1], tmp[0],s5[2]);
// uncompute tmp array
C_Toffoli(tmp[0], s5[0], s5[1], x[j+1]);
Toffoli( x[j+1], s5[0],s5[1]);
CNOT( x[j+1],s5[0]);
//}
//if(x[j]==1)
//{
CNOT( x[j],s5[0]);
Toffoli( x[j], s5[0],s5[1]);
// compute s5[2]
C_Toffoli(tmp[0], s5[0], s5[1], x[j]);
Toffoli( x[j], tmp[0],s5[2]);
// uncompute tmp array
C_Toffoli(tmp[0], s5[0], s5[1], x[j]);
// compute s5[3]
C_Toffoli(tmp[0], s5[1], s5[2], x[j]);
C_Toffoli(tmp[1], s5[0], tmp[0], x[j]);
Toffoli( x[j], tmp[1],s5[3]);
//uncompute tmp array
C_Toffoli(tmp[1], s5[0], tmp[0], x[j]);
C_Toffoli(tmp[0], s5[1], s5[2], x[j]);
C_Toffoli(tmp[0], s5[2], s5[3], x[j]);
C_Toffoli(tmp[1], s5[1], tmp[0], x[j]);
C_Toffoli(tmp[2], s5[0], tmp[1], x[j]);
Toffoli( x[j], tmp[2],s5[4]);
//uncompute tmp array
C_Toffoli(tmp[2], s5[0], tmp[1], x[j]);
C_Toffoli(tmp[1], s5[1], tmp[0], x[j]);
C_Toffoli(tmp[0], s5[2], s5[3], x[j]);
//}
j--;
}
}
/**************************************************************
* Algorithm O-1: ORACLE
* Para: u a qbit array of size n
* v a qbit array of size n
* edge a qbit; is 1 when u and v are connected
**************************************************************/
scaff_module EdgeORACLE(qbit u[], int uoffset, qbit v[], int voffset, qbit edge)
{
int i;
// local quantum workspace registers
qbit uint[cn];
qbit vint[cn];
qbit u17[cn];
qbit v17[cn];
qbit u3[2];
qbit v3[2];
qbit t[1];
qbit uF[1];
qbit vF[1];
qbit uH[1];
qbit vH[1];
qbit diffuvH[1];
qbit uv3[1];
qbit uvF[1];
qbit diffuvF[1];
qbit equalbit[2];
qbit flg[1];
/*************************************************************
* This array is basically used to do the statement flow control
* location at 0 is for "NOT t[0]"
***************************************************************/
qbit ctrcentr[n];
int hn = N/2;
// initializing the values
PrepZ(edge,0);
PrepZ(t[0],0);
PrepZ(uF[0],0);
PrepZ(vF[0],0);
PrepZ(uH[0],0);
PrepZ(vH[0],0);
PrepZ(diffuvH[0],0);
PrepZ(uv3[0],0);
PrepZ(uvF[0],0);
PrepZ(diffuvF[0],0);
PrepZ(flg[0],0);
for(i = 0; i < 2; i++)
{
PrepZ(equalbit[i],0);
}
for(i = 0; i < n ; i++)
{
PrepZ(ctrcentr[i],0);
}
ConvertNode(u, uoffset, uint, hn);
ConvertNode(v, voffset, vint, hn);
TestEqual(uint, vint, t[0]);
Pow17(uint, u17, flg[0]);
Pow17(vint, v17, flg[0]);
TestEqual(uint, u17, uF[0]);
TestEqual(vint, v17, vF[0]);
/**************************************************************************
* Assigned value of u17[cn-1] to uH[0] (same for v17 and vH)
***************************************************************************/
CNOT( u17[cn-1],uH[0]);
CNOT( v17[cn-1],vH[0]);
/***************************************
* MOD3 operation takes place
****************************************/
MOD3(u17, u3);
MOD3(v17, v3);
/********************************
* uvF[0] = uF[0] AND vF[0]
*********************************/
Toffoli( vF[0], uF[0],uvF[0]);
/*********************************************************************
* diffuvF[0] = 1 iff uF and vF are of different value
***********************************************************************/
CNOT( uF[0],diffuvF[0]);
CNOT( vF[0],diffuvF[0]);
/***************************************************************
* test if u3 and v3 are equal, result is stored in equalbit[0]
****************************************************************/
equalquInt2(u3, v3, equalbit[0]);
/********************************
* diffuvH[0] = (uH[0] != vH[0])
*********************************/
CNOT( vH[0],diffuvH[0]);
CNOT( uH[0],diffuvH[0]);
/***************************************************************
* test if u3 != v3, result is stored in equalbit[1]
****************************************************************/
CNOT( equalbit[0],equalbit[1]);
X(equalbit[1]);
/*************************************************************
* Flow control: Start
**************************************************************/
CNOT( t[0],ctrcentr[0]);
X(ctrcentr[0]);
/*******************************************************************************************
* First level
* t[0] = 1 : Do nothing here since edge is initialized in 0
* t[0] = 0 : Do nothing as well since we need edge to remain 0 for next level if statement
*******************************************************************************************/
/*************************************************************************************
* Second level
* Need t[0] = 0 (i.e. ctrcentr[0] =1) and uvF[0] = 1
**************************************************************************************/
Toffoli( uvF[0], ctrcentr[0],edge);
/****************************************************************************************
* 3rd level
* Need t[0] = 0 (i.e. ctrcentr[0] = 1), diffuvF[0] = 1
* diffuvF[0]=1 automatically excludes the case that uvF[0] = 1 (considered in 2nd level)
****************************************************************************************/
Toffoli( diffuvF[0], ctrcentr[0],ctrcentr[1]);
/******************************************
* edge[0] = 1 iff equalbit[0] = 1 (determined by u3 = v3) and ctrcentr[1] = 1
*******************************************/
Toffoli( equalbit[0], ctrcentr[1],edge);
/*************************************************************************
* If above condition is not fullfilled, should return 0
* For now, let us leave edge[0] unchanged as it is still 0 at this moment
* because we are in level 3 but the u3==v3 is not satisfied
* and in next level this value would not be touched because we condition
* on X(uvF[0]) at next level.
*************************************************************************/
/****************************************************************************
* 4th level: clearly this is the case when uF = vF = 0 because
* in level 2 and level 3, we have 3 cases (11, 01, 10) out of four considered
*******************************************************************************/
X(uvF[0]);
X(diffuvF[0]);
// the 00 case
Toffoli( diffuvF[0], uvF[0],ctrcentr[2]);
// u3!= v3 AND uH!=vH
Toffoli( diffuvH[0], equalbit[1],ctrcentr[3]);
// t[0] = 0 (i.e. ctrcentr[0] = 1) must be satsified (the original level one condition)
Toffoli( ctrcentr[3], ctrcentr[0],ctrcentr[4]);
CNOT( ctrcentr[4],edge);
/**********************************************************************
* Uncompute Process
**********************************************************************/
/****************************
* Level 1 - 4 uncomputation
*****************************/
Toffoli( ctrcentr[3], ctrcentr[0],ctrcentr[4]);
Toffoli( diffuvH[0], equalbit[1],ctrcentr[3]);
Toffoli( diffuvF[0], uvF[0],ctrcentr[2]);
X(diffuvF[0]);
X(uvF[0]);
Toffoli( diffuvF[0], ctrcentr[0],ctrcentr[1]);
X(ctrcentr[0]);
CNOT( t[0],ctrcentr[0]);
/***********************************
* uncompute equalbit[1]
************************************/
X(equalbit[1]);
CNOT( equalbit[0],equalbit[1]);
/********************************
* uncompute diffuvH[0]
*********************************/
CNOT( vH[0],diffuvH[0]);
CNOT( uH[0],diffuvH[0]);
/***************************************************************
* uncompute equalbit[0]
****************************************************************/
equalquInt2(u3, v3, equalbit[0]);
/*********************************************************************
* uncompute diffuvF[0]
***********************************************************************/
CNOT( uF[0],diffuvF[0]);
CNOT( vF[0],diffuvF[0]);
/********************************
* uncompute uvF[0]
*********************************/
Toffoli( vF[0], uF[0],uvF[0]);
/**********************************
* Undo u3, v3 by doing MOD3 again
***********************************/
MOD3(u17, u3);
MOD3(v17, v3);
/*************************
* undo uH[0] , vH[0]
**************************/
CNOT( u17[cn-1],uH[0]);
CNOT( v17[cn-1],vH[0]);
/*************************************************************************************************
* uncompute uF, vF : same reasoning because doing TestEqual again would reset uF and vF back to 0
**************************************************************************************************/
TestEqual(uint, u17, uF[0]);
TestEqual(vint, v17, vF[0]);
/*******************************************
* uncompute u17, v17, then uncompute flg[0]
********************************************/
X(flg[0]);
Pow17(uint, u17, flg[0]);
Pow17(vint, v17, flg[0]);
X(flg[0]);
/*******************************************************************************************************
* Uncompute vint, uint: same reasoning. Running ConvertNode again will uncompute uint and vint back to 0
* since we are passing the same parameter (but uint and vint). Please see the explanation in scaff_module SUB
*******************************************************************************************************/
ConvertNode(u, uoffset, uint, hn);
ConvertNode(v, voffset, vint, hn);
}
