[發明專利]采樣設備和用于控制采樣設備的方法

在審

• 申請號: 202010107459.7
• 申請日: 2020-02-21
• 公開（公告）號: CN111611126A
• 公開（公告）日: 2020-09-01
• 發明（設計）人: 土手曉;田村泰孝
• 申請（專利權）人: 富士通株式會社
• 主分類號: G06F11/30
• 分類號: G06F11/30;G06F17/15;G06N20/00;G06Q10/04
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 劉雯鑫;楊林森

本發明涉及采樣設備和用于控制采樣設備的方法。采樣設備包括：狀態保存單元，其保存多個狀態變量的值并每隔一定試驗次數將其輸出；能量變化計算單元，其基于根據更新索引值選擇的權重值計算能量變化值；第一偏移控制單元，其基于多個能量變化值確定第一偏移值并每隔一定試驗次數將其輸出，輸出通過將第一偏移值與多個能量變化值相加獲得的多個第一評估值；第一比較單元，其基于將多個第一評估值與閾值比較的結果輸出多個第一標志值；第一標志計數單元，其每隔一定試驗次數輸出通過對指示允許狀態轉換的第一標志值的數目計數獲得的第一計數值；以及選擇單元，其基于多個第一標志值或多個能量變化值將與狀態轉換之一對應的索引值輸出為更新索引值。

技術領域

本文討論的實施方式涉及采樣設備和用于控制采樣設備的方法。

背景技術

作為用于求解組合優化問題的技術，存在用于將組合優化問題轉變成表示磁體中自旋行為的伊辛模型(Ising model)以及用于使用馬爾可夫鏈蒙特卡羅方法將伊辛模型的狀態變換為低能量狀態的技術。在下文中，將馬爾可夫鏈蒙特卡羅方法簡稱為MCMC方法。伊辛模型的狀態可以由多個狀態變量的值的組合來表示。當狀態變量的數目等于N時，伊辛模型的狀態由x＝(x₁,x₂,...,x_N)等表示。狀態變量中的每一個可以使用值0或1。

表示伊辛模型的能量的伊辛型能量函數E(x)由例如下面的等式(1)定義。

右側的第一項是針對伊辛模型的所有狀態變量的所有組合在沒有任何遺漏和重復的情況下通過將兩個狀態變量的值(分別為0或1)和權重值(表示兩個狀態變量之間的交互作用的強度)的乘積相加獲得的。在等式(1)中，x_i表示具有標識信息(下文中稱為索引值)i的狀態變量，x_j表示具有索引值j的狀態變量，以及W_ij表示指示具有索引值i和j的狀態變量之間的交互作用的大小的權重值。

右側的第二項是具有每個索引值的偏置系數和狀態變量的乘積之和。在等式(1)中，b_i表示索引值i的偏置系數。

當狀態變量x_i變為1-x_i，狀態變量x_i的增加由Δx_i＝(1-x_i)-x_i＝1-2x_i表示。響應于自旋反轉(狀態變量的值的變化)的能量變化ΔE_i由下面的等式(2)表示。

在等式(2)中，當狀態變量x_i從1變為0，Δx_i等于-1。當狀態變量x_i從0變為1，Δx_i等于1。注意，h_i被稱為局部字段(local field)。通過根據值Δx_i將局部字段h_i乘以符號因子(+1或-1)而獲得的值為能量變化ΔE_i。

作為關于響應于特定狀態轉換而發生的能量變化ΔE的特定狀態轉換的允許概率(allowable probability)，可以使用由下面的等式(3)表示的由蒙特卡洛(Metropolis)方法或吉布斯(Gibbs)方法定義的允許概率A(ΔE)。

在等式(3)中，β表示反溫度(inverse temperature)(表示溫度的溫度值的倒數)。就概率而言，涉及能量的增加的狀態轉換也是允許的。

在常規MCMC方法中，隨機地或按索引值的次序(順序地)選擇狀態變量。基于響應于其中狀態變量的值改變的狀態轉換的能量變化ΔE，以上述允許概率A(ΔE)允許狀態轉換。當允許狀態轉換時，更新狀態變量的值。重復這樣的處理一定試驗次數。在某些情況下可以使用溫度逐漸降低的模擬退火方法來搜索最低能量狀態(最優解)。