PaperlayerView exact revision on arXiv

Source-linked AI summary

Probabilistic computing with p-bits

Jan Kaiser, Supriyo Datta

arXiv:2108.09836v2cs.ETcond-mat.dis-nnquant-ph

TL;DR

Monte Carlo algorithms address many problems, but deterministic implementations of random-number generators can require thousands of transistors. The paper proposes a p-computer built around p-bits and emulates systems with thousands of them, reporting significant acceleration of randomized algorithms across multiple application areas.

  • Problem

    Deterministic implementations of random-number generators can require thousands of transistors, despite Monte Carlo algorithms serving a broad range of problems.

    Source: §I · p. 1

  • Method

    The paper proposes a generic p-computer architecture based on p-bits and emulates systems with thousands of p-bits.

    Source: §IV · p. 6

  • Results

    The emulations show significant acceleration of randomized algorithms used in applications including Bayesian networks, optimization, Ising models, and quantum Monte Carlo.

    Source: §IV · p. 6

  • Takeaways & Limitations

    A p-computer can implement algorithms intended for quantum computers, although quantum Monte Carlo effectiveness depends on the sign problem and the ability to tame it.

    Source: §I · p. 1

    Quantum Monte Carlo effectiveness depends strongly on the algorithm’s sign problem and the ability to tame it.

    Source: §I · p. 1

Abstract

from arXiv · show

Digital computers store information in the form of bits that can take on one of two values 0 and 1, while quantum computers are based on qubits that are described by a complex wavefunction, whose squared magnitude gives the probability of measuring either 0 or 1. Here, we make the case for a probabilistic computer based on p-bits, which take on values 0 and 1 with controlled probabilities and can be implemented with specialized compact energy-efficient hardware. We propose a generic architecture for such p-computers and emulate systems with thousands of p-bits to show that they can significantly accelerate randomized algorithms used in a wide variety of applications including but not limited to Bayesian networks, optimization, Ising models, and quantum Monte Carlo.

I. INTRODUCTION

The paper argues that probabilistic computing can better serve nondeterministic problems than deterministic hardware running pseudo-random generators. It proposes a pipelined p-computer architecture and argues that its throughput can exceed standard CPU or GPU implementations across a broad range of applications.

I. INTRODUCTION

  • Monte Carlo methods serve many applications, but deterministic implementations of random-number generators require thousands of transistors, motivating a p-computer.The cited examples include Bayesian learning, protein folding, optimization, stock-option pricing, and cryptography.Source: §I · p. 1
  • The proposed p-computer pairs an N-bit random-number generator with a deterministic kernel, with parallel units and a data collector for combining outputs.RNG-kernel subunits may be connected in series or parallel, depending on the problem.Source: §I · p. 1
  • The authors argue that even one parallel unit can exceed standard CPU or GPU implementations across a broad range of applications.Pipelining the kernel and data collector lets them continually accept random numbers; the authors also note that quantum Monte Carlo effectiveness depends on the sign problem and the ability to tame it.Source: §I · p. 1

II. IMPLEMENTATION

The p-computer combines an N-bit RNG of p-bits with a deterministic, problem-specific kernel and data collector. The implementation uses CMOS pseudo-RNG p-bits, while compact s-MTJ p-bits remain a developing alternative that may substantially increase throughput.

II. IMPLEMENTATION

  • The architecture combines an N-bit RNG made of 1-bit p-bits with deterministic kernel and data-collection elements.The kernel is problem-specific, while the collector typically performs addition.Source: §II · p. 1, Figure 1 · p. 2
  • Each p-bit outputs a binary value whose mean is controlled by its input; with zero input, its output is distributed 50–50 between 0 and 1.A nonzero input, determined by the current sample, is generally needed to generate desired probability distributions.Source: §II · pp. 1–2
  • The CMOS implementation uses LFSRs, lookup tables, and thresholding, whereas s-MTJ p-bits are a proposed three-transistor alternative.All results here use the CMOS approach; the s-MTJ technology is nascent and has many unanswered questions.Source: Figure 1 · p. 2, §II · p. 2
  • A 2–3-order-of-magnitude performance improvement over the reported results may be possible by increasing clock frequency and parallel units with s-MTJ or other physics-based hardware.The reported results use an FPGA at 125 MHz; s-MTJs could support shorter clock periods and up to 100 times more parallel units for a given area and power budget.Source: §II · p. 2
  • Compact p-bit implementations face unresolved issues involving RNG variation and quality, reading rapid fluctuations, and analog inputs that require DACs unless the kernel is analog.The discussion notes that some applications may need higher-quality randomness than others.Source: §II · pp. 2–3

A. Simple integration

Simple integration estimates a sum from a limited set of randomly sampled configurations. The standard deviation decreases with sample count, so faster sample collection can benefit these applications.

A. Simple integration

  • Monte Carlo estimates a sum over N terms using a limited number Ns of configurations drawn with probability qα.The distribution {q} may be uniform or chosen to minimize the estimate’s standard deviation.Source: A. Simple integration · p. 3
  • The standard deviation of the Monte Carlo estimate decreases as 1/√Ns, and faster sample collection can benefit these applications.The sampling distribution can be uniform or chosen to minimize the estimate’s standard deviation.Source: A. Simple integration · p. 3
  • The sampling distribution {q} may be uniform or chosen to minimize the standard deviation of the estimate.Source: A. Simple integration · p. 3

B. Bayesian Network

The p-computer samples Bayesian networks by mapping each generation to an RNG block and storing conditional probabilities in a Kernel. This supports measuring correlations while avoiding computation over irrelevant nodes.

B. Bayesian Network

  • Nodes separated by p generations have correlation 1/2p, while measured absolute correlation between strangers goes down to zero as 1/√Ns.The network with N nodes maps to an N-bit RNG-block feeding into a Kernel that stores the conditional probability table relating it to the next generation.Source: B. Bayesian Network · p. 3
  • 125 MSamples per second is about two orders of magnitude faster than running the same algorithm on an Intel Xeon CPU.The p-computer uses Np = 1 and fc = 125 MHz; Monte Carlo accuracy ε requires Ns = 1/ε^2 samples.Source: B. Bayesian Network · p. 3
  • A p-computer can measure correlations among relevant nodes without integrating over irrelevant nodes, unlike deterministic algorithms described as inefficient for this problem class.The paper identifies one-way causal networks from parent to child nodes as a broader class that could benefit.Source: B. Bayesian Network · p. 3

C. Knapsack Problem

For knapsack optimization, the p-computer runs an MCMC algorithm that proposes small changes to accepted solutions. It improves substantially over CPU execution of the same algorithm, though a specialized deterministic algorithm can outperform it.

C. Knapsack Problem

  • Proposals change only two items from the previous accepted solution, rather than sampling solutions entirely at random.To avoid waiting multiple clock cycles for Kernel feedback, the method makes proposals every clock cycle using multiple-try Metropolis.Source: C. Knapsack Problem · p. 4
  • The comparison includes CPU and GPU implementations of the probabilistic algorithm alongside dynamic programming and Pisinger et al.’s deterministic algorithms.The projected p-computer performance assumes improved hardware such as s-MTJs, and the authors note possible gains from optimizing Metropolis or adding parallel tempering.Source: C. Knapsack Problem · p. 4
  • The p-computer provides orders-of-magnitude improvement over CPU implementation of the same MCMC algorithm, but Pisinger’s specialized deterministic algorithm outperforms it.MCMC solutions are within 1% of the correct solution; deterministic algorithms give the correct solution.Source: C. Knapsack Problem · p. 4

D. Ising model

The paper uses Boltzmann-machine energy functions to guide p-bit sampling for optimization and other tasks. The framework also covers invertible logic and quantum Monte Carlo for the transverse-field Ising model.

D. Ising model

  • Figure 4 presents a transverse-field Ising model example for quantum Monte Carlo and quantum annealing.The figure caption identifies its subfigures as a mapping to the p-computer framework and a solution of the model.Source: Figure 4 · p. 5
  • Boltzmann machines generate samples with probabilities proportional to exp(−βE), and optimization can encode the negative cost as energy.A large β makes the minimum-energy configuration nearly certain; quadratic energies use connection weights and biases.Source: D. Ising model · pp. 4–5
  • For quadratic energy functions, the Kernel performs a multiply-and-accumulate operation; it can be modified for more complicated or tabulated energies.The paper also cites an eight-bit p-computer example using fourth-order energy terms.Source: D. Ising model · p. 5
  • Choosing βE = −ln P lets a Boltzmann machine generate samples from a desired probability distribution.The paper also describes encoding logic by assigning zero energy to truth-table states and positive energy to other states.Source: D. Ising model · p. 5
  • A Boltzmann-machine logic implementation is invertible: it can generate possible inputs for a specified output, as well as outputs for given inputs.This contrasts with standard digital logic, according to the paper.Source: D. Ising model · p. 5

E. Quantum Monte Carlo

Quantum Monte Carlo estimates large sums over Feynman paths from selected samples, but cancellation can make accurate estimation sample-intensive. The section describes how p-bits can represent such calculations and reports accurate correlations for a mapped transverse-field Ising model.

E. Quantum Monte Carlo

  • A conceptual mapping represents n qubits and d gates with n × d p-bits whose states label terms in the matrix-product sum, called Feynman paths.The desired quantity is the sum of the paths' amplitudes.Source: E. Quantum Monte Carlo · p. 5
  • Quantum Monte Carlo estimates an enormous Feynman-path sum from selected samples, but mixed-sign or complex amplitudes can cancel and require many more samples.When all path amplitudes are positive, estimating the sum from a few samples is relatively easy.Source: E. Quantum Monte Carlo · p. 6
  • In gate-based quantum computing, complex unitary elements often cause path cancellation, potentially requiring many samples; p-computers could be competitive with noisy real-world quantum computers.A noiseless quantum computer would not face this sampling problem because it performs the sum exactly.Source: E. Quantum Monte Carlo · p. 6
  • For stoquastic Hamiltonians, positive matrix elements give Feynman-path amplitudes with the same sign, avoiding the sign problem.The Suzuki-Trotter method approximates e^-βH/r by products of e^-βH1/r and e^-βH2/r when H = H1 + H2 and the replica count is sufficiently large.Source: E. Quantum Monte Carlo · p. 6
  • For a 250-qubit transverse-field Ising model, 2,500 p-bits in 10 replicas produced very accurate correlations using 105 suitably spaced samples.The samples were spaced to ensure independence, an important concern in problems involving feedback.Source: E. Quantum Monte Carlo · p. 6
  • The section relates quantum Monte Carlo's selective Feynman-path summation to randomized algorithms for linear algebra, while noting the fields seem distinct at present.Source: E. Quantum Monte Carlo · p. 6

IV. CONCLUDING REMARKS

The conclusion presents p-computers as a p-bit-based architecture and reports emulations with thousands of p-bits for randomized algorithms across several application areas.

IV. CONCLUDING REMARKS

  • The proposed p-computer architecture uses p-bits that take values 0 and 1 with controlled probabilities and can use compact, energy-efficient specialized hardware.Source: §IV · p. 6
  • Emulations with thousands of p-bits show significant acceleration of randomized algorithms used in many applications.Source: §IV · p. 6
  • The prototypical applications include Bayesian networks, optimization, Ising models, and quantum Monte Carlo.Source: §IV · p. 6

Conflict of interests

The section discloses an author’s financial interest and is accompanied by a list of five references.

Conflict of interests

Loading 2108.09836v2…