PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Algorithms for Deep Convolutional Neural Networks

Iordanis Kerenidis, Jonas Landman, Anupam Prakash

arXiv:1911.01117v1quant-phcs.ET

TL;DR

The paper addresses the difficulty of implementing complete deep CNNs quantumly, especially their nonlinearities and pooling operations. It develops a modular shallow QCNN with quantum convolution, tomography, sampling, and backpropagation, and reports potential speedups alongside MNIST accuracy similar to a classical CNN. The authors also identify open questions about scaling and the effects of quantum behaviors.

  • Problem

    Quantum deep learning lacks an easy way to implement neural-network nonlinearities with quantum unitaries, limiting complete quantum CNN construction.

  • Method

    The paper designs a modular shallow QCNN that supports classical CNN operations, uses ℓ∞ tomography with probabilistic sampling, and includes quantum backpropagation.

  • Results

    The QCNN offers potential speedups over classical CNNs and achieves similar MNIST classification accuracy in numerical simulations.

  • Takeaways & Limitations

    The approach provides a quantum framework for evaluating and training CNNs while supporting larger kernels, deeper architectures, and high-dimensional inputs within the paper's stated scope.

  • Takeaways & Limitations

    The simulations use a small CNN, and the effects of QCNN behaviors without classical equivalents remain open questions.

Abstract

from arXiv · show

Quantum computing is a new computational paradigm that promises applications in several fields, including machine learning. In the last decade, deep learning, and in particular Convolutional neural networks (CNN), have become essential for applications in signal processing and image recognition. Quantum deep learning, however remains a challenging problem, as it is difficult to implement non linearities with quantum unitaries. In this paper we propose a quantum algorithm for applying and training deep convolutional neural networks with a potential speedup. The quantum CNN (QCNN) is a shallow circuit, reproducing completely the classical CNN, by allowing non linearities and pooling operations. The QCNN is particularly interesting for deep networks and could allow new frontiers in image recognition, by using more or larger convolution kernels, larger or deeper inputs. We introduce a new quantum tomography algorithm with $\ell_{\infty}$ norm guarantees, and new applications of probabilistic sampling in the context of information processing. We also present numerical simulations for the classification of the MNIST dataset to provide practical evidence for the efficiency of the QCNN.

1 Introduction

The paper frames QCNNs as a response to the computational demands of increasingly large deep-learning workloads, while addressing the difficulty of implementing neural-network nonlinearities with quantum unitaries. It proposes a complete quantum CNN and numerical simulations to assess its running time and accuracy.

  • Increasing dataset sizes and algorithmic complexity are expected to demand extreme computational power, motivating quantum computing as a candidate solution.
  • Quantum deep learning remains challenging because neural-network nonlinearities are difficult to implement with quantum unitaries.
  • CNNs are deep-learning architectures used for visual recognition, signal processing, and time series.
  • The paper proposes a quantum algorithm for a complete CNN with potential speedups over classical CNNs.
  • Numerical simulations evaluate the QCNN's running time and accuracy.

2 Main results

The paper develops a modular QCNN that reproduces classical CNN operations, including convolution, nonlinearities, pooling, and training. It combines quantum convolution, ℓ∞ tomography, probabilistic sampling, and backpropagation, with reported speedups and MNIST accuracy comparable to a classical CNN.

  • The QCNN supports any number of layers, arbitrary kernel counts and sizes, and a broad range of nonlinearities and pooling methods.Its modular architecture is designed to implement a complete CNN in quantum form.
  • Each quantum layer applies convolution, nonlinearity, and pooling, then uses ℓ∞ tomography and high-value sampling to recover a classical tensor efficiently.The quantum output approximates the classical layer output with error ϵ > 0.
  • Forward-pass speedup is exponential in the number of kernels and almost quadratic in the input's spatial dimension.The QCNN has the same inputs and outputs as the classical CNN, enabling direct comparison.
  • The QCNN's running time benefits from poly-logarithmic dependence on the number of kernels and sampling of important output values.The input-size contribution is incorporated through the sampling precision parameter η.
  • The algorithm includes quantum backpropagation that estimates kernel gradients within additive error δ and updates them through gradient descent.The procedure uses stored forward-pass quantities, kernels, inputs, outputs, and a loss function.
  • The quantum backpropagation procedure introduces a quantum tomography algorithm with ℓ∞ norm guarantees.The authors identify this tomography method as potentially independently useful.
  • Numerical MNIST simulations show classification accuracy similar to that of a classical CNN.The simulations assess the practical behavior of the proposed quantum CNN.

3 Classical Convolutional neural network (CNN)

A CNN processes tensor-valued images through repeated convolution, activation, pooling, and fully connected procedures. Its convolution can be represented as matrix multiplication after reshaping input regions and kernels.

  • 3.1 Tensor representation: CNNs represent images as 3-tensors whose dimensions encode height, width, and color channels.A colored image stacks one matrix per RGB channel.
  • 3.2 Architecture: A CNN repeatedly applies convolution, activation, pooling, and eventually fully connected layers to classify inputs.Activation introduces nonlinearities, pooling downsamples layers, and final nodes correspond to possible labels.
  • 3.3 Convolution Product as a Tensor Operation: A single kernel scans overlapping input regions, producing output entries from inner products and forming a feature map.Each high output indicates a strong response to the feature represented by the kernel at that position.
  • 3.3 Convolution Product as a Tensor Operation: Applying Dℓ+1 kernels to a 3-tensor input produces Dℓ+1 two-dimensional outputs, represented together as a 3-tensor.The kernel collection is represented as a 4-tensor Kℓ.
  • 3.3 Convolution Product as a Tensor Operation: Without padding or stride, convolution changes spatial dimensions according to Hℓ+1 = Hℓ−H + 1 and Wℓ+1 = Wℓ−W + 1.The paper notes that padding and stride can be incorporated but does not detail their use.
  • 3.4 Matrix Expression: Convolution is equivalent to matrix multiplication after reshaping input subregions into Aℓ and kernels into Fℓ.Rows of Aℓ represent vectorized input regions, while columns of Fℓ represent vectorized kernels.

4 Quantum Preliminaries

The paper introduces quantum-state representations, QRAM-based data access, quantum linear-algebra primitives, and amplitude-based subroutines. It also presents ℓ∞ tomography for recovering each state component with controlled error and logarithmic dimension dependence.

  • Quantum states: A vector in R^d is encoded as a quantum superposition on ⌈log(d)⌉ qubits, with amplitudes normalized by the vector norm.Quantum states are manipulated by unitary matrices and measured through amplitude-dependent probabilities.
  • Quantum subroutines: Amplitude estimation estimates a probability using P iterations and succeeds with probability at least 8/π^2.The estimate is exact when p = 0, and when p = 1 with even P.
  • Quantum subroutines: Median evaluation boosts the probability of obtaining a good inner-product estimate by combining multiple amplitude-estimation outputs and taking their median.The circuit is reversed afterward to remove garbage states.
  • QRAM and quantum linear algebra: QRAM supports storing matrix rows and applying associated quantum operations in O(log^2 n) time.The data structure also supports single-entry insertion, update, and deletion in O(log^2(n)) time.
  • QRAM and quantum linear algebra: Quantum linear-algebra runtimes depend on matrix condition and data-dependent parameters, including κ(M) and µ(M).The algorithms assume matrices are stored in suitable QRAM structures and can use a condition threshold.
  • ℓ∞ vector-state tomography: The proposed ℓ∞ tomography reconstructs every component within additive error δ using O(log d/δ^2) calls to the state-preparation unitary.Unlike ℓ2 tomography, its dependence on dimension is logarithmic rather than linear.

5 Forward pass for the QCNN

The QCNN forward pass converts convolution, nonlinear activation, and pooling into quantum procedures, then uses amplitude-based sampling and ℓ∞ tomography to recover useful classical outputs. Its quantum convolution achieves polylogarithmic dependence on input and kernel sizes up to precision- and norm-dependent factors.

  • Forward-pass structure: The forward pass implements convolution, nonlinear activation, quantum sampling, tomography, QRAM updating, and pooling across successive layers.The procedure assumes input and kernel data are stored in QRAM and produces outputs for the next layer.
  • Quantum convolution: A quantum convolution maps a 3D input tensor and 4D kernel tensor to a state approximating the activated convolution output within precision Δ.The convolution is reduced to inner-product estimation between input regions and kernel vectors.
  • Quantum convolution: The quantum convolution procedure has time complexity eO(M/ϵ), hiding factors poly-logarithmic in Δ and the sizes of the input and kernel.M is the maximum norm of a product between a kernel and an input region.
  • Sampling and tomography: Amplitude-based sampling prioritizes high-value convolution outputs, treating them as more informative while assigning low-value or unsampled outputs to zero.The paper interprets the output amplitudes as carrying information proportional to pixel importance.
  • Sampling and tomography: The algorithm estimates convolution values, applies nonlinear functions through arithmetic or Boolean circuits, and retrieves positions and values using conditional rotation, amplification, and ℓ∞ tomography.With high probability, values above η are recovered while smaller values are set to zero.
  • Sampling and tomography: Sampling a fraction σ of output pixels is equivalent to ℓ∞ tomography, with the required threshold η depending on output size and content.The approach aims to retain meaningful information while reducing the classical computation needed between layers.

5.2 QRAM update

The QRAM update stores sampled QCNN outputs in tree structures and integrates pooling online as samples arrive. Pooling-specific overwrite rules support maximum, average, and other pooling operations with a bounded runtime overhead.

  • Output storage: The QRAM stores the next-layer matrix through indexed queries, using a tree structure whose update depth is logarithmic in the number of leaves.Writing sampled convolution outputs therefore adds only a polylogarithmic multiplicative factor in the number of sampled points.
  • Output storage: After sampling a layer output, the algorithm maps each sampled tensor position to corresponding QRAM matrix positions and updates tree leaves and parent nodes.Unsampled leaves remain zero, representing low-valued or pooling-excluded points.
  • Quantum pooling: Pooling is performed during QRAM updates because the complete layer output is unavailable until tomography finishes.This enables online pooling as sampled points from the convolution output arrive.
  • Quantum pooling: For maximum pooling, a sampled value replaces the stored value only when larger; average pooling instead updates the stored value to the new average.The overwrite rule depends on the selected pooling operation.
  • Quantum pooling: Any pooling method can be integrated into the QRAM update, with worst-case overhead eO(P/η^2) for repeated leaf overwrites.P is the pooling size and is described as a small constant in most cases.

5.3 Running Time

The QCNN’s quantum convolution layer has a running-time advantage under stated sampling and kernel-size conditions, while integrating activation and pooling with little additional cost.

  • 5.3 Running Time: The quantum convolution layer’s running time is summarized separately from the classical layer, with polylogarithmic factors hidden by ˜O notation.The analysis tracks parameters including approximation error, kernel norms, sampling precision, and amplitude amplification.
  • 5.3 Running Time: A single quantum convolution layer can include ReLU and pooling without significant additional running time, unlike the classical CNN’s separate full-data operations.The comparison concerns the operations performed within one layer circuit.
  • 5.3 Running Time: The approximation error ϵ is empirical, and simulations suggest it can be relatively high without compromising learning.The paper also notes that injected noise may sometimes support more robust learning.
  • 5.3 Running Time: When kernel dimensions are a sufficient constant fraction of the input dimensions, the classical cost is quadratic in input size while the quantum cost is almost linear.This comparison uses Hℓ+1 = Hℓ−H +1 and the stated kernel-size condition.

5.4 Variable Summary

This section summarizes the variables used to describe a CNN layer and clarifies how quantum and classical layer inputs and outputs are represented.

  • 5.4 Variable Summary: The variable summary covers tensors, their approximations, and reshaped versions used in the layer analysis.The variables represent common layer quantities for the quantum and classical algorithms.
  • 5.4 Variable Summary: Table 1 lists the ℓth layer’s input variables, meanings, dimensions, and notations shared by the quantum and classical algorithms.Indices omitted for Yℓ are not used in the paper’s work.
  • 5.4 Variable Summary: Table 2 summarizes variables describing the quantum algorithm’s layer output, while Table 3 summarizes the classical algorithm’s layer output.The two tables organize output variables separately by algorithm.
  • 5.4 Variable Summary: The quantum and classical algorithms can be compared using the paper’s two corresponding diagrams.The section also flags notation ambiguities for clarification.
  • 5.4 Variable Summary: For the next layer, the quantum output is formally written as ˜Xℓ+1 and then reused under the reset notation Xℓ+1.The paper also replaces output indices with n for simplicity and stores the next-layer input as Aℓ+1 indexed by (p′, r′).

6 Quantum Backprogation Algorithm

The quantum backpropagation algorithm computes layer and kernel gradients, accounts for nonlinearities, tomography, and pooling, and updates kernels by gradient descent with stated precision guarantees.

  • 6 Quantum Backpropagation Algorithm: Backpropagation starts from the final-layer loss, modifies gradients for pooling, tomography, and nonlinearity, performs quantum matrix multiplications, estimates gradients by ℓ∞ tomography, and updates kernels.The listed steps propagate gradients through the layers and store the kernel-gradient estimates in QRAM before gradient descent.
  • 6 Quantum Backpropagation Algorithm: Theorem 6.1 provides a quantum backpropagation algorithm that estimates each kernel gradient to precision δ and updates kernel elements by gradient descent.The algorithm assumes input and kernel matrices for each layer are stored in QRAM and operates with a specified loss function.
  • 6 Quantum Backpropagation Algorithm: The required gradients are ∂L/∂Fℓ for kernel updates and ∂L/∂Yℓ for propagating the loss gradient to the preceding layer.The kernel gradient measures the loss derivative with respect to each kernel element.
  • 6 Quantum Backpropagation Algorithm: For convolution alone, the quantum gradient relations remain equivalent to the classical ones, with kernel gradients obtained through matrix operations involving Aℓ and the next-layer gradient.The derivation uses vectorization and the chain rule to relate layer and kernel derivatives.
  • 6 Quantum Backpropagation Algorithm: ReLU sets gradients to zero at negative inputs, while pooling sets gradients to zero for output positions not selected during pooling.Average pooling is described as relying on a similar idea to max pooling.
  • 6 Quantum Backpropagation Algorithm: Quantum backpropagation must modify stored gradients because the forward pass’s nonlinearities, tomography, and pooling were applied in superposition.The paper describes setting selected gradient values to zero before computing the preceding layer’s derivatives.
  • 6 Quantum Backpropagation Algorithm: The paper leaves open whether forward-pass subsampling can also reduce backpropagation cost by sampling only the largest derivatives without harming optimization.This is stated as an open question rather than an established speedup.
  • 6 Quantum Backpropagation Algorithm: The gradient update can be simulated with Gaussian relative noise, and numerical simulations tend to show acceptable noise does not disturb convergence.The noise has mean zero and standard deviation δ in the described simulation.

7 Numerical Simulations

The simulations implement QCNN effects in a small MNIST convolutional network and compare its noisy, sampled training and classification behavior with a classical CNN. The QCNN converges and classifies despite these modifications, although the experiments are computationally intensive and limited in scale.

  • Experimental setup: The experiment adds amplitude-estimation noise, capped ReLU, quantum sampling, and backpropagation noise to a PyTorch CNN trained on MNIST.MNIST contains 60,000 training and 10,000 testing images of handwritten digits.
  • Experimental setup: The simulated network uses two convolution layers with 5 and 10 kernels of size 7x7, followed by three fully connected layers and softmax over 10 classes.Pooling was not introduced in this simulation.
  • Limitations: The simulated CNN is small because each training curve required 4 to 8 hours on a classical computer, limiting experiments with deeper architectures.The authors suggest larger networks and more complex datasets as follow-up experiments.
  • Training: The QCNN can converge during training with sampling ratios up to 0.5, while meaningful information is preferentially sampled from convolution outputs.Training curves are compared with the classical CNN under varied sampling, amplitude-estimation, cap, and backpropagation parameters.
  • Classification: The QCNN can classify correctly on training and testing data despite noise and sampling, indicating no observed overfitting in these simulations.The conclusion is supported by the reported training and testing behavior rather than by a single quantitative table value.
  • Training: Small sampling ratios can produce a late training start, but convergence can begin after the kernels find a useful combination.The authors associate the delay with random initialization producing an uninformative convolution.

8 Conclusions

The paper presents a complete, shallow QCNN with quantum convolution, tomography, sampling, nonlinearities, pooling, and backpropagation. Its simulations show MNIST classification comparable to a classical CNN, while the speedup depends on tensor dimensions and is limited by classical-information recovery.

  • Contributions: The algorithm combines a quantum tensor convolution, importance-focused tomography, and quantum backpropagation for evaluating and training CNNs.The tomography samples meaningful information with higher probability to reduce algorithmic complexity.
  • Conclusions: The QCNN supports almost all classical CNN architectures, including bounded nonlinearities, pooling, arbitrary layer counts, and variable kernel sizes.The circuit is described as shallow and reusable across layers.
  • Speedup: The running time can speed up over classical CNNs through fast linear algebra and sampling of important output values.The potential benefit is especially associated with many input channels or kernels and larger architectures.
  • Limitations: State tomography and register encoding remain mandatory after nonlinearities and between layers, preventing exponential speedup in the number of input parameters.The paper therefore qualifies the speedup rather than claiming it applies uniformly to all input dimensions.
  • Empirical result: The QCNN’s MNIST simulations achieve classification accuracy similar to the classical CNN despite noise and sampling.The evidence comes from a small CNN simulation rather than a large-scale benchmark.

9 Appendix : Algorithm and Proof for ℓ∞norm tomography

The appendix presents an ℓ∞-norm tomography algorithm that reconstructs a classical vector approximation from a quantum state by sampling magnitudes and estimating signs. Its proof separates large and small coordinates and uses Chernoff bounds with union bounds.

  • Algorithm: The tomography algorithm reconstructs a classical vector e_X approximating a quantum state with an ℓ∞-norm guarantee.The stated procedure uses O(log d/δ^2) calls to the state-preparing unitary.
  • Algorithm: The algorithm measures N = 36 ln d / δ^2 copies to estimate coordinate probabilities, stores √p_i in QRAM, and then estimates coordinate signs.The sign estimate uses a Hadamard-based measurement and a threshold involving 0.4N p_i.
  • Proof: Chernoff bounds control sampling deviations, while union bounds extend coordinate-wise guarantees across all d coordinates.The appendix applies these bounds separately to large and small coordinates before combining them.
  • Proof: For coordinates with |x_i| > δ, the proof bounds both sign-estimation and magnitude errors using Chernoff concentration.The resulting coordinate error is bounded by δ with high probability for these coordinates.
  • Proof: For coordinates with |x_i| ≤ δ, the proof shows their estimated contributions remain small with very high probability.This handles the coordinates excluded from the large-coordinate set.

10 Quantum-Inspired Classical Algorithm

The paper compares its quantum approach with a quantum-inspired classical algorithm using ℓ2-BST data structures. The classical analogue preserves some logarithmic kernel dependence but loses the quantum method’s sampling-based speedup and has worse parameter dependence.

  • Classical analogue: Classical ℓ2-BST data structures can approximate inner products and emulate parts of quantum inner-product estimation.The comparison concerns classical analogues of quantum data-access and estimation procedures.
  • Complexity comparison: The quantum-inspired forward pass retains polylogarithmic dependence on kernel size but has quadratically worse dependence on precision, norm, nonlinearity cap, and average output magnitude.These differences arise when replacing the quantum procedures with classical analogues.
  • Prior evidence: Prior numerical experiments reported that quantum-inspired algorithms were less performant than both quantum and standard classical algorithms for the same tasks.This comparison is cited as related empirical evidence, not as a result of the present simulation.
  • Sampling limitation: The quantum-inspired algorithm cannot reproduce the speedup associated with sampling only a fraction σ of the convolution output.The paper states that its importance sampling has no classical analogue.
  • Sampling limitation: The importance-sampling procedure lacks asymptotic speedup but may still provide constant-factor savings in practice.This is a practical rather than asymptotic benefit.
Loading 1911.01117v1…