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] |
This program simulates the Antiferromagnetic Heisenberg Model. Currently it only tells you whether there are any null vectors found: answer is no. But eventually, it will tell you whether there are any low energy solutions (small eigenvalue solutions). I will research online about the difficult problem of finding eigenvalues of a matrix. The professor will provide the numerical value of what is a small eigenvalue. Update 1:I added methods for finding determinants. This is how I envision, I will test for eigenvalues below the threshold: test to see if the determinant is close enough to 0. The code below crashes due to large matrix size!!!! import java.io.*; import static java.lang.Math.*; import java.util.*; public class AntiferroHeisenModel { private int clausesize = 2; private int numvariable = 6; //crashes for greater than 6 private int numclause = 4; //crashes for greater than 4 private int numinstances = 3; //crashes for greater than 3 private int success= 0; private int counter=0; private double threshold=1.5; //2.0 private int counter3=0; public static void main(String[] args) { // TODO Auto-generated method stub AntiferroHeisenModel afh = new AntiferroHeisenModel(); /* double [][] mat= {{1,2,3},{4,5,6},{7,8,9}}; double val= afh.determinant(mat); System.out.println(val);*/ afh.generate(); } public void generate(){ ArrayList<Integer>temp = new ArrayList<Integer>(); ArrayList<ArrayList<Integer>> temp2 = new ArrayList<ArrayList<Integer>>(); for (int k = 0; k<numinstances; k++) { for (int j = 0; j<numclause; j++) { temp.add(new Integer(0)); for(int i = 0; i<clausesize-1; i++){ int a = (int)(Math.random()*numvariable)+1; temp.add(new Integer(a)); } temp2.add(temp); temp = new ArrayList<Integer>(); } if(Solve(temp2)){ success++; } temp2 = new ArrayList<ArrayList<Integer>>(); counter3=0; } System.out.println(success); } public boolean nullvecExist(boolean [] x){ for(int i=0; i<x.length; i++){ if(x[i]==true){ //System.out.print(i+" "); counter3++; } } for(int i=0; i<x.length; i++){ if(x[i]==true){ return true; } } return false; } public void swaprows(double[][]matrix){ //int zerocount = 0; int max = matrix.length; double [] temp; int current = 0; double ratio = 1; boolean found = false; //current is the line number you have just fixed. //i is all the line numbers that you are working on still. //the point of this part is to order rows by increasing zero count. /*for(int i=0; i<max; i++){ System.out.print(zeroCount2(matrix[i])+" "); }*/ current=0; int currentCount=0; while(current<max){ for(int i = current; i < max; i++){ if(zeroCount2(matrix[i]) == currentCount){ temp = matrix[i]; matrix[i] = matrix[current]; matrix[current] = temp; current++; } } currentCount++; } } public boolean [] gaussianElimination(double [][]matrix){ //int zerocount = 0; int max = matrix.length; double [] temp; int current = 0; double ratio = 1; boolean found = false; boolean []sol = new boolean [matrix.length]; //int zerocount = 0; //int max = matrix.length; //double [] temp; //int current = 0; //double ratio = 1; //boolean found = false; //count is the number of zeros in the line you have //just done working on. You stop working and you increase //count when you get to a transition in the number of zeros //in your rows of the matrix. swaprows(matrix); int ind=0; int oldind=ind; int count = zeroCount2(matrix[ind]); while(ind+1<max){ //System.out.println(count); for(int i = ind+1; i<max; i++){ int c = zeroCount2(matrix[i]); if(c==count) { ratio = matrix[i][c]/matrix[count][c]; for(int w = 0; w < matrix.length; w++){ matrix[i][w]-=matrix[count][w]*ratio; } } else if(c>count){ break; } } swaprows(matrix); for(int i=0;i<max; i++){ if(zeroCount2(matrix[i])<i ){ ind=i-1; break; }else{ if(i==max-1){ ind=max-1; } } } count=zeroCount2(matrix[ind]); } /*for(int u=0; u<matrix.length; u++){ for(int w=0; w<matrix.length; w++){ System.out.print(matrix[u][w]+" "); } System.out.println(""); }*/ for(int i=0; i<sol.length; i++){ sol[i]=true; } for(int i=0; i<matrix.length; i++){ /*int count6 = zeroCount2(matrix[i]); if (Math.abs(matrix[i][count6])>threshold){ sol[count6]=false; }*/ if(Math.abs(matrix[i][i])>threshold){ sol[i]=false; } } return sol; } public int zeroCount2 (double[] vec){ int temp = 0; for(int i = 0; i < vec.length; i++){ if(vec[i]==0){ temp++; } else{ break; } } return temp; } public boolean Solve(ArrayList<ArrayList<Integer>> temp2){ //temp2 is 15 (for example) clauses. int max = (int)pow(2,numvariable); double [] alpha = new double [max]; boolean[] beta; double[][] one = new double[max][max]; double [][] two = new double[max][max]; double[][] three = new double[max][max]; double[][] Constraint = new double[max][max]; boolean success = false; /*for(int i = 0; i < max; i++){ beta[i] = false; }*/ for(int i=0; i<temp2.size(); i++){ ArrayList<Integer> list = temp2.get(i); String path = makeString(list); one = makeSig(1,path); //z two = makeSig(2, path); //y three = makeSig(3, path); //x for(int k=0; k<max; k++){ for(int s=0; s<max; s++){ Constraint[k][s]+=(one[k][s]-two[k][s]+three[k][s]); } } } /*double det = determinant(Constraint); //System.out.println("det "+det); if(Math.abs(det)<threshold){ success=true; }*/ boolean [] x= gaussianElimination(Constraint); /*for(int j = 0; j < Constraint.length; j++){ for(int k = 0; k < Constraint.length; k++){ System.out.print(Constraint[j][k]+" "); } System.out.println(""); }*/ success = nullvecExist(x); return success; } public int countZero(double[]alpha){ int count=0; for(int i=0; i<alpha.length; i++){ if(alpha[i]!=0){ break; } count++; } return count; } public double[][] makeSig (int type, String path){ char next; double a0, a1, a2, a3; double[][]ul,ur,ll,lr; double [][] orig = new double[2][2]; if(path.charAt(path.length()-1)=='I'){ orig[0][0]=1; orig[0][1]=0; orig[1][0]=0; orig[1][1]=1; }else { if(type==1){ orig[0][0]=1; orig[0][1]=0; orig[1][0]=0; orig[1][1]=-1; }else if(type==2){ orig[0][0]=0; orig[0][1]=-1; orig[1][0]=1; orig[1][1]=0; }else { orig[0][0]=0; orig[0][1]=1; orig[1][0]=1; orig[1][1]=0; } } for(int i=path.length()-2; i>=0; i--){ next = path.charAt(i); if(next=='I'){ a0=1; a1=0; a2=0; a3=1; }else { if(type==1){ a0=1; a1=0; a2=0; a3=-1; }else if(type==2){ a0=0; a1=-1; a2=1; a3=0; }else { a0=0; a1=1; a2=1; a3=0; } } ul=multiply(a0, clone(orig)); ur=multiply(a1, clone(orig)); ll=multiply(a2, clone(orig)); lr=multiply(a3, clone(orig)); orig=makeLarge(ul, ur, ll, lr); } return orig; } public double[][] clone(double[][] mat){ double [][]temp = new double[mat.length][mat.length]; for (int i=0; i<mat.length; i++){ for(int j=0; j<mat[0].length; j++){ temp[i][j]=mat[i][j]; } } return temp; } public double[][] multiply(double c, double[][] mat){ double [][] temp = new double[mat.length][mat.length]; for (int i=0; i<mat.length; i++){ for (int j=0; j<mat[0].length; j++){ temp[i][j]= c*mat[i][j]; } } return temp; } public double[][] makeLarge(double[][] ul, double[][] ur, double[][] ll, double[][]lr){ double [][] temp = new double[ul.length*2][ul.length*2]; for(int i =0; i<ul.length; i++){ for(int j=0; j<ul.length; j++){ temp[i][j]=ul[i][j]; } } for(int i =0; i<ul.length; i++){ for(int j=0; j<ul.length; j++){ temp[i][j+ul.length]=ur[i][j]; } } for(int i =0; i<ul.length; i++){ for(int j=0; j<ul.length; j++){ temp[i+ul.length][j]=ll[i][j]; } } for(int i =0; i<ul.length; i++){ for(int j=0; j<ul.length; j++){ temp[i+ul.length][j+ul.length]=lr[i][j]; } } return temp; } public double determinant (double[][] mat){ if(mat.length==2){ return( mat[0][0]*mat[1][1]-mat[0][1]*mat[1][0]); } double det=0; for(int i=0; i<mat.length; i++){ double fac =mat[0][i]; if(i%2==1){ fac*=-1; } det+=fac*determinant(makeSmall(mat,0,i)); } return det; } public double[][] makeSmall(double[][] mat, int row, int col){ double [][] temp= new double[mat.length-1][mat.length-1]; int x1=0; int x2=0; for(int i=0; i<mat.length; i++){ if(i!=row){ for(int j=0; j<mat.length; j++){ if(j!=col){ //System.out.println(x1+" "+x2); temp[x1][x2]=mat[i][j]; x2++; } } x2=0; x1++; } } //System.out.println(x1+" "+x2); return temp; } public String makeString(ArrayList<Integer> list){ String str=""; int a = Integer.parseInt(""+list.get(0)); int b = Integer.parseInt(""+list.get(1)); for(int i = 0; i < numvariable; i++){ if(i != a && i != b){ str = "I"+str; }else { str = "S"+str; } } return str; } } |