Probabilistic Prime Factorization based on Virtually Connected Boltzmann Machine and Probabilistic Annealing

2025-05-02 0 0 1023.86KB 13 页 10玖币

侵权投诉



Probabilistic Prime Factorization based on Virtually Connected

Boltzmann Machine and Probabilistic Annealing

Hyundo Jung1*, Hyunjin Kim2*, Woojin Lee, Jinwoo Jeon, Yohan Choi, Taehyeong Park,

and Chulwoo Kim3

Korea University, Seoul, Korea

1: guseh7274@gmail.com, 2: jamespul321@gmail.com, 3: ckim@korea.ac.kr

*: These authors contributed equally to this work

Probabilistic computing has been introduced to operate functional networks using a probabilistic bit (p-bit),

generating 0 or 1 probabilistically from its electrical input. In contrast to quantum computers, probabilistic

computing enables the operation of adiabatic algorithms even at room temperature, and is expected to

broaden computational abilities in non-deterministic polynomial searching and learning problems. However,

previous developments of probabilistic machines have focused on emulating the operation of quantum

computers similarly, implementing every p-bit with large weight-sum matrix multiplication blocks1 or

requiring tens of times more p-bits than semiprime bits2–3. Furthermore, previous probabilistic machines

adopted the graph model of quantum computers for updating the hardware connections, which further

increased the number of sampling operations. Here we introduce a digitally accelerated prime factorization

machine with a virtually connected Boltzmann machine and probabilistic annealing method, designed to

reduce the complexity and number of sampling operations to below those of previous probabilistic

factorization machines1–3. In 10-bit to 64-bit factorizations were performed to assess the effectiveness of the

machine, and the machine offers 1.2×108 times improvement in the number of sampling operations compared

with previous factorization machines, with a 22-fold smaller hardware resource. This work shows that

probabilistic machines can be implemented in a cost-effective manner using a field-programmable gate array,

and hence we suggest that probabilistic computers can be employed for solving various large NP searching

problems in the near future.

Introduction

Deterministic computers have been developed to enhance

computing power using nanoscale transistors. However,

despite the increasing demand for solving combinatorial

optimization problems, deterministic computers perform

slow and inefficient search operations4, and the process-

scaling of transistors has been reaching its limit5. Quantum

computers have been introduced to rapidly solve these non-

deterministic polynomial (NP)-hard problems6–8. However,

the number of qubits required for such cases is still larger

than that of physically implemented qubits.

As a result of the above issues, probabilistic

computing13–24, which is realized by using magnetic tunnel

junction (MTJ) or complementary metal–oxide–

semiconductor (CMOS) technologies, has been proposed to

cost-effectively replace quantum annealers9–12, especially

for factorization calculations1–3. These Ising machines have

improved the factorization speed by four2 and six3 orders

above central processing units. However, the hardware

complexity and computation time of previous factorization

machines sharply increase as the number of total

probabilistic bits (p-bits) increases. Therefore, a novel

algorithm and its hardware implementation are required for

practical applications.

In this work, we propose a virtually connected

Boltzmann machine (VCBM) showing less hardware

complexity than the state-of-the-art probabilistic Ising

machines. Also, we introduce a probabilistic annealing

method for reducing the number of sampling operations of

the Boltzmann machine. Furthermore, we employed three

modulo operators (divide X and Y candidates by 3, 5, and 7)

preceded in each case by a sieve to determine the best

candidate (termed hereafter a “candidate sieve”) and a

decision block that consists of two modulo operators

(divide the semiprime by best candidate), in order to further

accelerate the performance of the factorization machine. To

show its potential to the community, results for up to 64-bit

factorization were produced using a field-programmable

gate array (FPGA).

Virtually connected Boltzmann machine

The Boltzmann machine25–27 is a type of constraint

satisfaction network that can use its probabilistic dynamics

to lead a system to ground states in combinatorial

optimization problems. Since the weights on the

connections between the spins of the Boltzmann machine

are fixed after the problem is formulated, Boltzmann

machines are frequently used for implementing Ising

models in hardware. However, as shown in Fig. 1a, the

hardware should be implemented with large spin-weight

matrix calculation circuits due to the 3-body and 4-body

terms of the Ising model1. On the other hand, when the Ising

model is implemented with hidden bits to represent 3-body

or 4-body terms12, the large number of hidden bits increases

the number of hardware connections to the fourth power of

N bits, (see Methods for details). In 2022, restricted

Boltzmann machine (RBM)28-based probabilistic

computing was introduced2, but the large number of

hardware connections in the RBM still limits the

application of these machines in large-scale general-

purpose probabilistic computers. Moreover, previous Ising

machines require the deployment of an additional



deterministic computer that formulates the hardware

connections of the Ising machine before solving problems1–

3, 13–24.

Figure 1b shows the high-level concept of the VCBM.

In the general Boltzmann machine, the input value of the k-

th p-bit (Ik) represents every connected interaction in the

system to the visible p-bit. Thus, the computational power

of CMOS digital circuits can be used to generate virtual

connections of each visible p-bit. In our machine, the

energy calculator is employed to calculate the digital input

of each p-bit, replacing the need for a large and complex

chain network composed of digital blocks or hidden p-bits.

Since the VCBM uses an equivalent probability equation of

input to p-bits as the general Boltzmann machine, the

VCBM represents an all-to-all connected Boltzmann

machine, which is suitable for solving large and complex

combinatorial problems. Moreover, the energy calculator

generates Ik of each p-bit, enabling the factorization of an

arbitrary semiprime N without reconfiguring its weight

connections between p-bits. Thus, our machine can perform

from 10-bit to 64-bit factorizations of semiprimes

continuously without additional hardware connection

formulations. Detailed information on the derivation is

provided in Methods.

Compared to the quantum annealers, we think that the

major advantage of probabilistic annealers is their

compatibility with digital CMOS circuits at room

temperature. Thus, we propose a digitally accelerated

probabilistic factorization machine architecture that

operates synchronously using both digital logic and the

Boltzmann machine, as shown in Fig. 1c. Considering that

the Boltzmann machine frequently generates a high-quality

output that is close to the global ground state, a set of nearby

numbers of the output of the machine output also have high

probability as an answer. Thus, we inserted a candidate

sieve between the machine and the decision block to choose

the candidate that is close to the output of the Boltzmann

machine but cannot be divided by 3, 5, and 7 (best candidate)

a b

Energy

Calculator

Energy calculator generates

digital input of p-bits

E(sk = 0) – E(sk = 1)

Input of k-th p-bit (Ik)

 Large programmable MAC units

 Reconfigure before solving different N

 Problem size limited by the number of p-bits

Fully-connected

Boltzmann machine1Fully-connected Boltzmann

machine with hidden bits12 Virtually-connected Boltzmann machine

 Many programmable MAC units

 Reconfigure before solving different N

 Problem size limited by the number of p-bits

 Small and fully-synthesizable energy calculator

 Solves arbitrary N without reconfiguration

 Solves large-scale problems through calculator

Fig. 1 | Demonstration of the developed factorization machine. a, b, Architectures of Boltzmann machine-based factorization

machines that can perform up to 10-bit factorization. Circles represent p-bits, and squares represent the approximate hardware area

of the digital logic. (a) In the graph model, p-bits of the general Boltzmann machine require a large area of spin-weight matrix

multiplication logic1. This hardware cost of matrix multiplication logic of the general Boltzmann machine can be reduced by

replacing the 3-body and 4-body terms with hidden p-bits11–12. However, hidden p-bits also increase hardware complexity. (b)

Architecture of the VCBM. The digital input of p-bits can be calculated using the term E(sk=0) – E(sk=1). Thus, the energy

calculator generates p-bit inputs without spin-weight matrix multiplication. c, Architecture of our probabilistic factorization

machine. In this work, we implemented a prototype of a 64-bit general-purpose factorization machine using an FPGA.



with small area consumption. Then, two modulo operators

of the decision block, which are pipelined to operate in two

cycles to reduce the critical-path delay, check whether X or

Y is the factor of N. Therefore, the decision block

determines the end of the factorization operation. For

factorizing up to 64-bit numbers, the machine uses 31 p-bits

that are implemented based on lookup tables (LUTs)2,29 of

the FPGA hardware. Detailed information on the FPGA

implementation is provided in Methods.

Probabilistic annealing

To further improve the factorization operation of the

machine, we developed a probabilistic annealing process.

The probabilistic annealing consists of performing parallel

updates and controlling dynamic system-significant p-bit

(SSPB). In previous works, the Ising machines reached the

global minimum with sequential updating1,14–24 or parallel

updating2–3,13, as shown in Fig. 2a. In the sequential update

process, the system updates each bit to have lower energy

after an update, forcing the system to climb the energy

barrier through consecutive low-probability decisions.

Thus, the sequential updating rather traps the system in a

local minimum. On the other hand, parallel update

machines were implemented for achieving shorter problem

solving, using RBM2, sparse Ising model3, and stochastic

cellular automata (SCA)13,30. However, the RBM machine

and sparse Ising model require pre-training before each

search operation. The SCA machine has been reported to

solve max-cut problems with a level of quality equivalent

to those of sequential update machines, but the machine

converges the system energy through a slow logarithmic

cooling along with penalty control, which rather fixes the

system to a specific wrong solution in factorization

problems. Moreover, previous parallel-updating machines

did not achieve a computational complexity advantage over

those using the sequential update method, which means

they shortened the operation time at the expense of

increasing the amount of hardware area.

Therefore, we introduce the probabilistic annealing to

make the system rapidly converge to a minimum. In

Yes

High prob.

Solution space

System energy

Sequential update with

simulated annealing

Low prob.

High temp.

Solution space

System energy

Parallel update with

simulated annealing

Low temp.

Solution space

System energy

Probabilistic annealing

Trapped Trapped

Solved

1st iter. 2nd iter.

3rd iter.

1st end

2nd end

Start

Update X,

i = i + 1

N mod X = 0?

Yes

Update Y

N mod Y = 0?

i = 2'b11?

End

No Yes

E(S) << 1 E(S) >> 4

Candidate

sieve Select X

for modulo

pbits

Energy

calculator

CLK

(10 MHz)

X Modulo

operator

Y Modulo

operator

Calculate

Ik of XCalculate

Ik of YCalculate

Ik of XCalculate

Ik of Y

Update

X bits Update

Y bits Update

X bits Update

Y bits

N mod X N mod XN mod X

N mod Y N mod Y

Select Y

for modulo Select X

for modulo Select Y

for modulo

Fig. 2 | Demonstration of probabilistic annealing. a, Com-parison of state transitions in annealing processes. In general,

sequential updating makes it difficult for the system to escape from a local minimum. In addition, previous machines performing

parallel updating were designed to gradually decrease the temperature, causing the system to converge slowly and be trapped in a

local minimum in its final state. The probabilistic annealing of the current work was designed to accelerate the system convergence

to a minimum with parallel updating and dynamic SSPB control. Upon completion of 8 sampling operations (in which the number 8

is constant for every factorization operation in this work), the system restarts a searching iteration from a higher energy state until

achieving the solution to the problem. b, Flowchart and operating sequence of the factorization machine. This machine is designed

to employ a decision block (X and Y modulo operators) for determining the completion of factorization when N mod X or N mod Y

becomes 0. The operation of the candidate sieve is conducted after the p-bit update (omitted in the flowchart for simplicity).

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ProbabilisticPrimeFactorizationbasedonVirtuallyConnectedBoltzmannMachineandProbabilisticAnnealingHyundoJung1*,HyunjinKim2*,WoojinLee,JinwooJeon,YohanChoi,TaehyeongPark,andChulwooKim3KoreaUniversity,Seoul,Korea1:guseh7274@gmail.com,2:jamespul321@gmail.com,3:ckim@korea.ac.kr*:Theseauthorscontributed...

展开>> 收起<<

Probabilistic Prime Factorization based on Virtually Connected Boltzmann Machine and Probabilistic Annealing.pdf

共13页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Probabilistic Prime Factorization based on Virtually Connected Boltzmann Machine and Probabilistic Annealing

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: