@yuichirominato 2019.02.19更新 86views

【すり抜け】SAでトンネル効果


はじめに

最近時間が少しずつできてきたので気になったことを少しずつ実行しはじめています。そんな中、最初に量子アニーリングで「トンネル効果」ですり抜けるので計算が早いと聞いた時にふと思ったのが、(それSAでもできそう。。。)というものでした。

あれから3年ようやくちょっといろいろ試してみます。

まず考察

1、横磁場をかけるとポテンシャル曲線の起伏が減って、01を行き来しやすくなる。最初にJijやhiの絶対値を小さくしてから少しずつ大きくすればトンネル効果が出るのでは?

2、モンテカルロ計算の際にシングルスピンフリップだからトンネル効果が現れなくて、山の向こう側にいけないのなら、シングルフリップではなくクラスタフリップでモンテカルロのエネルギー評価をしてみては?

と普通にたくさんアイデアが出てきました。いちいち調べるのめんどいので研究者の方々にお任せして、とりあえずjavascriptで実際どうなのか実装してみます。

量子アニーリングと揃えるために、アニーリング初期にトンネル効果を発動させるべく、初期設定からだんだん設定値を通常のSAに戻して行ってみます。

実装

通常のSAだが、Jijとhiの値の絶対値を小さくして始める。探索空間が広がる気がします。見た目を楽しくするために隣接格子の2Disingでやってみます。

まずは普通の実装。

デモサイトこちらに。

https://minatoyuichiro.github.io/various_sa/

<!doctype html>
<html>
<head>
</head>
<body>
<canvas id="main" width="2000" height="900"></canvas>
<script>
 var N = 120;
 var n = 80;
 var T = 10;
 var q = new Array(N);
 var jij = 1;
 var loop = 50000;

 for(var i=0;i<N;i++){
  q[i] = new Array(n);
  for(var j=0;j<n;j++){
   q[i][j] = Math.floor(Math.random()-0.5)*2+1;
  };
 };

 //html5 canvas
 var canvas = document.getElementById('main');
 var ctx = canvas.getContext('2d');
 var anneal = setInterval(function(){

  //monte carlo loop start
  for(var k=0;k<loop;k++){
   var x = Math.floor(Math.random()*N);
   var y = Math.floor(Math.random()*n);
   var dE = jij*2*q[x][y]*(q[(N+x-1)%N][y] + q[(x+1)%N][y] + q[x][(n+y-1)%n] + q[x][(y+1)%n]);
   if(Math.exp(-dE/T)>Math.random()){ // Metropolis
    q[x][y] = -q[x][y]; //flipping qbit
   };
  };

  //updating drawing
  ctx.clearRect(0,0,2000,900);
  ctx.beginPath();
  for(var j=0;j<n;j++){
   for(var i=0;i<N;i++){
    if(q[i][j]==1){
     ctx.fillStyle = 'rgb(255,0,0)';
    }else{
     ctx.fillStyle = 'rgb(255,255,255)';
    }
    ctx.fillRect(i*7,j*8,5,5);
   };
  };
  T = T*0.95;
 },1);
</script>
</body>
</html>

次にJijを途中から戻すタイプ

デモサイトこちらに

https://minatoyuichiro.github.io/various_sa/jij.html


<!doctype html>
<html>
<head>
</head>
<body>
<canvas id="main" width="2000" height="900"></canvas>
<script>
 var N = 120;
 var n = 80;
 var T = 10;
 var q = new Array(N);
 var jij_init = 1;
 var jij = 1;
 var loop = 50000;
 for(var i=0;i<N;i++){
  q[i] = new Array(n);
  for(var j=0;j<n;j++){
   q[i][j] = Math.floor(Math.random()-0.5)*2+1;
  };
 };

 //html5 canvas
 var canvas = document.getElementById('main');
 var ctx = canvas.getContext('2d');
 var anneal = setInterval(function(){
  jij = jij_init/T
  //monte carlo loop start
  for(var k=0;k<loop;k++){
   var x = Math.floor(Math.random()*N);
   var y = Math.floor(Math.random()*n);
   var dE = jij*2*q[x][y]*(q[(N+x-1)%N][y] + q[(x+1)%N][y] + q[x][(n+y-1)%n] + q[x][(y+1)%n]);
   if(Math.exp(-dE/T)>Math.random()){ // Metropolis
    q[x][y] = -q[x][y]; //flipping qbit
   };
  };

  //updating drawing
  ctx.clearRect(0,0,2000,900);
  ctx.beginPath();
  for(var j=0;j<n;j++){
   for(var i=0;i<N;i++){
    if(q[i][j]==1){
     ctx.fillStyle = 'rgb(255,0,0)';
    }else{
     ctx.fillStyle = 'rgb(255,255,255)';
    }
    ctx.fillRect(i*7,j*8,5,5);
   };
  };
  T = T*0.95;
 },1);
</script>
</body>
</html>

最後にクラスタフリップ

デモサイトこちらに

https://minatoyuichiro.github.io/various_sa/cluster.html


<!doctype html>
<html>
<head>
</head>
<body>
<canvas id="main" width="2000" height="900"></canvas>
<script>
 var N = 120;
 var n = 80;
 var T = 10;
 var q = new Array(N);
 var jij = 1;
 var loop = 50000;
 var change = 0.5;
 for(var i=0;i<N;i++){
  q[i] = new Array(n);
  for(var j=0;j<n;j++){
   q[i][j] = Math.floor(Math.random()-0.5)*2+1;
  };
 };

 //html5 canvas
 var canvas = document.getElementById('main');
 var ctx = canvas.getContext('2d');
 var anneal = setInterval(function(){
  //monte carlo loop start
  for(var k=0;k<loop;k++){
   var x = Math.floor(Math.random()*N);
   if(T>change){
   var x1 = Math.floor(Math.random()*N);
   var x2 = Math.floor(Math.random()*N);
   var x3 = Math.floor(Math.random()*N);
   var x4 = Math.floor(Math.random()*N);
   }
   var y = Math.floor(Math.random()*n);
   var dE = jij*2*q[x][y]*(q[(N+x-1)%N][y] + q[(x+1)%N][y] + q[x][(n+y-1)%n] + q[x][(y+1)%n]);
   if(T>change){
   dE += jij*2*q[x1][y]*(q[(N+x1-1)%N][y] + q[(x1+1)%N][y] + q[x1][(n+y-1)%n] + q[x1][(y+1)%n]);
   dE += jij*2*q[x2][y]*(q[(N+x2-1)%N][y] + q[(x2+1)%N][y] + q[x2][(n+y-1)%n] + q[x2][(y+1)%n]);
   dE += jij*2*q[x3][y]*(q[(N+x3-1)%N][y] + q[(x3+1)%N][y] + q[x3][(n+y-1)%n] + q[x3][(y+1)%n]);
   dE += jij*2*q[x4][y]*(q[(N+x4-1)%N][y] + q[(x4+1)%N][y] + q[x4][(n+y-1)%n] + q[x4][(y+1)%n]);
   }
   if(Math.exp(-dE/T)>Math.random()){ // Metropolis
    q[x][y] = -q[x][y]; //flipping qbit
    if(T>change){
    q[x1][y] = -q[x1][y]; //flipping qbit
    q[x2][y] = -q[x2][y]; //flipping qbit
    q[x3][y] = -q[x3][y]; //flipping qbit
    q[x4][y] = -q[x4][y]; //flipping qbit
    }
   };
  };

  //updating drawing
  ctx.clearRect(0,0,2000,900);
  ctx.beginPath();
  for(var j=0;j<n;j++){
   for(var i=0;i<N;i++){
    if(q[i][j]==1){
     ctx.fillStyle = 'rgb(255,0,0)';
    }else{
     ctx.fillStyle = 'rgb(255,255,255)';
    }
    ctx.fillRect(i*7,j*8,5,5);
   };
  };
  T = T*0.95;
 },1);
</script>
</body>
</html>

結論

普通のと他のも比べてみましたが、挙動はやっぱり問題によるきがしますが、気持ち早くなった気がしたものもありました。

SAはパラメータチューニングだけでなくて、クラスタのフリップやJijの操作によってもパフォーマンスは変化しそうです。以上です!

Recommended


Wikiへ移動