PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Hopfield neural network

Patrick Rebentrost, Thomas R. Bromley, Christian Weedbrook, Seth Lloyd

arXiv:1710.03599v3quant-ph

TL;DR

The paper addresses how quantum algorithms can improve Hopfield-network storage and operation for pattern recognition, reconstruction, and optimization. It encodes the network in quantum-state amplitudes, introduces quantum Hebbian learning, and uses matrix inversion to obtain logarithmic dependence on data dimension, with an RNA-sequence recognition application.

  • Problem

    The paper examines how quantum computing can improve the storage capacity and computational speed of Hopfield-network methods for pattern recognition, reconstruction, and optimization.

  • Method

    The method encodes Hopfield-network states in quantum amplitudes, represents the weight matrix as a density matrix using quantum Hebbian learning, and applies quantum matrix inversion.

  • Results

    Logarithmic dependence on data dimension is obtained for the quantum operation approach, with comparable reconstruction performance to the conventional approach in the RNA-sequence application.

  • Takeaways & Limitations

    An exponentially large Hopfield network can be represented with a polynomial number of qubits, and the method can recognize partially specified H1N1 RNA sequences.

Abstract

from arXiv · show

Quantum computing allows for the potential of significant advancements in both the speed and the capacity of widely used machine learning techniques. Here we employ quantum algorithms for the Hopfield network, which can be used for pattern recognition, reconstruction, and optimization as a realization of a content-addressable memory system. We show that an exponentially large network can be stored in a polynomial number of quantum bits by encoding the network into the amplitudes of quantum states. By introducing a classical technique for operating the Hopfield network, we can leverage quantum algorithms to obtain a quantum computational complexity that is logarithmic in the dimension of the data. We also present an application of our method as a genetic sequence recognizer.

I. INTRODUCTION

The paper adapts Hopfield networks to quantum computing, motivated by potential quantum speedups and compact amplitude-based representations. It introduces qHop, quantum Hebbian learning, and matrix-inversion-based operation for pattern-related tasks.

  • Motivation: Quantum machine learning combines quantum subroutines with established machine-learning algorithms to seek computational speedups.The paper situates qHop within developments including quantum linear algebra, amplitude amplification, and quantum annealing.
  • Hopfield networks: Hopfield networks are single-layer recurrent networks that support pattern recognition, reconstruction, and optimization as content-addressable memories.Their neurons update according to weighted connections among the network's units.
  • Quantum adaptation: The paper focuses on Hopfield networks because their fully visible structure allows information to be encoded directly into quantum-state amplitudes.This encoding enables the use of quantum phase estimation and matrix inversion in suitable cases.
  • Contribution: The proposed qHop stores network states in qubit amplitudes and introduces quantum Hebbian learning to represent the weighting matrix as a density matrix.The method also adapts the classical Hopfield network for information erasure and uses matrix inversion to optimize its operation.
  • Contribution: The approach targets exponentially large networks represented with polynomially many qubits and quantum operation times logarithmic in the data dimension.The paper additionally presents a genetic-sequence-recognition application.

II. NEURAL NETWORKS

This section defines neural networks through binary neuron states, graph connectivity, and weighting matrices, then specializes these ideas to the fully visible, undirected Hopfield network trained with Hebbian learning.

  • Neural-network representation: A neural network consists of neurons whose activation pattern is connected through a real square weighting matrix W.The matrix elements wij specify connection strengths between neurons i and j.
  • Training: Training sets the weighting matrix using known activation patterns and learning methods such as backpropagation, gradient descent, or Hebbian learning.In a fully visible network, every neuron serves as both input and output.
  • Hopfield network: The Hopfield network is a single-layered, fully visible, undirected neural network trained with the Hebbian rule.Its weighting elements reflect how often neuron pairs fire together across M training patterns.
  • Weighting matrix: The identity matrix I_d appears in the normalized weighting-matrix construction.Here I_d denotes the d-dimensional identity matrix.

III. QUANTUM NEURAL NETWORKS

The paper encodes activation patterns as amplitudes of quantum states rather than assigning one qubit to each neuron. This reduces the qubit representation overhead to logarithmic scaling in the number of neurons, subject to efficient state preparation.

  • Amplitude encoding: The method associates a d-dimensional activation pattern with a pure quantum state expressed in the standard basis.This provides an amplitude-based encoding of the neural network.
  • State representation: For binary activation patterns with xi = ±1, the normalization satisfies |x|^2 = d.The corresponding quantum state is normalized separately for use as a state vector.
  • Qubit scaling: N = ⌈log2 d⌉ qubits represent a d-level quantum system, so the qubit overhead scales logarithmically with the number of neurons.The weighting matrix is then addressed in the quantum setting through quantum Hebbian learning.
  • State preparation: Preparing the encoded state |x⟩ from classical activation data is a central classical-to-quantum read-in step.The paper identifies qRAM and efficient quantum state-preparation techniques as possible routes, with logarithmic overhead in d in suitable settings.
  • State preparation: Activation patterns may alternatively be supplied directly by a quantum device or as outputs of a quantum channel.For direct quantum-device preparation, the runtime is efficient when the gate count is polynomial in the number of qubits.

IV. QUANTUM HEBBIAN LEARNING

Quantum Hebbian learning represents the Hopfield weight matrix as a mixed quantum state and makes its information available to quantum algorithms. The procedure uses memory-pattern states, sparse Hamiltonian simulation, and phase estimation to access eigenvalues and eigenstates with favorable dimension scaling.

  • Quantum Hebbian learning: qHeb associates the Hopfield weighting matrix W with a mixed state ρ stored in a register of N qubits.The method uses training-pattern states as the memory information encoded in ρ.
  • State preparation: The training states |x(m)⟩ can be prepared with runtime T_in ∈ O(poly(log d)) in the settings considered.Efficient preparation is a prerequisite for using qHeb as an efficient quantum procedure.
  • Limitation: Full quantum state tomography can scale polynomially with d, although low-rank states admit techniques with runtime O(poly(d log d, r)).The paper therefore considers direct use of ρ for extracting eigeninformation instead of reconstructing the full state.
  • Quantum Hebbian learning: qHeb sequentially applies unitaries associated with memory-pattern projectors to simulate conditional evolution under ρ.The unitaries act through ancilla-controlled operations and swaps between subsystems.
  • Simulation: Sparse Hamiltonian simulation provides logarithmic-in-d scaling for each unitary Uk under the stated sparsity construction.The relevant block matrix is 1-sparse and self-adjoint, enabling efficient simulation methods.
  • Quantum readout: The resulting qHeb procedure simulates ρ conditionally to precision ϵ and supports phase estimation of its eigenvalues and eigenstates.The paper describes the overall qHeb runtime as depending on log d, t, M, and 1/ϵ.
  • Outcome: The method prepares the weight matrix from training data as a mixed quantum state and uses it for higher-level quantum cognitive operations.The paper specifically identifies learning the eigenvalues and eigenvectors of ρ as an application.

V. THE HOPFIELD NETWORK

The Hopfield network stores activation patterns through Hebbian learning and retrieves them either by iterative updates or by solving a relaxed constrained optimization problem. The matrix-inversion approach produces continuous-valued activations that can be projected to binary predictions.

  • The standard Hopfield procedure randomly updates neurons, producing non-increasing energy and eventual convergence to a local minimum.
  • Hebbian learning sets the weighting matrix from training activation patterns so stored patterns become local minima of the network energy.
  • The alternative classical method reconstructs incomplete, noise-free patterns by minimizing energy subject to fixed known-neuron values.
  • The reconstruction problem is converted into a linear system whose solution contains the activation vector and Lagrange multipliers.
  • The recovered activations are continuous confidence values and can be projected to the nearest ±1 state for neuron predictions.

VI. THE QUANTUM HOPFIELD NETWORK

qHop runs the matrix-inversion Hopfield method by encoding incomplete patterns and network information into quantum states. Quantum phase estimation, sparse Hamiltonian simulation, filtering, and amplification produce a state proportional to the pseudoinverse solution.

  • The incomplete activation pattern and threshold data are encoded in an input state, and the optimization solution is represented as A^-1|w⟩.
  • qHop implements the matrix-inversion approach by combining quantum phase estimation, sparse Hamiltonian simulation, filtering, and amplification.
  • The matrix A is simulated by decomposing it into block matrices and applying Suzuki–Trotter time evolution over short steps.
  • Eigenvalue thresholding with user-defined µ trades runtime against pseudoinverse error before the algorithm returns the filtered inverse-applied state.
  • Multiple incomplete patterns can be processed in superposition, but extracting each individual pattern still requires O(K) qHop operations.

VII. ALGORITHM EFFICIENCY

The claimed efficiency of qHop depends on efficient state preparation, Hamiltonian simulation, phase estimation, filtering, and output handling. Its logarithmic dimension dependence is constrained by memory count, input assumptions, and parameter choices.

  • qHop assumes input-state preparation can be performed in O(poly(log d)) time using qRAM or efficient state-preparation techniques.
  • Phase estimation combines sparse simulation for projector and identity blocks with quantum Hebbian simulation for the training-state block.
  • The phase-estimation runtime is dominated by state exponentiation, while filtering and amplification add a separate overhead.
  • Maintaining efficiency requires 1/µ ∈ O(poly(log d)), linking the eigenvalue threshold to the algorithm's overall runtime.
  • Because qHop scales linearly with the number of stored patterns M, logarithmic dimension dependence requires operating substantially below classical capacity.
  • The regularization parameter must satisfy γ ≥ ∥W∥ for a local minimum, but excessive γ adds runtime overhead.

VIII. OUTPUT

The reconstructed quantum state is intended for global information extraction or as an output to a larger quantum toolchain rather than direct amplitude-by-amplitude readout. Fidelity tests and observable measurements provide task-specific alternatives to tomography.

  • Tomography can extract amplitudes from the reconstructed state but introduces overhead polynomial in the data dimension.
  • A swap test compares the reconstructed state with a reference state such as a training pattern through global fidelity measurement.
  • Expectation values of binary observables can classify the reconstructed state according to task-specific membership categories.
  • qHop can serve as a quantum-toolchain component that reconstructs a state from an incomplete superposition and passes it to a subsequent operation.

IX. COMPARISON

qHop is compared with classical Hopfield procedures and alternative quantum approaches, with potential lower computational demands for suitably large systems. The authors qualify this comparison because it is not a comprehensive benchmark.

  • Classical approaches: The original Hopfield procedure has runtime polynomial in the number of neurons because it typically samples every neuron.
  • Comparison: qHop can potentially operate with lower computational demands than classical approaches for suitably large d.The comparison contrasts qHop with the original Hopfield procedure and sparse classical matrix inversion methods.
  • Quantum approaches: Alternative quantum Hopfield approaches use basis-state encoding with Grover search or adiabatic dynamics governed by a spectral gap.Adiabatic approaches can have similar runtimes to classical methods when the spectral gap is exponentially small.
  • Scope: The analysis does not constitute a comprehensive benchmark against possible classical and quantum approaches to running the Hopfield network.

X. APPLICATION

The paper applies Hopfield reconstruction to recognizing H1N1 influenza A RNA sequences from partial information. In a small numerical example, the classical and matrix-inversion approaches show comparable recovery performance, while qHop offers logarithmic runtime in system dimension.

  • RNA recognition: The application stores RNA-base encodings from eight H1N1 influenza A segments in a Hopfield weighting matrix.Each RNA segment is converted to a double-sized binary string before storage.
  • Experimental setting: The experiment stores the first 50 RNA-bases from each of 8 segments, giving d = 100 and M = 8.The weighting matrix is filled to classical capacity with M = 5 ≈ d/(2 log d) in the small example.
  • Evaluation: Both approaches reconstruct full activation patterns from randomly selected partial RNA information, with Hamming distance averaged over 1000 repetitions.The tested partial-information range is l/2 ∈ {1, 2, . . . , 50}.
  • Results: The conventional and matrix-inversion approaches have comparable performance, and each recovers the input segment for suitably large partial information.The quantum version can classify the sample using a swap test with a target state corresponding to H1N1.

XI. DISCUSSION

The discussion presents qHop as an amplitude-encoded quantum Hopfield network with potentially faster learning and operation, while identifying implementation requirements and qHeb as a new quantum-learning subroutine.

  • qHop: qHop encodes an exponential number of neurons in the amplitudes of a polynomially large register of qubits.
  • Efficiency: The learning and operation steps of qHop can be exponentially quicker than classical approaches.
  • Requirements: Efficient qHop operation requires state initialization, qHeb, matrix inversion, and Hamiltonian simulation to be implemented efficiently.The discussion identifies pure-state preparation or qRAM, sparse Hamiltonian simulation, and density matrix exponentiation as relevant techniques.
  • Capacity: Using qHeb introduces linear dependence on the number of training examples, which affects quantum Hopfield capacity.
  • qHeb: qHeb adapts Hebbian learning to the quantum setting by representing the weight matrix as a mixed quantum state or Hamiltonian.Memory patterns are sequentially imprinted as pure quantum states onto memory qubits.

Appendix A: Perturbed data

The appendix develops constrained and perturbed-data variants of Hopfield optimization and explains how regularization supports local-minimum guarantees and reconstruction quality. It also states conditioning requirements for effective quantum matrix inversion.

  • Perturbed data: For perturbed data, the optimization includes an l2-norm constraint through a regularization parameter β.
  • Perturbed data: The perturbed-data first-order condition produces a matrix inversion problem for finding x.The displayed criterion contains ((γ + β)Id − W)x + θ − βx(pert) = 0.
  • Constrained minimization: The constrained optimization reaches a local minimum when γ > ∥W∥, because γId − W is positive definite.The appendix uses Sylvester’s criterion and the Schur complement to establish the condition.
  • Regularization: For l = 50 known neurons, the average Hamming distance drops to zero for sufficiently high γ > ∥W∥ ≈ 0.185.Choosing an arbitrarily large γ adds polynomial runtime to qHop.
  • Quantum inversion: The quantum matrix-inversion method is effective when the eigenvalue threshold preserves polylogarithmic runtime and either avoids or controls pseudoinverse error.The relevant condition is 1/µ ∈ O(poly(log d)), with error controlled when |µmin| < µ.
Loading 1710.03599v3…