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(".") ); } } |