PaperlayerView exact revision on arXiv

Source-linked AI summary

Enhancing Generative Models via Quantum Correlations

Xun Gao, Eric R. Anschuetz, Sheng-Tao Wang, J. Ignacio Cirac, Mikhail D. Lukin

arXiv:2101.08354v1quant-phcond-mat.stat-mechcs.LGstat.ML

TL;DR

The paper asks whether quantum correlations can increase the expressive power of Bayesian-network generative models. It extends these models with basis-enhanced quantum circuits and proves separations associated with nonlocality and contextuality, then reports that the separation also appears on standard data sets.

  • Problem

    Whether a minimal quantum extension of Bayesian networks offers greater expressive power matters because generative models need to capture complex correlations while keeping their structure simple.

    Source: §I · p. 1

  • Method

    The authors extend Bayesian networks to basis-enhanced Bayesian quantum circuits, a tensor-network class, and prove expressivity separations using quantum nonlocality and contextuality.

    Source: §II · p. 2

  • Results

    The proofs establish linear separation in k for k-gram models and quasi-polynomial separation in bond dimension for HMMs, while numerical tests show separation on standard data sets.

    Source: §VI · p. 14

  • Takeaways & Limitations

    Quantum-foundations concepts can inform classical generative models, and the authors identify quantum correlations as a resource for enhancing their efficiency even on classical tasks.

    Source: §VI · p. 15

    The examples studied can be efficiently simulated classically, although some require quantum machines during training.

    Source: §VI · p. 15

Abstract

from arXiv · show

Generative modeling using samples drawn from the probability distribution constitutes a powerful approach for unsupervised machine learning. Quantum mechanical systems can produce probability distributions that exhibit quantum correlations which are difficult to capture using classical models. We show theoretically that such quantum correlations provide a powerful resource for generative modeling. In particular, we provide an unconditional proof of separation in expressive power between a class of widely-used generative models, known as Bayesian networks, and its minimal quantum extension. We show that this expressivity advantage is associated with quantum nonlocality and quantum contextuality. Furthermore, we numerically test this separation on standard machine learning data sets and show that it holds for practical problems. The possibility of quantum advantage demonstrated in this work not only sheds light on the design of useful quantum machine learning protocols but also provides inspiration to draw on ideas from quantum foundations to improve purely classical algorithms.

I. INTRODUCTION

The paper argues that minimal quantum extensions of Bayesian networks can represent distributions that classical counterparts cannot, linking the gap to quantum nonlocality and contextuality. It motivates these models as a way to study expressive power in generative modeling and reports both theoretical separations and practical dataset results.

I. INTRODUCTION

  • The paper asks how generative models might benefit from quantum correlations, since expressive power helps determine whether models capture complex correlations while keeping their structure simple.The introduction notes that the physical origin of potential quantum advantage in quantum machine learning is not well understood beyond abstract complexity arguments.Source: §I · p. 1

II. SUMMARY OF RESULTS AND THEIR IMPLICATIONS

  • Bayesian networks admit a quantum-circuit interpretation, and allowing local measurements beyond the computational basis defines basis-enhanced Bayesian quantum circuits, a tensor-network class inheriting the graph structure.The paper focuses on a minimal quantum extension and relates it to tensor networks.Source: §II · p. 2, §III · p. 4
  • Basis-enhanced 2-gram models represent distributions that no classical k-gram model with k = o(n) can approximate under the stated error model, a separation attributed to quantum nonlocality.The proof uses nonlocal correlations in GHZ-state measurements.Source: §II · p. 2
  • A basis-enhanced model with state-space dimension D cannot be approximated by a translation-form classical HMM with fewer than DΩ(log D) hidden units, a separation attributed to quantum contextuality.The proof strategy connects contextuality to a lower bound on the hidden states needed to represent stabilizer measurements.Source: §II · pp. 2–3
  • On SPECT Heart and Promoter Gene Sequences, basis-enhanced HMMs outperform HMMs on training and testing data, with KL-divergence improvements significant at > 5σ; performance is comparable on biofam.The likelihood-ratio test accounts for potential overfitting from the basis-enhanced model's additional parameters.Source: §II · p. 4
  • For k-gram and HMM models, the extensions can remain classically efficient tensor-network models with minimal computational overhead, while some more complex models such as 2D Bayesian networks cannot be efficiently implemented classically.The authors present the classical cases as quantum-inspired approaches and the more complex cases as relevant to quantum machine-learning design.Source: §II · p. 4

III. UNSUPERVISED GENERATIVE MODELING AND MINIMAL QUANTUM EXTENSIONS

  • Directly representing an n-variable distribution takes exponentially many parameters, whereas underlying structure can make polynomial-size representations sufficient for many natural distributions.The paper focuses on Bayesian networks and a minimal quantum extension, while noting that the approach can extend beyond Bayesian networks.Source: §III · p. 4

A. Bayesian Networks and Language Processing

The section develops a minimal quantum extension of Bayesian-network generative models and explains how it relates to tensor networks. It sets up comparisons between classical and quantum models using KL-divergence error criteria.

A. Bayesian Networks and Language Processing

  • Bayesian networks specify joint distributions by multiplying each node’s transition probability conditioned on its parents, and k-gram models are a 1D Bayesian-network form used in language modeling.HMMs generalize k-gram models with hidden nodes that store correlations and can represent conditional translation distributions.Source: A. Bayesian Networks and Language… · pp. 4–5

B. Bayesian Quantum Circuits and Minimal Quantum Extensions

  • Bayesian quantum circuits reproduce Bayesian-network distributions through computational-basis measurements, using sequences of uniformly controlled gates subject to directed-acyclic-graph restrictions.The gate restrictions encode one target variable per transition and prevent a qubit from being targeted after it has served as a control.Source: B. Bayesian Quantum Circuits and… · p. 5, §1 · p. 5

1. Bayesian Quantum Circuits

  • A uniformly controlled gate applies a single-qubit unitary to its target, selected by the state of its control qubits.The corresponding implementation can be inefficient in general, though common structured or low-dependency transitions can make it easier.Source: §1 · p. 5

2. Basis-Enhanced Bayesian Quantum Circuits

  • BBQCs minimally extend BQCs by allowing arbitrary local measurement bases, retaining locality while enabling quantum advantages associated with nonlocality and contextuality.The paper states that this unconditional correlation-based separation is more modest than its complexity-theory-based argument.Source: §2 · p. 6

3. BBQCs as Tensor Networks

  • BBQCs remain tensor networks; for a k-gram model their MPS bond dimension is bounded by 2^(k−1).The paper relates the exponent to the maximum information transmitted through a qubit and says changing the measurement basis does not increase the bond dimension.Source: §3 · p. 6

IV. PROVABLE EXPRESSIVITY SEPARATION THROUGH QUANTUM CORRELATIONS

  • The paper compares BQCs and BBQCs on sequential data and uses nonlocality and contextuality to establish unconditional separations between classical k-gram/MPS and HMM/MPO models.It presents quantum correlations as resources for generative-model advantage in some toy models.Source: §IV · p. 6

A. Error Models

  • The comparison measures classical models’ ability to generate BBQC distributions with KL divergence; the stated error model requires both forward and reverse divergences to be finite.The paper describes multiplicative error as stronger and less realistic than finite KL divergence.Source: A. Error Models · p. 6

B. A Toy Model: k-gram Models and Quantum Nonlocality

The section constructs a basis-enhanced 2-gram model whose measurement correlations cannot be reproduced by short-memory classical k-gram models under the stated error criterion. Its argument uses a GHZ-state construction and a local-hidden-variable reduction.

B. A Toy Model: k-gram Models and Quantum Nonlocality

  • The basis-enhanced 2-gram model embeds a GHZ state in a cluster state, with measurement settings selecting X or Y bases for the physical qubits.Measuring the other qubits in X can leave a GHZ state up to Pauli corrections; the relevant three-variable outcomes obey a constraint that local hidden-variable theories cannot satisfy.Source: B. A Toy Model: k-gram Models and… · p. 7
  • For k < ⌊(n−1)/2⌋, classical k-gram models cannot approximate the constructed BBQC distribution under finite-KL error; the separation is 2 versus O(n).The proof conditions on intermediate variables and maps the resulting classical distribution to a local hidden variable theory.Source: B. A Toy Model: k-gram Models and… · p. 7
  • Conditioning on intervening variables fixed to zero separates the three selected k-gram factors, each depending on only one selected variable, yielding a local-hidden-variable description.The selected variables are more than 2k positions apart, so their factors can be normalized as local response probabilities independent of the other measurement settings.Source: B. A Toy Model: k-gram Models and… · p. 7

1. Ontological Theories and Hidden Markov Models

  • An ontological model assigns a hidden state distribution to a quantum state, specifies measurement outcomes, and allows measurement-dependent transitions between hidden states.The text identifies an HMM as equivalent to this representation when its hidden state includes the ontological state, input, and output.Source: §1 · p. 8

2. Ontological Theories Representing Quantum States

Ontological theories represent quantum states using probability distributions over shared hidden variables, while sequential simulation requires memory of measurement histories. The Mermin–Peres magic square shows that contextuality can rule out a hidden variable shared by certain quantum states.

2. Ontological Theories Representing Quantum States

  • Quantum states are represented by probability distributions over shared hidden variables, with their supports recording which variables can represent each state.Under the stated error model, whether a measurement probability is zero matters, not its precise value.Source: §2 · p. 8
  • To simulate sequential measurements, an HMM must retain enough memory of previous measurement bases and outcomes to predict future behavior.The HMM state at each time step is a distribution over hidden states, and different histories are combined by taking unions of their supports.Source: §2 · p. 9

3. No Common Hidden Variables in the Mermin–Peres Magic Square

  • For the Mermin–Peres construction, three stabilizer states cannot share a common hidden variable because the resulting measurement predictions contradict quantum mechanics.The contradiction uses the states’ stabilizers, including a measurement of Y1Y2.Source: §3 · pp. 9–10, §2 · p. 9

4. Bounding the Efficiency of Hidden Markov Models

The section bounds the hidden-state resources needed to simulate stabilizer measurements and compares them with a basis-enhanced 2-gram model. The resulting gap persists for HMMs without translational invariance.

4. Bounding the Efficiency of Hidden Markov Models

  • The ontological theory requires at least |S|/m state variables; Lemma 2 concludes m ≤ 2^(n^2/4+7n/2) after showing any subset of stabilizer states larger than that threshold contains three states forming a Mermin-Peres magic square.Source: §4 · p. 10
  • Classical translation-form HMMs require at least 2^Ω(n^2) hidden states, while a basis-enhanced 2-gram model uses 2^O(n), yielding a separation of D^Ω(log D).Here n is the number of qubits, and D is the basis-enhanced model’s state-space dimensionality.Source: §4 · p. 10
  • The lower-bound argument is not restricted to stabilizer states and also applies to HMMs without translational invariance.The latter extension follows by relabeling the time-dependent quantities.Source: §4 · p. 10

5. A Basis-Enhanced 2-gram Model from Stabilizer States

A basis-enhanced 2-gram model simulates Pauli measurements on stabilizer states with exponentially fewer internal states than the classical HMM lower bound. The paper also describes numerical testing and a tensor-network approach to simulating these models.

5. A Basis-Enhanced 2-gram Model from Stabilizer States

  • A basis-enhanced 2-gram model simulates Pauli measurements on stabilizer states using O(n) qubits, while any classical HMM requires at least 2^Ω(n^2) hidden states.The model has D = 2^O(n) internal states and is also representable as a 2D Bayesian network.Source: §5 · p. 11, Figure 5 · p. 11

V. NUMERICAL TESTS ON REAL WORLD DATA

  • The numerical tests compare classical HMMs and basis-enhanced 2-gram models using forward KL divergence, with the stated aim of testing practical advantage and robustness to other error models.The divergence is estimated stochastically because summing its exponentially many terms is intractable in practice.Source: §V · pp. 11–12

A. Simulation of Basis-Enhanced 2-gram Models

  • Low-bond-dimension basis-enhanced 2-gram models can be simulated with tensor networks, and their unitary parameters are optimized using gradients on the unitary manifold.The implementation precomputes shared tensor contractions within each training mini-batch.Source: A. Simulation of Basis-Enhanced 2-gram… · p. 12

B. Model Training

The section describes training procedures for classical and basis-enhanced sequence models, then reports their performance on three datasets. The conclusion connects the expressive-power separation to quantum nonlocality and contextuality and identifies boundaries for extending the approach.

B. Model Training

  • Classical HMMs use Baum–Welch training, while basis-enhanced models use classically efficient tensor-network gradients and unitary-constrained Riemannian gradient descent.The unitary-space update addresses the fact that ordinary gradient descent would generally violate circuit unitarity; the update is modified to include momentum.Source: B. Model Training · pp. 12–13

C. Model Comparison on Data Sets

  • The data comparison treats biofam as a control with local correlations and tests generalization using withheld data or the standard SPECT Heart test set.The models were evaluated over ten trials, with the minimum achieved loss used to compare expressive power.Source: C. Model Comparison on Data Sets · pp. 13–14
  • The basis-enhanced 2-gram model outperformed the classical HMM on Promoter Gene Sequences and SPECT Heart, while both performed equally well on biofam.The improvement on Promoter Gene Sequences and SPECT Heart was significant at 5σ confidence under a likelihood-ratio test.Source: C. Model Comparison on Data Sets · p. 14

VI. CONCLUSION AND OUTLOOK

  • The theoretical separation is associated with quantum nonlocality and contextuality, yielding linear k-gram and quasi-polynomial HMM bond-dimension separations.The paper also reports numerical evidence that the separation holds on practical datasets.Source: §VI · p. 14
  • The approach may extend to broader models, but counting methods do not directly cover non-energy-based neural networks with real-valued hidden units.The conclusion also notes that some example models require quantum machines during training, despite being efficiently simulable classically.Source: §VI · pp. 14–15
  • The authors connect quantum foundations to machine learning and propose using those ideas to develop quantum-inspired classical and quantum models.They identify MPS, tree-like tensor networks, and MERA as possible directions.Source: §VI · p. 15

Appendix A: Relations Among Various Machine Learning Models

The appendix relates common sequence models, maps Bayesian networks to Bayesian quantum circuits, and describes when collective gates can implement structured transitions with depth independent of parent count.

Appendix A: Relations Among Various Machine Learning Models

  • A deep belief net has the form of a 2-gram model when its hidden variables are also observed.The appendix also gives a relation between deep belief nets and this sequence-model family.Source: Appendix A · p. 15
  • A k-gram model can be simulated by an HMM using L^(k−1) hidden variables per site, where L is the vocabulary length.The construction groups k−1 sites of the k-gram model into one HMM site.Source: Appendix A · p. 15

1. Mapping Between Bayesian Networks and Quantum Circuits

  • A Bayesian network maps to a Bayesian quantum circuit by assigning each node a qubit and encoding its marginal or conditional probabilities in state preparation and uniformly controlled gates.Measuring the circuit in the computational basis produces the same probability distribution as the corresponding Bayesian network.Source: §1 · p. 15, Figure 9 · p. 16

2. Efficient Implementation Using Multi-Qubit Collective Gates

  • Uniformly controlled gates are not generally efficient to implement, but the paper gives an approximate collective-gate construction for transitions structured as a function of a weighted sum of parent variables.For bounded-derivative functions, the construction can use depth polynomial in log(1/ϵ), independent of the number of parents k.Source: §2 · pp. 16–17

3. Exponential Separation of Expressive Power Between BBQCs and Bayesian Networks Based on Computational Complexity Theory

This section presents a complexity-theoretic route to separating basis-enhanced Bayesian quantum circuits from classical Bayesian networks. Its argument uses a hard-to-compute probability construction and a conditional consequence for the polynomial hierarchy.

3. Exponential Separation of Expressive Power Between BBQCs and Bayesian Networks Based on Computational Complexity Theory

  • Under the stated theorem, a polynomial-parameter Bayesian network approximating the constructed BBQC under multiplicative error would imply collapse of the polynomial hierarchy to its third level.The theorem is attributed to Ref..Source: §3 · p. 17, a. Related Computational Complexity… · p. 17

a. Related Computational Complexity Classes

  • The proof’s complexity consequence relies on a hierarchy whose levels generalize P and NP, with non-collapse widely believed.The polynomial hierarchy is described using oracle access to lower levels.Source: a. Related Computational Complexity… · p. 17

b. The Basis-Enhanced Bayesian Network Used in the Proof

c. Sketch of the Proof

The proof sketch uses the complexity of approximating the constructed distribution’s probabilities to derive a polynomial-hierarchy consequence. The accompanying section defines inference and training for generative models and describes KL-divergence optimization.

c. Sketch of the Proof

  • If a Bayesian network approximated the constructed probability q(x) under multiplicative error, Stockmeyer’s theorem would place the approximation in Σp_2, leading to a polynomial-hierarchy collapse.The construction’s multiplicative-error probability computation is #P-hard; the proof sketch notes that its approximation argument is nonconstructive.Source: c. Sketch of the Proof · p. 18
  • The nonconstructive argument establishes existence of a polynomial-size classical circuit for each fixed input size, but not an efficient procedure to construct it.The passage distinguishes this result from the separate construction of a BBQC whose probability computation is #P-hard.Source: c. Sketch of the Proof · p. 18

4. Algorithms for Inference and Learning

  • Inference extracts information such as marginal or conditional probabilities, while training chooses model parameters to approximate the data distribution.Training is described as minimizing KL divergence between the data distribution and the model distribution, commonly through gradient descent.Source: §4 · pp. 18–19

a. Heuristic Quantum Algorithms for Inference and Learning

The section discusses heuristic quantum algorithms for Bayesian-network learning and inference, then develops error-model relations and Mermin–Peres magic-square lemmas. These results connect computational approaches with bounds on classical representations of stabilizer measurements.

a. Heuristic Quantum Algorithms for Inference and Learning

  • Quantum learning and inference can be framed as local-Hamiltonian ground-state preparation, with runtime proportional to the inverse energy gap but no guaranteed inverse-polynomial gap.Exact training and inference are computationally difficult for both classical Bayesian networks and BBQCs; heuristic algorithms are proposed for each.Source: a. Heuristic Quantum Algorithms for… · p. 19

Appendix C: Relations Among Various Error Models

  • For translation models, avoiding assumptions on the prior requires matching the zero-probability supports of p(y | x) and q(y | x) for every x and y.The passage states that q(y | x) = 0 if and only if p(y | x) = 0.Source: Appendix C · p. 19
  • A multiplicative-error bound implies bounded KL divergences in both directions, which in turn implies the error model in Eq. (1).The passages also state that this implication holds with γ smaller than 1/2 and that the multiplicative-error requirement is stronger than requiring small KL divergence.Source: Appendix C · p. 19

Appendix D: Lemma Proofs for the Mermin–Peres Magic Square

  • More than 2n2/4+7n/2 stabilizer states guarantee three states whose stabilizers form a Mermin–Peres magic square.The proof reduces the states to graph-state forms and constructs a square whose commuting observables exhibit contextuality.Source: Appendix D · p. 20
  • If three stabilizer states and selected stabilizers form a Mermin–Peres magic square, their supports must have empty intersection in an ontological theory consistent with quantum mechanics.A common support element would force a deterministic +1 result, while the resulting states after measurement are orthogonal, producing a contradiction.Source: Appendix D · p. 20

Appendix E: Robust Separation of k-gram Model Under l1-Distance

This appendix proves a robust l1-distance separation between a particular basis-enhanced 2-gram model and k-gram models with k < n/6. The proof uses GHZ-type measurements, which retain nonlocality with probability greater than 1/9.

Appendix E: Robust Separation of k-gram Model Under l1-Distance

  • 1/288 is a lower bound on the l1-distance: for k < n/6, no k-gram model can approximate the specified basis-enhanced 2-gram distribution more closely.The appendix derives the separation by combining its GHZ-test lemmas.Source: Appendix E · pp. 21, 23
  • The proof uses a Bell test on the GHZ state with X- and Y-basis measurements, while noting that the restricted bases do not always yield the state up to local unitaries.The lemma bounds the probability that nonlocality remains despite this restriction.Source: Appendix E · p. 21
  • More than 1/9 of measurements of the remaining qubits yield a GHZ state up to Pauli and S gates, defining the appendix's GHZ-type measurement.The proof analyzes the single-qubit Clifford gates through a random walk among six elements of S3.Source: Appendix E · p. 21

Appendix F: HHM to Simulate Fig. 2(a)

The appendix describes an HMM representation of the process in Fig. 2(a), with an upper bound on its hidden variables given by the number of quantum states involved.

Appendix F: HHM to Simulate Fig. 2(a)

  • The number of quantum states involved in the Fig. 2 process upper-bounds the number of hidden variables in its HMM representation.The evolution is driven by measuring the first qubit in each pair.Source: Appendix F · p. 23
  • The second qubit in each pair stores a single-qubit stabilizer state in this representation.The passage describes its evolution as driven by measurements of the first qubit.Source: Appendix F · p. 23
  • Only six single-qubit stabilizer states are involved: |0⟩, |1⟩, |+⟩, |−⟩, |+i⟩, and |−i⟩.Source: Appendix F · p. 23

Appendix G: Supplemental Numerics Figures

The supplemental passage identifies Fig. 12 as a tensor-network representation of the derivative of the loss function in Eq. (20).

Appendix G: Supplemental Numerics Figures

  • Figure 12 plots the tensor network representation of the derivative of the loss function in Eq. (20), as stated in the cited passage.Source: Appendix G · p. 23
Loading 2101.08354v1…