PaperlayerView exact revision on arXiv

Source-linked AI summary

Unsupervised Machine Learning on a Hybrid Quantum Computer

J. S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Didier, E. Schuyler Fried, S. Hong, P. Karalekas, C. B. Osborn, A. Papageorge, E. C. Peterson, G. Prawiroatmodjo, N. Rubin, Colm A. Ryan, D. Scarabelli, M. Scheer, E. A. Sete, P. Sivarajah, Robert S. Smith, A. Staley, N. Tezak, W. J. Zeng, A. Hudson, Blake R. Johnson, M. Reagor, M. P. da Silva, C. Rigetti

arXiv:1712.05771v1quant-ph

TL;DR

The paper addresses how classical learning and optimization can be hybridized with near-term quantum processors for unsupervised clustering. It trains a 19-qubit processor with QAOA and gradient-free Bayesian optimization, finding that the hybrid approach reaches optimal solutions in fewer steps than uniform random sampling and remains effective under realistic noise.

  • Problem

    The paper studies how to use near-term quantum processors for an unsupervised clustering task while combining quantum circuits with classical optimization.

  • Method

    The authors translate clustering into a weighted Maxcut problem and optimize QAOA circuit angles with gradient-free Bayesian optimization.

  • Results

    The 19-qubit implementation reaches optimal solutions in many fewer steps than uniform random sampling, with experimental behavior rejecting the random-sampling explanation above 99%.

  • Takeaways & Limitations

    Classical optimization can train the quantum clustering algorithm around realistic coherent and incoherent imperfections.

  • Takeaways & Limitations

    Gaussian-process updates require matrix inversion scaling as O(m^3), which can become prohibitively expensive as the number of samples grows.

Abstract

from arXiv · show

Machine learning techniques have led to broad adoption of a statistical model of computing. The statistical distributions natively available on quantum processors are a superset of those available classically. Harnessing this attribute has the potential to accelerate or otherwise improve machine learning relative to purely classical performance. A key challenge toward that goal is learning to hybridize classical computing resources and traditional learning techniques with the emerging capabilities of general purpose quantum processors. Here, we demonstrate such hybridization by training a 19-qubit gate model processor to solve a clustering problem, a foundational challenge in unsupervised learning. We use the quantum approximate optimization algorithm in conjunction with a gradient-free Bayesian optimization to train the quantum machine. This quantum/classical hybrid algorithm shows robustness to realistic noise, and we find evidence that classical optimization can be used to train around both coherent and incoherent imperfections.

INTRODUCTION

The paper frames clustering as an unsupervised learning task that assigns labels using pairwise similarity, then maps it to a weighted Maxcut optimization problem. Maxcut is computationally difficult but broadly applicable to combinatorial problems.

  • Clustering: Clustering assigns similar data elements the same label and dissimilar elements different labels using a chosen distance measure.Pairwise distances form a graph whose edge weights represent dissimilarity.
  • Clustering: Maximizing distances between vertices assigned different labels provides a natural clustering objective formulated as a Maximum-Cut problem.The distance matrix serves as the weighted graph for the Maxcut formulation.
  • Maxcut: Maxcut partitions an undirected weighted graph into two sets and sums the weights of edges crossing between them.The cut cost is defined by the weights connecting the two disjoint vertex sets.
  • Maxcut: Maxcut is NP-complete and can represent problems including scheduling, computer-aided design, traffic management, image recognition, and QUBO optimization.The paper uses a physical interacting-spin system whose ground state encodes the solution.

QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM

QAOA prepares a superposition of bit strings using alternating cost and driver operations, then measures the state to seek low-energy solutions. Its performance depends on selecting suitable circuit angles.

  • QAOA: QAOA is a heuristic for preparing a superposition whose probability amplitudes concentrate around solutions of a combinatorial optimization problem.The problem is encoded in a cost Hamiltonian.
  • QAOA: QAOA begins with an equal superposition, alternates cost and driver unitaries, and measures the resulting state in the computational basis.At iteration i, the cost unitary uses γ_i and the driver unitary uses β_i.
  • Circuit: Each circuit iteration applies the cost interactions followed by single-qubit X rotations, with β and γ selected by the optimization routine.The illustrated circuit uses three independent interaction rounds before measurement.
  • Optimization: With optimal angles, the probability of sampling the lowest-energy bit string increases with iterations and approaches unity as iterations grow.QAOA itself does not specify how to find the optimal angles in general.

BAYESIAN OPTIMIZATION

The paper uses Bayesian optimization to select QAOA angles by modeling noisy objective evaluations and choosing informative sampling points. The experiments use a Rigetti 19Q processor and compare optimization traces with random sampling.

  • Bayesian optimization: Bayesian optimization searches QAOA angles by sequentially evaluating a black-box objective and updating a prior over functions.Here, the objective is the best sampled bit-string value at each angle pair.
  • Bayesian optimization: The optimizer uses posterior-derived utility to choose evaluation points and reduce costly black-box evaluations instead of randomly walking the parameter space.The posterior balances uncertainty with the search for high-value regions.
  • Quantum processor: The Rigetti processor contains tunable and fixed-frequency transmons coupled in a lattice, with one fabrication defect leading to its treatment as a 19-qubit device.Some couplers are omitted, producing three-fold rather than four-fold connectivity.
  • Problem instance: The clustering instance uses randomly chosen edge weights derived from overlaps between neighboring probability distributions and maps them onto the chip connectivity.The corresponding Maxcut graph labels vertices by qubits and colors them by the solution.

IMPLEMENTATION

The implementation matches the clustering Hamiltonian to the Rigetti 19Q connectivity and keeps the QAOA circuit shallow. The hybrid software runs parameterized circuits on the processor and uses Bayesian optimization to update classical parameters.

  • Problem implementation: The clustering Hamiltonian is constructed to match Rigetti 19Q connectivity, reducing circuit depth while using all available qubits.The task clusters overlapping probability distributions using the Bhattacharyya coefficient as a dissimilarity measure.
  • Circuit implementation: The cost unitary fits within a circuit depth corresponding to six CZ gates interspersed with single-qubit operations.Three rounds of non-overlapping interactions are required because some graph vertices have three neighbors.
  • Software: The algorithm is implemented in Python with pyQuil and Forest, while the Bayesian optimizer uses the BayesianOptimization package.Forest controls the quantum computer and accesses generated data.

RESULTS

The 19-qubit hybrid clustering algorithm frequently reached known optima, doing so in fewer steps than uniform random sampling and outperforming that null model statistically.

  • RESULTS: The algorithm reached the optimum in fewer than 55 Bayesian optimization steps for the vast majority of random problem instances.Approximately 25% of runs did not reach the optimum within 55 steps.
  • RESULTS: Approximately 10 minutes covered 55 Bayesian optimization steps with N = 2500 measurements per step, including quantum–classical communication and scheduling overhead.
  • RESULTS: Kolmogorov-Smirnov tests excluded uniform random bit-string sampling as an explanation for experimental behavior at a level higher than 99%.The corresponding noiseless simulation excluded the null hypothesis at a level higher than 99.99%.
  • RESULTS: The experiment demonstrated a 19-qubit hybrid quantum algorithm for clustering using Bayesian optimization of classical parameters within QAOA.

SUPPLEMENTARY INFORMATION

The supplementary procedure maps weighted Maxcut instances to an Ising Hamiltonian and uses QAOA sampling distributions whose cost statistics are optimized experimentally.

  • SUPPLEMENTARY INFORMATION: Missing edges are added with zero weights to lift an arbitrary n-node graph to a fully connected graph K_n before constructing the Ising formulation.Symmetric edge weights and spin variables s_j ∈ {−1, +1} encode the bipartition.
  • SUPPLEMENTARY INFORMATION: The quantum Maxcut formulation uses qubit spin operators and an additional minus sign so the optimal solution is the minimum-energy state.
  • SUPPLEMENTARY INFORMATION: The Bayesian optimization trace represents sampled cost distributions with kernel-density violins whose widths show sampling frequency and internal lines mark 1σ and 2σ intervals.
  • SUPPLEMENTARY INFORMATION: Selected QAOA angles produced distributions that sampled large costs corresponding to approximate solutions of the random Maxcut instance.

Clustering on a fully connected graph

For a 20-point, fully connected clustering instance, QAOA found good solutions while sampling only a small fraction of the bit-string state space, and optimization improved the best observed cost.

  • Clustering on a fully connected graph: The 20-point dataset forms two visually distinguishable clusters, and its pairwise Euclidean distances define the adjacency matrix for Maxcut clustering.
  • Clustering on a fully connected graph: Random sampling has probability 2/2^20 ≈ 2 · 10^-6 of finding either optimal bit-string, requiring approximately 2^19 samples for significant success probability.
  • Clustering on a fully connected graph: Each QAOA evaluation sampled N = 250 strings, only 250/2^20 ≈ 0.02 of the full state space, yet the procedure found good solutions for this non-trivial instance.
  • Clustering on a fully connected graph: The optimized sampling procedure corresponds to a 100× improvement over uniform sampling when the correct bit-string is prepared.
  • Clustering on a fully connected graph: The optimizer gradually improved its best observed cost while increasingly sampling distributions with large standard deviations.

Construction of the optimization functional

The optimization functional treats QAOA outputs as parameterized random distributions and optimizes selected order statistics, especially extreme sampled costs.

  • Construction of the optimization functional: The cost function transforms the bit-string distribution D_x(θ) into a real-valued distribution D_f(θ) with corresponding probability and cumulative distribution functions.
  • Construction of the optimization functional: A QAOA run prepares bit strings x with probability p(x; θ) = |ψ(x; θ)|^2, defining a parameterized distribution D_x(θ).
  • Construction of the optimization functional: Order statistics F_(j) sort the costs from N independent experiments, enabling percentile-based optimization objectives.
  • Construction of the optimization functional: The procedure primarily minimizes the first-order statistic or maximizes the N-th order statistic to target extreme sampled costs.
  • Construction of the optimization functional: Numerical evaluation of these statistics also provides uncertainty estimates for the sampled distribution.

Gaussian Process description of the extreme value optimization

The method models noisy, expensive QAOA extreme-value statistics with a Gaussian process and uses Bayesian optimization to select evaluations that balance exploration and exploitation.

  • Gaussian-process model: Extreme-value functions are expensive and generally unknown, so the method evaluates them at sampled QAOA angles and models noisy observations with a Gaussian process.Finite sampling and imperfect gate and readout fidelities make observations differ from the underlying statistic.
  • Gaussian-process model: The Gaussian-process prior assumes the extreme-value statistic varies as a Gaussian function of the QAOA parameters, with a Matérn-2.5 kernel specifying correlations.The Gaussian assumption is described as a practical unbiased prior despite not necessarily being true.
  • Posterior updates: Bayesian optimization updates the Gaussian-process posterior analytically after each noisy observation using the properties of multivariate normal distributions.The procedure sequentially conditions the prior on newly sampled values.
  • Computational limitation: Gaussian-process updates require matrix inversion scaling as O(m^3), which can become prohibitively expensive as the number of samples increases.The passage identifies improved scaling and surrogate methods as active research directions.
  • Sampling strategy: The acquisition function selects the next QAOA angle by balancing exploration of uncertain regions against exploitation near the best known value.Its explore-exploit behavior is controlled by β_m, while μ_m(θ) and σ_m(θ) provide the posterior mean and variance.

Comparison to Random Sampling

The evaluation compares Bayesian optimization with random sampling across multiple Maxcut instances using optimization traces and empirical time-to-optimum distributions. The reported eCDF comparison rejects the hypothesis that both procedures share the same underlying distribution.

  • Experimental comparison: Five randomly chosen problem instances were run over fourteen hours on the 19Q architecture, with time-to-optimum measured as steps until the optimal value was reached.The optimal value was readily estimated for these problem instances.
  • Experimental comparison: The eCDF of Bayesian-optimization time-to-optimum was compared with a Bernoulli-based random-sampling CDF and the exact random-sampling CDF.The comparison used optimization traces and empirical cumulative distributions.
  • Optimization traces: Most traces reached the optimal cost well before the 55-step cutoff in 83 independent 19Q runs.The traces corresponded to a fixed random Maxcut instance.
  • Statistical test: KS_23,55 ≈0.392 was obtained for the empirical CDFs shown in Fig. S4b.The Kolmogorov-Smirnov statistic compares the two empirical cumulative distributions.
  • Statistical test: α = 8.451 · 10^-4, allowing rejection of H0 with probability p = 1 − α for the compared empirical CDFs.H0 states that the two eCDFs arise from the same underlying distribution function.

Example of a clustering application for the 19Q architecture

The clustering application represents compact-support distributions in R2 through pairwise overlap similarities, then uses the resulting graph to formulate assignments for distributions with minimal overlap.

  • Similarity construction: The Bhattacharyya coefficient provides a similarity measure between the distributions.It is used despite not satisfying the triangle inequality required of a typical distance metric.
  • Graph construction: Pairwise overlaps are encoded as weighted edges in a graph whose vertices identify the individual distributions.The graph construction supports mapping the clustering problem onto the architecture.

Detailed device parameters

The supplementary material summarizes Rigetti 19Q device, gate, readout, and two-qubit performance parameters measured at approximately 10 mK, including exclusions for a non-tunable qubit.

  • Device characterization: Tables S2 and S3 summarize the main performance parameters of the Rigetti 19Q processor.Single-qubit gate fidelities were estimated with randomized benchmarking, while two-qubit fidelities used quantum process tomography.
  • Device characterization: The reported T1 and T* parameters were measured at base temperature T ≈10 mK.The table caption identifies this as the measurement temperature.
  • Readout and gate metrics: Readout fidelity is defined as F_RO = [p(0|0) + p(1|1)]/2.Here p(b|a) is the probability of measuring state b when the qubit was prepared in state a.
  • Two-qubit parameters: Qubit 3 is not tunable, so parameters for the 3−8 and 3−9 pairs are omitted from the two-qubit table.The exclusion applies specifically to interactions involving those pairs.
Loading 1712.05771v1…