|
Chris Pollett > Students > Yunxuan
[Bio] [Blog] [Final Step of Shor's and Grover's Algorithms] [Threshold of Error Correction] [Random-kSAT-Generator: Version 1] [Random-kQSAT-Generator: Version 2] [Random-kQSAT-Generator: Version 3] [Antiferromagnetic Heisenberg Model] [Random-kQSAT-Generator: Version 4] [Random-kQSAT-Generator: Version 5] [Random-kQSAT-Generator: Version 6] [Thesis] |
In the Deutch Josza problem, we are give a function, which we are promised is either balanced or uniform. If the function is balanced, it returns 0 for exactly half of times and 1 for the half of the times. If the function is uniform, it returns 0 or 1 all of the times. To determine if a function is balanced, the worst case scenario means we have to query, (2^n)/2+1 times. The output of the algorithm is 0 if the function is uniform and some other integer if the algorithm is balanced. In this code of that I programmed in java, the methods evaluate() and analyze(), were copy and pasted from jQuantum quantum simulator source code.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import static java.lang.Math.*;
import java.io.*;
public class DeutchJosza {
public int xStateMax;
public int yStateMax;
public static final String[] constantName = {"PI", "pi", "E", "e"};
public static final double[] constantValue = { PI , PI, E, E };
public static int maxOpLength = 6;
public String [] myfunction;
public int output;
public static void main (String [] args){
DeutchJosza dj = new DeutchJosza();
System.out.println("Three rules regarding input:");
System.out.println("1. This program ignores the order of operation"
+ " you must use brackets to indicate which operations you"
+ " want to do first if the analysis you want is not"
+ " simply from left to right.");
System.out.println("2. This program does not allow negative numbers "
+ "and all negative numbers generated in the process of "
+ "calculation will be treated as positive.");
System.out.println("3.Becareful of singularities in the function i.e. at 0.");
String line="";
System.out.println("Enter f(x,y) for the Deutch Josza algorithm->");
try{
BufferedReader in = new BufferedReader (new InputStreamReader(System.in));
line = in.readLine();
}catch(Exception ex){
System.out.println("Bad Input");
}
System.out.println(dj.Deutch(2, 3, line));
int xsize=0, ysize=0;
String str="";
System.out.println("Enter number of qubits in x-register->");
try{
BufferedReader in = new BufferedReader (new InputStreamReader(System.in));
xsize = Integer.parseInt(in.readLine());
}catch(Exception ex){
System.out.println("Bad Input");
}
System.out.println("Enter number of qubits in y-register->");
try{
BufferedReader in = new BufferedReader (new InputStreamReader(System.in));
ysize = Integer.parseInt(in.readLine());
}catch(Exception ex){
System.out.println("Bad Input");
}
System.out.println("Enter function bit string->");
try{
BufferedReader in = new BufferedReader (new InputStreamReader(System.in));
str= in.readLine();
}catch(Exception ex){
System.out.println("Bad Input");
}
System.out.println(dj.Deutch2(xsize, ysize,str));
//System.out.println(dj.Deutch2(3, 3,"10101010101010101010101010101010101010101010101010101010101010101" ));//output=1*/
}
public int Deutch2 (int xsize, int ysize, String function){
double [] x = {xsize,2};
double [] y = {ysize,2};
xStateMax = (int) evaluate (x,"pow");
yStateMax = (int) evaluate (y,"pow");
int [] values = new int [xStateMax*yStateMax];
int measured=0;
int factor=0;
int [] multiples= new int [xStateMax*yStateMax];
for(int i=0; i<xStateMax; i++){
for (int j=0; j<yStateMax; j++){
if (i*yStateMax+j<function.length()){
values[i*yStateMax+j]=(int) function.charAt(i*yStateMax+j);
}else {
break;
}
if (i*yStateMax+j>=function.length())
break;
}
}
if (function.length()<xStateMax*yStateMax){
System.out.println(function.length()+" "+xStateMax*yStateMax);
for (int k=function.length(); k<xStateMax*yStateMax;k++){
values[k]=0;
System.out.print(values[k]);
}
}
for (int k=0; k<xStateMax*yStateMax; k++){
for(int i=0; i<xStateMax; i++){
for (int j=0; j<yStateMax; j++){
factor = (int)(values[i*yStateMax+j]+ dotProduct((i*yStateMax+j),k));
double [] y2 = new double [2];
y2[0]=factor;
y2[1]=-1;
factor = (int) evaluate(y2,"pow");
multiples[k]+=factor;
}
}
}
for (int k=0; k<xStateMax*yStateMax; k++){
if (multiples[k]<0){
multiples[k]*=-1;
}
if (multiples[k]>=multiples[measured])
measured=k;
}
//System.out.println(measured);
return measured;
}
public int Deutch(int xSize, int ySize, String function){
double [] x = {xSize,2};
double [] y = {ySize,2};
xStateMax = (int) evaluate (x,"pow");
yStateMax = (int) evaluate (y,"pow");
myfunction = analyse (function);
double [][] values = new double [xStateMax][yStateMax];
String str = "";
int measured=0;
int functionvalue=0;
int factor=0;
int []multiples= new int [xStateMax*yStateMax];
String myfunc=function;
for(int i=0; i<xStateMax; i++){
for (int j=0; j<yStateMax; j++){
function = function.replace("x", ""+i);
function = function.replace("y", ""+j);
values[i][j]=solve(function);
function = myfunc;
}
}
for (int k=0; k<xStateMax*yStateMax; k++){
for(int i=0; i<xStateMax; i++){
for (int j=0; j<yStateMax; j++){
factor = (int)(values[i][j]+ dotProduct((i*yStateMax+j),k));
double [] y2 = new double [2];
y2[0]=factor;
y2[1]=-1;
factor = (int) evaluate(y2,"pow");
multiples[k]+=factor;
}
}
}
for (int k=0; k<xStateMax*yStateMax; k++){
if (multiples[k]<0){
multiples[k]*=-1;
}
if (multiples[k]>=multiples[measured])
measured=k;
}
return measured;
}
public int dotProduct (int x, int z){
int product=0;
double [] x1 = new double [2];
double [] y1 = new double [2];
x1[1]=(double)x;
x1[0]=2.0;
y1[1]=(double)z;
y1[0]=2.0;
int xdigit=(int)evaluate(x1,"mod");
int zdigit=(int)evaluate(y1,"mod");
while (x>0 && z>0){
if (xdigit==zdigit){
product=product+1;
}
x = x>>1;
int temp4 = x;
x1[1]=(double) temp4;
x1[0]=2.0;
xdigit= (int) evaluate(x1,"mod");
z = z>>1;
temp4 = z;
y1[1]=(double) temp4;
y1[0]=2.0;
zdigit= (int) evaluate(y1,"mod");
}
return product;
}
public double solve (String function){
int start=0;
int end = 0;
String temp="";
String innerfunction="";
String[] parsed;
boolean simplest= false;
double answer=0.0;
boolean unary=false;
boolean binary=false;
boolean ternary=false;
boolean found=false;
String op = "";
String str2="";
parsed = analyse(function);
if (parsed.length==1){
return Double.parseDouble(parsed[0]);
}
for (int k=0; k<parsed.length; k++){
for (int j1=0; j1<operator[1].length;j1++){
if (parsed[k].equals(operator[1][j1])){
unary=true;
op = parsed[k];
}
}
for (int j2=0; j2<operator[2].length;j2++){
if (parsed[k].equals(operator[2][j2])){
binary=true;
op = parsed[k];
}
}
for (int j3=0; j3<operator[3].length;j3++){
if (parsed[k].equals(operator[3][j3])){
ternary=true;
op = parsed[k];
}
}
}
if (unary || binary || ternary){
if (unary && parsed.length==2){
simplest=true;
double [] x = new double [1];
x[0]= Double.parseDouble (parsed[1]);
answer=evaluate (x,op);
return answer;
}
else if (binary && parsed.length==3){
simplest=true;
double [] x = new double [2];
x[0]= Double.parseDouble (parsed[0]);
x[1]= Double.parseDouble (parsed[2]);
answer=evaluate (x,op);
return answer;
}
else if (ternary && parsed.length==4){
simplest=true;
double [] x = new double [3];
int k3=0;
for (int k2=0; k2<parsed.length; k2++){
if (!parsed[k2].equals(op)) {
x[k3] = Double.parseDouble(parsed[k2]);
k3++;
}
}
answer=evaluate (x,op);
return answer;
}
}
int i;
if (!simplest){
for (i=1; i<parsed.length-1; i++){
if (parsed[i-1].equals("(")&& !parsed[i].equals("(")){
start=i;
}
else if (parsed[i+1].equals(")")){
end=i;
found=true;
break;
}
}
if(!found){
boolean opNotFound=true;
start=0;
for (int i2=0; opNotFound && i2<parsed.length-2; i2++){
if(isOperator(parsed[i2])&& !isOperator( parsed[i2+1])){
end=i2+1;
opNotFound=false;
}
else if (isOperator(parsed[i2])&& isOperator(parsed[i2+1])){
opNotFound=false;
double [] x = new double [1];
x[0]= Double.parseDouble (parsed[i2+2]);
answer=evaluate (x,parsed[i2+1]);
if (answer<0){
answer=answer*-1;
}
String tempstr=""+answer;
StringBuilder sb3 = new StringBuilder("");
sb3.append(parsed[i2+1]);
sb3.append(parsed[i2+2]);
function = function.replace(sb3.toString(), tempstr);
parsed=analyse(function);
end=i2+1;
}
}
}
}
StringBuilder sb = new StringBuilder("");
for(int i2=start; i2<end+1; i2++){
sb.append(parsed[i2]);
}
StringBuilder sb2 = new StringBuilder("");
double temp2 = solve(sb.toString());
if (temp2<0)temp2=-1*temp2;
sb2.append(temp2);
if (found)
str2 = "("+sb.toString()+")";
else
str2=sb.toString();
function = function.replace(str2, sb2.toString());
return solve(function);
}
private static double evaluate(double[] x, String op) {
double y = 0.0;
if (op.equals("+")) {
y = (x[1] + x[0]);
} else if (op.equals("-")) {
y = x[1] - x[0];
} else if (op.equals("*")) {
y = (x[1] * x[0]);
} else if (op.equals("/")) {
if ( x[0] != 0 && x[1] != 0 )
y = (x[1] / x[0]);
else if ( x[0] == 0 && x[1] == 0 )
y = 1;
else if ( x[1] > 0 )
y = Double.POSITIVE_INFINITY;
else
y = Double.NEGATIVE_INFINITY;
} else if (op.equals("%")) {
x[0] = (int) x[0];
x[1] = (int) x[1];
y = (x[1] % x[0]);
} else if (op.equals("mod")) {
x[0] = (int) x[0];
x[1] = (int) x[1];
if ( x[0] == 0 )
y = Double.POSITIVE_INFINITY; //??
else {
if ( x[0] < 0 )
x[0] = -x[0];
if ( x[1] >= 0 )
y = x[1] % x[0];
else if ( x[1] < 0 )
y = x[0] + x[1] % x[0];
}
} else if (op.equals("^") || op.equals("pow")) {
y = pow(x[1], x[0]);
} else if (op.equals("sin")) {
y = sin(x[0]);
} else if (op.equals("cos")) {
y = cos(x[0]);
} else if (op.equals("tan")) {
y = tan(x[0]);
} else if (op.equals("cot")) {
y = 1/tan(x[0]);
} else if (op.equals("sec")) {
y = 1/cos(x[0]);
} else if (op.equals("csc")) {
y = 1/sin(x[0]);
} else if (op.equals("asin")) {
y = asin(x[0]);
} else if (op.equals("acos")) {
y = acos(x[0]);
} else if (op.equals("atan")) {
y = atan(x[0]);
} else if (op.equals("acot")) {
y = atan(1/x[0]);
} else if (op.equals("sinh")) {
y = ( exp(x[0]) - exp(-x[0]) ) / 2;
} else if (op.equals("cosh")) {
y = ( exp(x[0]) + exp(-x[0]) ) / 2;
} else if (op.equals("tanh")) {
y = ( exp(x[0]) - exp(-x[0]) ) / ( exp(x[0]) + exp(-x[0]) );
} else if (op.equals("coth")) {
y = ( exp(x[0]) + exp(-x[0]) ) / ( exp(x[0]) - exp(-x[0]) );
} else if (op.equals("arsinh")) {
y = log( x[0] + sqrt( x[0]*x[0] + 1 ) );
} else if (op.equals("arcosh")) {
y = log( x[0] + sqrt( x[0]*x[0] - 1 ) );
} else if (op.equals("artanh")) {
y = log( (1 + x[0]) / (1 - x[0]) ) / 2;
} else if (op.equals("arcoth")) {
y = log( (x[0] + 1) / (x[0] - 1) ) / 2;
} else if (op.equals("exp")) {
y = exp(x[0]);
} else if (op.equals("ln")) {
y = log(x[0]);
} else if (op.equals("log")) {
y = log(x[0]) / log(10);
} else if (op.equals("ld")) {
y = log(x[0]) / log(2);
} else if ( op.equals("w") || op.equals("sqrt") ) {
y = sqrt(x[0]);
} else if ( op.equals("and") || op.equals("&&") || op.equals("&") ) {
y = x[1] * x[0];
} else if ( op.equals("or") || op.equals("|") ) {
y = x[1] >= x[0] ? x[1] : x[0];
} else if ( op.equals("xor") ) {
y = (x[1] + x[0]) % 2;
} else if ( op.equals("if") ) {
y = x[2] == 1 ? x[1] : x[0];
} else if ( op.equals("modPow") ) {
for (int i=(int) x[1]; i>1; i--){
x[1]*=x[0];
}
double[] x2={x[2],x[1]};
y = evaluate (x2,"mod");
} else if (op.equals("<")) {
if ( x[1] < x[0] )
y = 1;
else
y = 0;
} else if (op.equals("<=")) {
if ( x[1] <= x[0] )
y = 1; // true
else
y = 0;
} else if (op.equals(">")) {
if ( x[1] > x[0] )
y = 1;
else
y = 0;
} else if (op.equals(">=")) {
if ( x[1] <= x[0] )
y = 1;
else
y = 0;
} else if (op.equals("==") || op.equals("=") ) {
if ( x[1] == x[0] )
y = 1;
else
y = 0;
}
return y;
}
private static String[] analyse(String function) {
for ( int i = 0; i < constantName.length; i++ ) {
function = function.replaceAll( constantName[i], Double.toString(constantValue[i] ) );
}
function = function.replaceAll(", ", ";");
function = function.replaceAll(" ", "");
function = function.replace(',', '.');
function = function.replace(':', '/');
function = function.replace('[', '(');
function = function.replace(']', ')');
function = function.replace('{', '(');
function = function.replace('}', ')');
function = function.replaceAll("&&", "&");
ArrayList<String> element = new ArrayList<String>();
int j = 0;
int i = 0;
while ( i < function.length() ) {
String symbol = function.substring(i, i+1);
if ( isDigit( symbol ) ) {
int end = i;
for (int k = i+1; k < function.length(); k++) {
symbol = function.substring(k, k+1);
if ( isDigit( symbol ) ) {
end++;
} else
break;
}
if (i < end) {
element.add( function.substring(i, end+1) );
} else {
element.add( function.substring(i, i+1) );
}
} else if ( symbol.equals("(") || symbol.equals(")" ) ) {
element.add(symbol);
} else {
int opLength = 1;
boolean isOp = false;
while (
!isOp &&
(i + opLength <= function.length() ) &&
opLength <= maxOpLength
) {
symbol = function.substring( i, i + opLength );
isOp = isOperator( symbol );
opLength++;
if ( isOp && ( i + opLength <= function.length() ) ) {
String symbol2 = function.substring( i, i + opLength );
if ( isOperator( symbol2 ) ) {
symbol = symbol2;
}
}
}
if ( isOp ) {
element.add( symbol );
} else {
return null;
}
}
if ( j > 0 && ( element.get(j)).equals("-") ) {
String secondLast = element.get(j-1);
if (
secondLast.equals("(") ||
secondLast.equals("=") || secondLast.equals("==") ||
secondLast.equals("<") || secondLast.equals("<=") ||
secondLast.equals(">") || secondLast.equals(">=") ||
secondLast.equals("&") || secondLast.equals("&&") ||
secondLast.equals("|") || secondLast.equals(")") ||
secondLast.equalsIgnoreCase("and") ||
secondLast.equalsIgnoreCase("or") ||
secondLast.equalsIgnoreCase("xor")
) {
element.add(j, "0" );
j++;
}
} else if ( j == 0 && ( element.get(j) ).equals("-") ) {
element.add(0, "0" );
j++;
}
if ( j > 3 && element.get(j-1).equals("mod") && element.get(j-3).equals("^") ) {
String[] tmpOps = new String[6];
tmpOps[0] = "modPow";
tmpOps[1] = "(";
tmpOps[2] = element.get(j-4);
tmpOps[3] = element.get(j-2);
tmpOps[4] = element.get(j);
tmpOps[5] = ")";
for ( int k = 0; k < 5; k++ ) {
element.remove(j-k);
}
for ( int k = 0; k < 6; k++ ) {
element.add(j - 4 + k, tmpOps[k] );
}
j++;
i += tmpOps[4].length() - 1;
}
i += element.get(j).length();
j++;
}
String[] parsedFunction = new String[ element.size() ];
parsedFunction = element.toArray( parsedFunction );
return parsedFunction;
}
private static boolean isOperator(String string) {
boolean isOp = false;
int i = 0;
while ( !isOp && i < operator.length ) {
isOp = isOperator( i, string );
i++;
}
return isOp;
}
/** Tests whether the argument <code>string</code> is an i-nary operator.
* i=0 is a variable, i=1 a unary operator, i=2 a binary operator, i=3 a ternary operator, etc.
*/
private static boolean isOperator( int i, String string ) {
boolean isOp = false;
int j = 0;
while ( !isOp && j < operator[i].length ) {
isOp = string.equalsIgnoreCase( operator[i][j] );
j++;
}
return isOp;
}
public static final String[][] operator = {
{// variables:
"x", "y", "z"
},
{// unary operators:
"ln", "ld",
"exp", "log",
"sqrt", "w",
"sin", "cos", "tan", "cot", "sec", "csc",
"asin", "acos", "atan", "acot",
"sinh", "cosh", "tanh", "coth",
"arsinh", "arcosh", "artanh", "arcoth",
},
{// binary operators:
"+", "-", "*", "/", "%", "^", "pow", "mod",
"=", "<", ">", "==", "<=", ">=",
"&&", "|", "&", "and", "or", "xor",
";", ","
},
{// ternary operators:
"if", "modPow"
},
/*
{// quaternary operators:
"for", "sum"
}
*/
};
private static boolean isDigit( String symbol ) {
return (
symbol.equals("1") || symbol.equals("2") || symbol.equals("3") ||
symbol.equals("4") || symbol.equals("5") || symbol.equals("6") ||
symbol.equals("7") || symbol.equals("8") || symbol.equals("9") ||
symbol.equals("0") || symbol.equals(".")
);
}
}
|