PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Deep Learning

Nathan Wiebe, Ashish Kapoor, Krysta M. Svore

arXiv:1412.3489v2quant-phcs.LGcs.NE

TL;DR

Classical Boltzmann-machine training faces exponentially hard gradient calculations and limitations from contrastive divergence. The paper introduces quantum Gibbs-state preparation and gradient-estimation algorithms, reporting improved model quality, asymptotic deep-network advantages, and efficient full-BM training. The framework is not expected to be exact and efficient for every Boltzmann machine.

  • Problem

    Classical gradient computation for Boltzmann machines is exponentially hard, while contrastive divergence lacks a true-objective gradient, can reach suboptimal solutions, and cannot directly train full Boltzmann machines.

  • Method

    The paper reduces Boltzmann-machine training to quantum Gibbs-state preparation and proposes GEQS and GEQAE for estimating the gradients.

  • Results

    Quantum training significantly improves model objectives, offers an asymptotic advantage for deep networks under constant κ, and efficiently trains full Boltzmann machines.

  • Takeaways & Limitations

    The framework supports richer models than classically tractable approaches, including full Boltzmann machines and multi-layer fully connected models.

  • Takeaways & Limitations

    The algorithms are not expected to be both exact and efficient for all Boltzmann machines, and numerical experiments are limited to models with at most 20 units.

Abstract

from arXiv · show

In recent years, deep learning has had a profound impact on machine learning and artificial intelligence. At the same time, algorithms for quantum computers have been shown to efficiently solve some problems that are intractable on conventional, classical computers. We show that quantum computing not only reduces the time required to train a deep restricted Boltzmann machine, but also provides a richer and more comprehensive framework for deep learning than classical computing and leads to significant improvements in the optimization of the underlying objective function. Our quantum methods also permit efficient training of full Boltzmann machines and multi-layer, fully connected models and do not have well known classical counterparts.

Introduction

Boltzmann machines are generative deep networks trained by optimizing likelihood, but classical gradient estimation is exponentially hard and contrastive divergence has important limitations.

  • Model: Boltzmann machines use undirected interactions to model training data probabilistically with visible and hidden units.Their units encode features or concepts, while interaction weights represent statistical dependencies.
  • Model: A Boltzmann machine assigns configurations of visible and hidden units probabilities through a Gibbs distribution normalized by a partition function.The configuration energy depends on biases and interaction weights.
  • Training objective: Training modifies weights and biases with gradient descent to maximize the likelihood of observed training data, including L2 regularization against overfitting.The objective is the maximum-likelihood objective defined over the training set.
  • Architectures: A deep restricted Boltzmann machine organizes hidden and visible units into distinct layers, with the output layer often treated as visible for classification.The figure contrasts this layered structure with fully connected Boltzmann machines.
  • Classical challenge: Computing gradients directly is exponentially hard in the numbers of visible and hidden units, motivating approximate classical methods.The cited approach is contrastive divergence, which does not provide the gradient of a true objective function.
  • Classical challenge: Contrastive divergence can yield suboptimal solutions, lack convergence guarantees under some regularizers, and cannot directly train full Boltzmann machines.These limitations motivate quantum alternatives for deep learning.

GEQS Algorithm

GEQS prepares an approximate Gibbs state from an efficient prior distribution and uses quantum sampling to estimate Boltzmann-machine gradients, offering favorable training resources under stated conditions.

  • Algorithm: GEQS prepares a coherent analog of a Boltzmann machine’s Gibbs state and samples it to estimate the expectation values needed for gradients.The algorithm is designed as an efficient alternative to classical gradient approximations.
  • State preparation: The algorithm uses a mean-field or related efficient approximation as a non-uniform prior over configurations before refining it toward the Gibbs state.The mean-field approximation is a product distribution minimizing KL(Q||P), and related structured approximations can also be used.
  • State preparation: Quantum amplitude amplification quadratically boosts state-preparation success when the initial success probability is small.The target Gibbs state is obtained by measuring the right-most qubit as 1.
  • Complexity: Assuming κ is constant, quantum sampling provides an asymptotic advantage for training deep networks.The gradient-estimation cost is tied to the number of model edges, while the classical comparison includes layer-dependent scaling.
  • Resources: GEQS requires O(nh + nv + log(1/E)) logical qubits when P(v, h) is accessed as an oracle with precision E.The training data need not be stored in a quantum database, avoiding a requirement scaling with Ntrain logical qubits.
  • Accuracy and limits: GEQS remains efficient with fixed κ at the price of probability-distribution errors, while fidelity stays high when the total probability of violating configurations is small.The exact value of κ need not be known, and the resulting fidelity is formalized as at least 1 −ϵ under the stated condition.
  • Accuracy and limits: GEQS is not expected to be both exact and efficient for all Boltzmann machines, and hard instances remain possible under complexity-theoretic assumptions.The paper states that the practical frequency of such hard examples is unknown.

GEQAE Algorithm

GEQAE exploits quantum access to training data in superposition and uses amplitude estimation to reduce gradient-estimation variance, making it preferable for sufficiently large datasets.

  • Quantum data access: GEQAE accesses training vectors through a quantum oracle, allowing the data to be processed in superposition rather than sequentially.A single oracle query can prepare a uniform superposition over training vectors.
  • Benefits: GEQAE produces a quadratic reduction in estimated-gradient variance relative to GEQS when training data are available through a quantum oracle.This can yield substantial performance improvements for large training sets.
  • Resource trade-off: Quantum training-data access typically requires more qubits for GEQAE than for GEQS because the data must be stored directly or indirectly in the quantum computer.Superposition access mitigates this cost by reducing the number of data accesses.
  • Gradient estimation: GEQAE estimates gradient expectations by amplitude estimation of probabilities associated with Gibbs-state preparation and joint visible-hidden events.The method estimates P(1) and P(11) to recover expectations such as ⟨vihj⟩.
  • Regime: GEQAE is preferable to GEQS if √Ntrain ≫E.The comparison reflects the trade-off between training-set size and model-edge count in the query complexity.

Parallelizing Algorithms

GEQS and GEQAE exploit quantum parallelism to reduce circuit depth for deep Boltzmann-machine training, while contrastive-divergence depth grows with the number of layers.

  • Quantum parallelism: GEQS and GEQAE can leverage fault-tolerant quantum parallelism to train deep restricted Boltzmann machines more effectively.Layer energies and mean-field state preparations can be computed simultaneously.
  • Quantum parallelism: The energy computation has depth O(max(nv, nh) log(max(nv, nh))) per layer and the layer energies can be summed in depth O(log(ℓ)).These operations avoid serializing all layer computations.
  • Quantum parallelism: GEQAE derivatives can be computed independently, and mini-batching can reduce depth at the cost of increased circuit size.The paper describes this as a depth–circuit-size trade-off.
  • Classical comparison: Contrastive-divergence training has O(ℓ2) depth because it is a feed-forward algorithm, unlike GEQS and GEQAE.Most CD-k operations are parallelizable, but its k sampling rounds for each layer are not easily parallelized.

Numerical Results

The numerical studies examine κ, optimization quality, and model capacity under quantum and classical training settings. They find manageable κ for large networks, improved objective values from ML optimization, and higher capacity for full Boltzmann machines than dRBMs.

  • κ scaling: κ primarily depends on the quality of the mean-field approximation rather than visible or hidden-unit counts.Doubling visible units did not substantially increase κ despite a 2^6 Hilbert-space difference.
  • κ scaling: κ ≈ 1000 typically gives a close Gibbs-state approximation, while hedging strategies can reduce κ to roughly 50.
  • κ scaling: κ^-1 ∈ O(σ^2(w_i,j)E) for small random RBMs when σ^2(w_i,j)E ≪ 1.
  • κ scaling: Weights in large contrastive-divergence-trained RBMs rapidly shrink as hidden units increase, suggesting κ remains manageable as networks grow.For N = 0, the empirical scaling is σ^2 ∈ O(E^-1).
  • Optimization quality: ML-training substantially improves resultant model quality, with differences between optima for deep networks reaching approximately 10%.Contrastive divergence can outperform ML-objective gradient descent in highly constrained cases because its stochastic approximation is less sensitive to local minima.
  • Model capacity: A full Boltzmann machine with n_v = 6 and n_h = 4 achieves O_ML ≈ -1.84, compared with approximately -2.3 for a comparable dRBM.The paper reports the dRBM value as 25% less than the full-BM result.

Conclusions

The paper frames Boltzmann-machine training as quantum state preparation rather than contrastive-divergence approximation. This framework improves gradients and model optimization, supports full BMs, and still requires hardware experiments to assess generalization.

  • Conclusions: Training Boltzmann machines can be reduced to quantum state preparation without contrastive divergence or assumptions about graph topology.
  • Conclusions: The framework refines mean-field approximations into states close or equivalent to the desired Gibbs state.
  • Conclusions: The method’s operation count does not explicitly depend on dRBM layer count, reduces training-data accesses quadratically, and enables full-BM training.
  • Conclusions: Future quantum-hardware experiments are needed to assess the algorithm’s generalization performance.

Appendix A: Quantum algorithm for state preparation

The appendix constructs coherent Gibbs states by refining efficiently computed mean-field distributions with quantum rejection sampling. The preparation succeeds with probabilities controlled by κ and can trade fidelity against an insufficient κ bound.

  • State-preparation pipeline: The algorithms prepare a quantum distribution approximating the Gibbs distribution, then refine it through rejection sampling.The resulting state can be measured to obtain Gibbs-distribution samples for expectation estimation.
  • Quantum acceleration: Amplitude estimation can quadratically reduce the number of operations needed to reach a fixed sampling error.
  • Mean-field initialization: Mean-field distributions Q and Q_x provide efficiently computable, factorized initial states and variational partition-function approximations.Q_x applies when visible units are clamped to a training vector x.
  • κ parameter: κ is an upper bound on the ratio between the Gibbs-probability approximation based on Z_Q and the mean-field distribution Q.
  • Success probability: A coherent Gibbs state is prepared with success probability Z/(κZ_Q), and the clamped-state analogue succeeds with probability Z_x/(κ_xZ_x,Q).
  • Circuit construction: The preparation circuit computes mean-field parameters and partition-function estimates, prepares |ψ_Q⟩ with single-qubit rotations, and uses reversible probability encoding with an ancilla rotation.
  • Approximation trade-off: If the approximation error is at most ϵZ, the prepared state has fidelity at least 1 − ϵ with probability at least Z(1 − ϵ)/(κZ_Q).

Appendix B: Gradient calculation by sampling

GEQS prepares Gibbs-state samples from a mean-field state to estimate the expectation values needed for Boltzmann-machine gradients. The resulting approach has an asymptotic advantage for deep networks under constant κ, while optimizing the maximum-likelihood objective up to sampling error.

  • Gradient calculation by sampling: GEQS prepares the Gibbs state from a mean-field state and samples it to estimate the expectation values required for the gradient.Amplitude amplification quadratically reduces the mean repetitions needed to draw Gibbs-distribution samples.
  • Gradient calculation by sampling: Mean-field states provide an efficiently computable prior that is close to the Gibbs distribution and serves as a shortcut for state preparation.The algorithm’s prepared final distributions are not themselves mean-field distributions.
  • Gradient calculation by sampling: Theorem 1 establishes a quantum algorithm for estimating the maximum-likelihood gradient using Ntrain samples on a connected graph with E edges.The theorem characterizes the mean number of quantum operations required by the algorithm.
  • Gradient calculation by sampling: For connected graphs, state-preparation costs scale as Õ(E), so Algorithm 3 has expected cost scaling as Õ(NtrainE) up to logarithmic factors.This scaling follows from energy evaluation and rotation-synthesis costs.
  • Gradient calculation by sampling: Assuming κ is constant, quantum sampling provides an asymptotic advantage for training deep networks.The comparison is difficult because the classical and quantum approaches optimize different objective functions.
  • Gradient calculation by sampling: The quantum approach is expected to find superior models because it optimizes the maximum-likelihood objective up to finite-sample error.This expectation is explicitly qualified by sampling error from finite Ntrain.

Appendix C: Training via quantum amplitude estimation

The amplitude-estimation approach uses coherent access to the training set and quantum state preparation to estimate individual gradient components. It achieves Õ(1/δ)-type state-preparation scaling for constant learning rate, with complexity depending on κ, conditioned quantities, and graph size.

  • Training via quantum amplitude estimation: A single quantum access to UO prepares a uniform distribution over the training data, although exploiting the superposition requires more than classical random sampling.Algorithm 4 uses the superposition to provide advantages under certain circumstances.
  • Training via quantum amplitude estimation: Algorithm 4 prepares a uniform superposition of training data, applies the training-data oracle UO, and uses amplitude estimation to compute gradient components.The method can be adapted from weight derivatives to bias derivatives.
  • Training via quantum amplitude estimation: For constant learning rate r, Algorithm 4 requires Õ(1/δ) state preparations to achieve overall derivative error δ.The construction first estimates data and model expectations within error Δ, yielding derivative error at most 2Δr.
  • Training via quantum amplitude estimation: For connected graphs, expected oracle-query complexity scales as Õ((κ + maxv κv)/δ), while circuit complexity scales as Õ((κ + maxv κv)E/δ).Each state preparation uses one UO query and Õ(E) operations.
  • Training via quantum amplitude estimation: Amplitude estimation provides detailed information about one gradient component, but its measurement biases make inference about remaining components unclear.This limits straightforward reuse of amplitude-estimation evidence across other gradient directions.
  • Training via quantum amplitude estimation: Algorithm 4 requires quantum access to the training data, whereas serial processing of a stored database can require Θ(Ntrain) space and time per oracle query.The oracle can otherwise be implemented in O(polylog(Ntrain)) time using O(Ntrain) memory.
  • Hedging strategies: Large κ can obstruct exact Gibbs-state preparation, with examples requiring κ above 10^20 even for small Boltzmann machines.Hedging adjusts mean-field expectations through α to reduce bias, without substantially changing state preparation.

Appendix E: Numerical experiments

The numerical experiments compare contrastive-divergence training with maximum-likelihood optimization across restricted and deeper Boltzmann machines. They examine objective quality, gradient-estimation noise, and state-preparation scaling under synthetic and subsampled MNIST data.

  • Data and Methodology: The experiments compare contrastive divergence with Algorithm 3 or Algorithm 4 while optimizing the same maximum-likelihood objective.Different gradient approximations can lead to different local optima even from identical initial conditions.
  • Data and Methodology: The comparison protocol uses local-optimum perturbations and cross-initialization combinations denoted CD–ML, ML–CD, and ML–ML.The perturbation procedure is repeated 459 times with perturbation size 10^-3.
  • Data and Methodology: Figure 5 shows that mean objective-function error scales quadratically with gradient noise, indicating resilience to sampling noise.A noise level of δ = 0.01 is reported as sufficient to obtain optima close to those at δ = 0.
  • Data and Methodology: Zero-mean sampling errors can be mitigated by adjusting the learning rate, whereas GEQAE errors are not guaranteed to be unbiased.The passage reports empirical strategies for reducing errors to the 10^-2 threshold.

3. Errors due to mean–field approximation and the scaling of κ

The quantum state-preparation approach depends on the mean-field approximation and κ, whose required scale is governed by approximation quality, weight variance, and graph structure. Small κ can support accurate preparation in many RBMs, while full Boltzmann machines and harder instances may require substantially larger values or remain difficult to characterize.

  • κ < 10 suffices for near-zero state-preparation error in all considered synthetic RBM cases.κ increases slowly with the number of visible units and the standard deviation of synthetic-model weights.
  • KL(Q||P) tends to be less than 0.1 for realistic weight distributions, indicating close mean-field and Gibbs distributions.The KL divergence also measures the slack in the variational approximation to the log-partition function.
  • KL(Q||P) empirically scales as O(σ2(w_i,j)E), yielding P_success ≈ 1/κ when σ2(w_i,j) is in O(1/E).The algorithms are expected to be exact and efficient when σ2(w_i,j)E is small.
  • Differences between contrastive-divergence and maximum-likelihood optima are significant in both location and quality, supporting potential improvements from quantum ML-like training.The comparison reports model-location discrepancies of a few percent and objective-quality differences of about 0.1 percent in small examples.
  • Full Boltzmann machines can yield better optima than restricted models, but accurate state preparation may require κ > 50 for harder instances while κ < 20 suffices for smaller-weight cases.For full models, larger κ is generally needed than for RBMs, and the required scale depends strongly on weight standard deviation.
  • Small numerical studies cannot conclusively determine whether typical full-Boltzmann-machine models are easy or hard state-preparation instances.The observed confidence intervals include many models that conform to the mean-field distribution for σ = 1.

Appendix F: Training using sub–sampled MNIST data

Sub-sampled MNIST experiments reproduce the qualitative differences between contrastive-divergence and maximum-likelihood training seen on synthetic data. However, the scaling of discrepancies and state-preparation requirements remains uncertain in these small experiments.

  • On sub-sampled MNIST, CD–1 and ML optima differ by a few percent in location and by as much as half a percent in O_ML.The estimates use 1000 random restarts and hidden-unit counts n_h ∈ {4, 6, 8, 10}.
  • The MNIST discrepancies are comparable to those observed for synthetic training sets.This applies to both relative model discrepancies and the quality of the resulting optima.
  • The discrepancy between contrastive-divergence and ML training grows approximately linearly with the number of hidden units in the examined graphs.The authors cannot exclude polynomial or exponential asymptotic scaling because the observed growth is modest.
  • For ML-trained MNIST models, the mean-field approximation remains stable as more nodes are added, with nearly constant median bad-configuration probability at κ = 2000.The median varies slightly at κ = 1, while the transition to exact preparation has unresolved scaling.
  • The scaling of the transition point for the α = 0.5 hedging strategy is unclear, with both power-law and exponential behavior consistent with the data.Larger numerical experiments may be needed to distinguish these possibilities.
  • Strong correlations induced by training-data patterns may harm the mean-field approximation, while structured mean-field approximations could improve fidelity.The choice of an initial prior distribution for configuration likelihoods remains an open optimization issue.

Appendix G: Review of mean–field theory

Mean–field theory approximates the Gibbs distribution with an optimized uncorrelated product distribution, enabling efficient estimates of model expectations and the partition function. Its accuracy improves as correlations vanish, and its partition-function estimate is a lower bound with small observed error in suitable settings.

  • Mean–field approximation: The mean–field approximation chooses an uncorrelated distribution Q(v, h) minimizing KL(Q||P) relative to the Gibbs distribution P(v, h).The product form enables efficient computation and preparation using single-qubit rotations.
  • Mean–field equations: Fixed-point iteration solves the sigmoid mean–field equations for µ_i and ν_j until convergence, with convergence guaranteed when the map’s Jacobian norm is at most 1.The procedure is analogous to Gibbs sampling but remains efficient because it uses a polynomial number of configurations.
  • Use in optimization: Mean–field approximations provide the expectations needed to estimate derivatives of OML, including data-conditioned approximations with visible units fixed.The same methodology applies when approximating distributions conditioned on observed data.
  • Approximation quality: Among product distributions, the optimized Q gives the least error in the log-partition-function approximation.The mean–field parameters minimize KL divergence among product distributions.
  • Approximation quality: The log-partition estimate is a lower bound, and experiments report less than 1% error depending on weight distribution and graph geometry.Structured mean field, TAP, or AIS can reduce errors at higher classical computational cost.
  • Weak-correlation limit: The state-preparation success probability approaches 1 as the maximum interaction strength max_i,j |w_i,j| approaches zero.In this limit, the distribution factorizes, KL divergence approaches zero, and the relevant partition-function ratios approach one.

Appendix H: Review of contrastive divergence training

Contrastive divergence replaces intractable Gibbs-distribution sampling with a finite number of Gibbs-sampling rounds to approximate the model gradient. Increasing the number of rounds improves the approximation, but the method remains limited in model class, training time, and direct applicability to deep networks.

  • Contrastive divergence: Contrastive divergence approximates the model average by drawing samples from a finite-round Gibbs-sampling approximation to the Gibbs distribution.Gibbs sampling alternates hidden-unit and visible-unit updates conditioned on the other layer.
  • Contrastive divergence: CD−1 uses one Gibbs-sampling round, while CD−10 uses ten rounds to obtain a closer approximation to the Gibbs distribution.The resulting hidden probabilities are averaged across training vectors to estimate model-average terms for each weight.
  • Objective approximation: CD−n optimizes the difference between average log-likelihoods after zero and n Gibbs-sampling rounds rather than directly optimizing the maximum-likelihood objective.As n approaches infinity, the contrastive-divergence objective becomes the average log-likelihood and its derivatives are asymptotically correct.
  • Limitations: Contrastive divergence does not permit hidden–visible interactions, can require hours to days of training, and does not directly train deep networks.Deep restricted Boltzmann machines are typically trained layer by layer, which breaks the undirected structure.
  • Quantum background: Quantum states encode amplitudes across exponentially many basis states using a linear number of qubits, with measurement producing basis-state outcomes probabilistically.Quantum computation uses reversible unitary gates, while measurement collapses the state and is not reversible.
Loading 1412.3489v2…