PaperlayerView exact revision on arXiv

Source-linked AI summary

The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine

Brian Coyle, Daniel Mills, Vincent Danos, Elham Kashefi

arXiv:1904.02214v4quant-phcs.LG

TL;DR

The paper asks whether near-term quantum devices can provide provable advantages for a useful machine-learning application despite classical simulation concerns. It introduces Ising Born machines with new training methods, finding improved distribution fitting and classical sampling hardness, while leaving quantum learning supremacy unresolved for specific datasets.

  • Problem

    The paper asks whether near-term quantum machine-learning applications can achieve provably superior performance over all classical alternatives.

  • Method

    The authors define Ising Born machines and develop quantum-kernel MMD, Stein discrepancy, and Sinkhorn divergence training methods with quantum gradients.

  • Results

    The proposed methods outperform MMD with a classical kernel on total variation distance, while model sampling is classically hard up to multiplicative error under standard complexity assumptions.

  • Takeaways & Limitations

    Ising Born machines are candidates for provable quantum advantage in near-term quantum machine learning, and quantum learning supremacy is formalized as a target notion.

  • Takeaways & Limitations

    The Sinkhorn-based approach does not provably achieve quantum learning supremacy for the relevant task because the total-variation upper bound has exponential scaling.

Abstract

from arXiv · show

The search for an application of near-term quantum devices is widespread. Quantum Machine Learning is touted as a potential utilisation of such devices, particularly those which are out of the reach of the simulation capabilities of classical computers. In this work, we propose a generative Quantum Machine Learning Model, called the Ising Born Machine (IBM), which we show cannot, in the worst case, and up to suitable notions of error, be simulated efficiently by a classical device. We also show this holds for all the circuit families encountered during training. In particular, we explore quantum circuit learning using non-universal circuits derived from Ising Model Hamiltonians, which are implementable on near term quantum devices. We propose two novel training methods for the IBM by utilising the Stein Discrepancy and the Sinkhorn Divergence cost functions. We show numerically, both using a simulator within Rigetti's Forest platform and on the Aspen-1 16Q chip, that the cost functions we suggest outperform the more commonly used Maximum Mean Discrepancy (MMD) for differentiable training. We also propose an improvement to the MMD by proposing a novel utilisation of quantum kernels which we demonstrate provides improvements over its classical counterpart. We discuss the potential of these methods to learn `hard' quantum distributions, a feat which would demonstrate the advantage of quantum over classical computers, and provide the first formal definitions for what we call `Quantum Learning Supremacy'. Finally, we propose a novel view on the area of quantum circuit compilation by using the IBM to `mimic' target quantum circuits using classical output data only.

Introduction

The paper asks whether near-term quantum devices can support generative models with provable advantages over classical alternatives. It introduces Ising Born machines and new training objectives to pursue useful, classically hard quantum generative modelling.

  • Near-term devices face limited qubit counts, connectivity, and circuit depth, restricting their ability to run canonical quantum-speedup algorithms.
  • Generative modelling learns a data distribution from finite samples so a model can generate new samples from that distribution.
  • The paper frames its central question as whether a parameterized quantum circuit can provide provably superior machine-learning performance over classical alternatives on near-term devices.
  • The authors define Ising Born machines, a restricted quantum circuit Born-machine subclass, and introduce quantum-kernel MMD, Stein discrepancy, and Sinkhorn divergence training methods.The new cost functions require deriving their gradients in the quantum setting.
  • The proposed methods outperform MMD with a classical kernel by achieving a closer fit measured by total variation distance.
  • Sampling from the model is classically hard up to multiplicative error in the worst case under the non-collapse of the polynomial hierarchy, including many training circuit families.
  • The paper defines quantum learning supremacy as a framework for provable advantage in distribution learning and proposes generative modelling as a useful context retaining provable quantum advantage.

Results

The paper introduces Ising Born Machines, efficient gradient-based training methods, and hardness results for classical simulation. It also formalizes quantum learning supremacy and demonstrates distribution-based quantum circuit compilation.

  • Training: The training framework derives efficient gradients for the Stein discrepancy and Sinkhorn divergence, alongside MMD and quantum-kernel variants.The hybrid procedure uses auxiliary quantum circuits for parameter-shift gradients while the remaining computation is classical.
  • Model: The paper defines Ising Born Machines as quantum circuit Born machines whose restricted two-qubit circuit terms form Ising Hamiltonians.The model uses parameterized quantum circuits and measurement-generated samples for distribution learning.
  • Sinkhorn Complexity: Choosing ϵ = O(n^2) gives regularized Sinkhorn divergence the same sample complexity as MMD and exponentially better scaling than unregularized optimal transport.The authors identify this as a theoretically efficient regularization regime, while noting that lower values may work in practice.
  • Numerical Performance: Sinkhorn divergence and Stein discrepancy achieve lower TV than Gaussian-kernel MMD, with their advantage observed numerically and persisting on Rigetti hardware.The spectral Stein approximation does not outperform MMD, while the Sinkhorn advantage is reported on both simulated and physical devices.
  • Hardness and Quantum Advantage: For many parameter values, the model and its gradient-estimation circuits are hard to simulate classically up to multiplicative error in the worst case.A separate circuit family is shown hard up to additive TV error 1/384 under a conjecture about computing the Ising partition function.
  • Hardness and Quantum Advantage: The paper defines quantum learning supremacy as quantum generative learnability for a distribution class that is not comparably learnable by efficient classical algorithms.It presents this as a framework and potential pathway rather than a demonstrated supremacy result.
  • Quantum Compiling: The IBM can perform weak quantum circuit compilation without extra quantum resources by matching a target circuit’s output distribution rather than its unitary.The authors train an Ising Born Machine with an LSHD cost to mimic a random IQP circuit using a QAOA architecture.

Discussion

The paper introduces the QCIBM as a restricted quantum circuit Born machine with classical-simulation hardness, improved training methods, and applications to quantum circuit compilation. It formalizes quantum learning supremacy while identifying unresolved barriers to proving it for particular datasets.

  • The QCIBM uses the Born rule in a hybrid parameterized quantum circuit to provide a generative machine-learning model.
  • The model is hard to simulate classically up to multiplicative error for many circuit families encountered during gradient-based training.
  • Quantum kernels and new cost functions, including Stein discrepancy and Sinkhorn divergence, improve generative-model training over previous methods.The Sinkhorn regularisation can be chosen for efficient computability as the qubit count grows.
  • The model can heuristically compile one quantum circuit into another through classical optimisation while requiring minimal quantum overhead.
  • Quantum learning supremacy is formalized as a framework, but achieving it for a particular dataset remains unresolved.The paper notes that IQP-like hard distributions may be difficult to test and learn, while the presented methods are not suited to this task.

Methods

The experiments train QCIBMs on randomly generated multimodal binary distributions using QAOA circuits, Adam optimisation, and specified approximations for Stein and MMD calculations.

  • The target distribution is generated from randomly selected binary-string modes, with sample probabilities determined by Hamming distance to those modes.
  • Adam optimisation uses β1 = 0.9, β2 = 0.999, ϵ = 1 × 10^-8, and an initial learning rate ηinit.Adam was selected because it was found more robust to sampling noise.
  • All numerical experiments use a QAOA structure for the underlying QCIBM, with fixed mixer parameters and randomly initialized Ising parameters.
  • The Stein discrepancy uses three Nyström eigenvectors for three qubits and six eigenvectors for four qubits.
  • Gaussian-kernel MMD experiments use bandwidth parameters σ = [0.25, 10, 1000].

I Integral Probability Metrics as Cost Functions

The paper frames distribution discrepancies as integral probability metrics and motivates alternatives to KL divergence because its gradient and probability estimates are computationally difficult for these PQC models.

  • KL divergence is used as a relative benchmark, but its gradient cannot be estimated efficiently for the parameterized quantum-circuit models considered.
  • Computing the required model probabilities is #P-hard, making the KL gradient impractical to compute efficiently.
  • Integral probability metrics are defined by a function class F over the model and target distributions.
  • MMD restricts F to the unit ball of a Hilbert space and is relatively easy to compute with low sample complexity.
  • Total variation is both an integral probability metric and an f-divergence, with its discrete form obtained from a bounded-function space.
  • The Kantorovich metric uses the Lipschitz seminorm and is equivalent to the Wasserstein metric through the Kantorovich–Rubinstein theorem.

II Kernel Methods and the MMD

The paper develops quantum-kernel formulations for MMD by embedding samples into quantum feature spaces, connecting the kernels to Ising-like circuits and estimating them through quantum measurements.

  • A kernel is a symmetric positive-definite function whose Gram matrix is positive semidefinite, while feature maps embed samples into Hilbert spaces.
  • The quantum kernel is defined as the squared overlap κ(x, y) = |⟨Φ(x)|Φ(y)⟩|^2 of quantum feature-map states.
  • The associated quantum RKHS contains functions of the form f(x) = |⟨w|Φ(x)⟩|^2.
  • The feature-map encoding uses diagonal unitaries with the same Ising form as the QCIBM, although an additional diagonal layer means the circuit is not IQP.
  • The quantum kernel requires only single- and two-qubit operations and uses the same entanglement layout and single-qubit rotations as the QCIBM.
  • The kernel is conjectured to be classically hard to estimate to polynomially small error, while quantum devices can estimate it with additive sampling error.
  • MMD compares distributions through the difference in their kernel mean embeddings and can be estimated unbiasedly from independent samples.
  • The MMD estimator has a quadratic convergence rate that does not depend on the sample-space dimension.

III Stein Discrepancy & Score Approximations

The Stein discrepancy compares the model distribution with the data distribution using Stein identities and kernelised forms adapted to discrete sample spaces. Its quantum training gradient differs from MMD through a data-weighted Stein kernel, increasing computational demands while potentially improving distribution comparison.

  • Stein discrepancy: The Stein discrepancy defines a distribution comparison through Stein’s identity and can be kernelised into a closed-form expression.The kernelised form is analogous to MMD but is derived from a Stein operator and function space.
  • Discrete formulation: Discrete Stein discrepancy requires replacing continuous gradients with a discrete shift operator on the sample space.The construction uses cyclic permutations and partial difference operators for binary-string distributions.
  • Discrete formulation: The discrete Stein identity differs from the continuous case because boundary-vanishing restrictions are unnecessary.This distinction applies to functions in the discrete Stein setting, including complex-valued functions.
  • Quantum training: The QCIBM Stein cost compares pθ with π using a π-weighted kernel and requires gradients with respect to circuit parameters.Its gradient uses the Ising Born machine gradient while treating the Stein kernel as parameter-independent.
  • Quantum training: The Stein gradient uses κπ instead of the ordinary MMD kernel κ, making computation harder but potentially providing a more powerful and asymmetric comparison.Quantum-kernel evaluation makes each kernel term efficient, but score-function evaluation remains a separate challenge.

III.1 Computing the Stein Score Function

Computing the Stein score requires data probabilities and probabilities of shifted samples, which are unavailable or difficult for implicit distributions. The paper therefore develops sample-based approximations using Stein-identity inversion and kernel feature maps.

  • Score-function challenge: For each model sample, the Stein score requires π(x) and π(¬_i x) for every coordinate shift.This makes direct score evaluation dependent on probabilities of outcomes that may not be observed in the data.
  • Implicit models: For implicit models, exact score computation is not immediate because classical simulation hardness can make the required probabilities unavailable efficiently.The paper motivates sample-based approaches for models that generate samples without exposing explicit probability densities.
  • Score-function challenge: Empirical-distribution estimates fail when shifted outcomes are absent from the observed data, a problem that worsens as qubit count grows.The score cannot be computed for an outcome whose required shifted probabilities are missing.
  • Identity method: The Identity method approximates the score by inverting Stein’s identity using samples from the data distribution.It represents score values at sampled points and estimates them through a regularised ridge-regression problem.
  • Identity method: The Identity method uses a feature map in an RKHS, with candidate kernels including quantum, Gaussian-mixture, and exponentiated-Hamming kernels.Any chosen feature map must obey the discrete Stein identity.

III.1.2 Spectral Approximation of Stein Score

The Spectral method approximates the Stein score through kernel eigenfunctions estimated with the Nyström method. Because binary strings have 2^n eigenfunctions, the expansion is truncated to the largest eigenvalues.

  • Spectral method: The Spectral method uses Nyström approximation to estimate kernel eigenfunctions relative to the data distribution π.The method adapts a continuous-probability construction to the discrete setting.
  • Spectral method: Quantum kernels provide complex-valued feature-space basis functions that satisfy the discrete Stein identity.The basis functions are orthonormal under the discrete distribution π.
  • Spectral method: The method estimates eigenvalues and eigenvectors from a covariance kernel matrix built from Monte Carlo samples.Sampled eigenfunctions are used to approximate the true eigenfunctions at observed data points.
  • Spectral method: The Spectral method approximates shifted eigenfunctions to obtain an estimator for the Stein score.Applying the discrete shift operator enables approximation of the difference terms required by the score.
  • Spectral method: For binary strings of length n, the eigenfunction count is 2^n, so the score expansion is truncated to the J largest eigenvalues and eigenvectors.This truncation controls the otherwise exponentially large spectral sum.

IV Sinkhorn Divergence & Sample Complexity

The Sinkhorn divergence regularises optimal transport to interpolate between Wasserstein distance and MMD while easing computation. The paper develops its sample-based potentials and gradients, including handling gradients at previously unseen model samples.

  • Optimal transport: Optimal transport compares distributions by finding the lowest-cost coupling that moves mass between them.With metric transport costs, optimal transport yields the Wasserstein metric.
  • Optimal transport: The Wasserstein metric has sample complexity O(1/M^(1/n)) in n dimensions and high computational complexity.These drawbacks motivate regularisation to smooth and simplify the problem.
  • Sinkhorn divergence: Entropy regularisation produces a cost function that interpolates between Wasserstein distance and MMD.This combines MMD’s low sample complexity and ease of computation with desirable Wasserstein properties.
  • Sinkhorn divergence: The Sinkhorn divergence adds autocorrelation terms so the regularised transport cost is unbiased.At extreme regularisation values, it recovers MMD and unregularised optimal transport.
  • Gradient computation: Sinkhorn potentials are computed by iterating the Sinkhorn algorithm until convergence, with iteration requirements depending on ϵ and the problem.The potentials arise from a primal-dual optimal-transport formulation.
  • Gradient computation: The Sinkhorn gradient can be extended to unseen model samples using optimal vectors computed during divergence evaluation.Gradients are obtained by sampling from pθ± and evaluating ϕ(x) with the previously computed vectors.

IV.1 Sample Complexity

This section compares sample-complexity behavior for MMD, Wasserstein distance, and Sinkhorn divergence on distributions over binary vectors. It derives dimension-dependent bounds and discusses regularization choices for controlling dependence on the number of qubits.

  • Sample-complexity comparison: MMD reaches accuracy ϵ with O(ϵ^-2) samples, whereas Wasserstein distance requires O(ϵ^-n) samples for distributions supported in R^n.For binary vectors, the support is the n-dimensional Hamming hypercube.
  • Estimator behavior: The Sinkhorn estimator converges to the true divergence as the sample count M grows, while the regularized optimal-transport theorems incur only constant overhead from the symmetric terms.The convergence and asymptotic statements are presented for empirical distributions and bounded domains.
  • Sinkhorn bounds: Sinkhorn-divergence estimation has bounds depending on the dimension n, the regularization ϵ, the support sizes, and the cost-function constants.The stated theorem assumes bounded subsets of R^n and a smooth Lipschitz cost.
  • Binary-vector setting: Embedding the Hamming hypercube into the unit hypercube with ℓ1 cost gives ||x − y||1 = n and ||c(x, y)||∞ = n.These quantities are used to instantiate the general Sinkhorn bounds for the binary-vector setting.
  • Regularization choice: Choosing Sinkhorn regularization ϵ = O(n^2) can reduce unfavorable dimension dependence and yield polynomial dependence on the number of qubits in the theoretical sample complexity.The authors note that practice may permit substantially smaller regularization without a sample-complexity blow-up.

V Extra Numerical Results

The supplementary experiments compare kernels and training costs across simulated three- and four-qubit systems, real three-qubit hardware, and a compilation example. They reinforce several main-text trends while exposing hardware- and method-specific caveats.

  • Evaluation scope: TV is available as a benchmark for the small examples but cannot generally be computed as the number of qubits scales.This limits direct TV-based evaluation to small systems.
  • Kernel comparison: The quantum kernel κQ provides no obvious training advantage over the Gaussian kernel κG for three qubits and performs slightly worse on average.This behavior remains apparent across a range of learning rates and questions the usefulness of quantum kernels for this task.
  • Simulated training: Both Sinkhorn divergence and Stein discrepancy achieve lower TV values than MMD in the four-qubit simulator experiments.The Sinkhorn result depends strongly on the regularization value and was observed on a particular dataset.
  • Hardware experiments: 500 samples support rapid learning on the QPU, although hardware noise produces higher variance across training runs.For three qubits, Sinkhorn’s simulator advantage over MMD is not observed on real hardware.
  • Hardware experiments: Hardware can achieve lower MMD than the simulator while performing worse in total variation, suggesting that noisy-hardware MMD training may produce overconfident incorrect results.The comparison concerns Supplementary Figure 4’s hardware and simulator conditions.
  • Circuit compilation: The three-qubit QCIBM mimics a random IQP circuit’s output distribution without learning the target circuit’s same parameters.The supplementary compilation example uses a three-qubit QVM and reproduces the output-distribution behavior described for the two-qubit case.

VI.1 Multiplicative Error Hardness of Ising Born Machine Circuits

This section argues that broad families of Ising Born Machine circuits inherit worst-case classical sampling hardness from IQP and QAOA constructions, including heterogeneous parameters and several measurement rotations.

  • Hardness results: The core QCIBM circuit is shown to be classically hard to sample from within multiplicative error by assembling prior IQP and QAOA hardness results.The argument targets uniform circuit families and derives complexity-theoretic consequences from efficient classical simulation.
  • IQP hardness: IQP circuits with homogeneous angles π/8 provide a hard special case whose efficient weak classical simulation would imply PostBPP = PP and collapse PH to the third level.The theorem is stated for output distributions simulated within a specified multiplicative-error range.
  • Parameter generality: The hardness extends from homogeneous to independently parameterized single- and two-qubit gates when irrational-angle repetitions approximate the required π/8 gates.Each gate may have its own approximation error, provided it remains below the fault-tolerant threshold.
  • QAOA extensions: Several QAOA-derived parameter settings are related to postselected universal computation, yielding analogous polynomial-hierarchy-collapse consequences.The construction covers fixed parameters and extends to general diagonal and final-rotation angles through constant or polynomial overheads.
  • Measurement rotations: Hardness also applies to families with final Hadamard-axis or Pauli-Y rotations by relating their output distributions to hard IQP distributions.For a Pauli-Y rotation, choosing Δ_k = π/4 produces samples differing by a bit flip, preserving classical sampling hardness.

VI.2 Total Variation Distance Hardness of Ising Born Machine Circuits

This section connects Ising Born Machine sampling hardness to worst-case and total-variation arguments, then examines whether training and gradient evaluation preserve hard circuit classes.

  • Initialization: Initializing QCIBM parameters in IQP-hard regimes transfers worst-case sampling hardness to the model, although random initialization may also produce barren plateaus.The initialization is chosen to connect the QCIBM to established IQP hardness settings.
  • Partition-function connection: IQP output amplitudes can be expressed through an Ising partition function, linking classical sampling to the complexity of approximating that function.The section compares this relationship with BosonSampling and matrix-permanent computation.
  • TV hardness: If a classical algorithm sampled arbitrary IQP output distributions within additive TV error 1/384, then a BPP^NP algorithm would solve every problem in P^#P, collapsing PH to the third level.This result assumes #P-hardness of approximating |Z|^2 within relative error 1/4 + o(1) for a 1/24 fraction of instances.
  • Gradient evaluation: Parameter-shifted circuits used for gradients differ by single parameter changes that can be reabsorbed while remaining within the hard circuit classes.The argument is presented for all listed cost functions, including MMD, Stein discrepancy, and Sinkhorn divergence.
  • Training dynamics: Training can preserve irrational parameter structure and worst-case hardness across epochs, but updates approaching zero-angle settings can yield a uniform, classically simulatable distribution.With no final measurement rotation, diagonal gates only add phases, which do not affect computational-basis probabilities.
  • Scope and caveats: The hardness claims remain worst-case, so they do not guarantee that a particular trained or implemented instance is difficult to simulate.Computing the proposed intermediate quantum kernel may additionally increase the conjectured classical simulation difficulty of training.

VII Supremacy of Quantum Learning

This section formalizes quantum learning supremacy for distribution learning and distinguishes efficient generation from efficient probability evaluation.

  • QLS framework: The paper introduces a formal definition of quantum learning supremacy for distribution learning, based on classical distribution learnability theory.The proposed framework is intended to identify cases where quantum learning succeeds while classical learning does not.
  • Generators and evaluators: The framework focuses on discrete distributions over n-bit strings and permits classical or quantum generators, with quantum generators producing their own randomness.Evaluators instead output exact point probabilities and use polynomial resources.
  • Generator–evaluator distinction: Even IQP distributions can be efficiently sampled by quantum computers while their output probabilities are #P-hard to compute classically, motivating the generator–evaluator distinction.The paper broadens learnability beyond KL divergence to general cost functions to connect learning with TV-based hardness results.
  • Learnability definitions: A distribution class is (d, ε, C)-learnable when a class-C algorithm learns a generator whose output distribution is within ε under metric d.The learning algorithm receives access to a generator for the target distribution and must run in polynomial time in 1/ε, 1/δ, and n.
  • Operational criterion: QLS occurs when a distribution class is learnable in BQP but not learnable in BPP for the same metric and error tolerance.Total variation is offered as a typical choice of metric, while weaker cost functions are also possible.
Loading 1904.02214v4…