PaperlayerView exact revision on arXiv

Source-linked AI summary

Machine learning \& artificial intelligence in the quantum domain

Vedran Dunjko, Hans J. Briegel

arXiv:1709.02779v1quant-phcs.AIcs.CV

TL;DR

Quantum information and machine learning have largely developed independently despite shared questions about computation, learning, and intelligence. This review synthesizes their interaction, including quantum-enhanced learning, machine learning for quantum technologies, and quantum generalizations of learning concepts. It reports progress across data analysis, interactive learning, quantum-agent frameworks, and broader theories of quantum learning and intelligence.

  • Problem

    Quantum information and machine learning have distinct challenges, while the extent to which they can benefit from each other and support quantum generalizations of learning remains under investigation.

  • Method

    The paper develops a broad survey spanning quantum learning from data, quantum learning through interaction, quantum agent-environment paradigms, and conceptual generalizations of learning and intelligence.

  • Results

    The review reports quantum improvements in interactive learning under specified conditions, quantum-classical complexity separations in generalized reinforcement learning, and algorithmic speed-up potential for amplitude-encoded data.

  • Takeaways & Limitations

    Quantum effects may enhance learning agents and data-analysis methods, while quantum information provides a basis for broader theories of learning and intelligence.

Abstract

from arXiv · show

Quantum information technologies, and intelligent learning systems, are both emergent technologies that will likely have a transforming impact on our society. The respective underlying fields of research -- quantum information (QI) versus machine learning (ML) and artificial intelligence (AI) -- have their own specific challenges, which have hitherto been investigated largely independently. However, in a growing body of recent work, researchers have been probing the question to what extent these fields can learn and benefit from each other. QML explores the interaction between quantum computing and ML, investigating how results and techniques from one field can be used to solve the problems of the other. Recently, we have witnessed breakthroughs in both directions of influence. For instance, quantum computing is finding a vital application in providing speed-ups in ML, critical in our "big data" world. Conversely, ML already permeates cutting-edge technologies, and may become instrumental in advanced quantum technologies. Aside from quantum speed-up in data analysis, or classical ML optimization used in quantum experiments, quantum enhancements have also been demonstrated for interactive learning, highlighting the potential of quantum-enhanced learning agents. Finally, works exploring the use of AI for the very design of quantum experiments, and for performing parts of genuine research autonomously, have reported their first successes. Beyond the topics of mutual enhancement, researchers have also broached the fundamental issue of quantum generalizations of ML/AI concepts. This deals with questions of the very meaning of learning and intelligence in a world that is described by quantum mechanics. In this review, we describe the main ideas, recent developments, and progress in a broad spectrum of research investigating machine learning and artificial intelligence in the quantum domain.

I. INTRODUCTION

Quantum information processing extends computation and information science through quantum phenomena, models, and algorithms. This survey frames quantum methods alongside machine learning and artificial intelligence, emphasizing their potential interaction and mutual benefit.

  • Quantum information: Quantum information studies communication, processing, and use of information governed by phenomena absent from classical physics.Quantum information includes restrictions such as the impossibility of cloning unknown quantum information.
  • Quantum machine learning: The survey examines how quantum advantages may support machine learning and artificial intelligence tasks, while also noting that quantum machine learning has an ambiguous meaning.It can refer either to quantum algorithms for machine learning or to machine learning applied to quantum information processing.
  • Quantum computation: Quantum computers have demonstrated advantages for algebraic problems, linear algebra, optimization, simulation, sampling, and oracle-based computation.Examples include factoring, discrete logarithms, semidefinite programming, approximate optimization, and quantum simulation.
  • Quantum computation: Oracle query complexity counts how many times an algorithm calls a black-box resource specified only by its input-output relations.Grover’s search provides a canonical quantum example with a quadratic improvement for unordered search.
  • Computational models: Quantum computational models such as quantum Turing machines, quantum circuits, measurement-based computation, and adiabatic computation are conceptually distinct despite computational equivalence.Different models are better suited to different applications, including theoretical, algebraic, distributed, and optimization problems.

1. Learning from data: machine learning

Machine learning studies algorithms that learn from data, while reinforcement learning studies agents that learn through interaction. These settings fit within a broader agent-environment view of artificial intelligence, which concerns autonomous agents pursuing goals.

  • Learning from data: Machine learning constructs algorithms that learn from data and make predictions, commonly in supervised, unsupervised, and reinforcement-learning settings.Supervised learning uses labeled examples, whereas unsupervised learning addresses data-analysis tasks without such labels.
  • Learning from data: Supervised learning includes classification and regression, while unsupervised learning includes clustering, feature extraction, dimensionality reduction, and generative modeling.Dimensionality reduction addresses high-dimensional representations and attempts to preserve relevant data structure.
  • Learning from data: A one-second standard-resolution video clip can occupy approximately 10^8-dimensional space, illustrating the curse of dimensionality in raw data representations.The estimate follows from approximately 10^6 dimensions per frame multiplied by 30 frames.
  • Learning from interaction: Reinforcement learning trains agents to choose action sequences from percepts using rewards, with learning occurring through online interaction with an environment.The agent-environment formalism can also express supervised and unsupervised settings, although reinforcement learning typically uses a reward function.
  • Agent-environment paradigm: Artificial intelligence focuses on intelligent agents that perceive environments, act autonomously, learn from experience, and select activities to achieve goals.Agents are defined relative to environments, and specialized learning algorithms can be viewed as restricted agents in specialized environments.

b. Notation

This section introduces classical ML models and concepts used to position later quantum proposals. It focuses on neural networks, Hopfield and Boltzmann machines, and support vector machines.

  • Neural networks: Feed-forward neural networks are commonly used for supervised learning, while recurrent networks support feedback and include Hopfield networks and Boltzmann machines.Deep learning approaches generally fit the feed-forward paradigm.
  • Neural networks: Artificial neurons are real-valued functions parameterized by weights and an activation function, which can be combined into neural networks.Perceptrons are threshold-activation special cases of artificial neurons.
  • Neural networks: Neural-network training can face computational cost, training instabilities such as vanishing gradients, and large dataset requirements.Higher-complexity models may also overfit and offer weaker generalization guarantees.
  • Hopfield networks: Hopfield networks use recurrent binary neurons and energy minimization to form associative or content-addressable memories.A trained network converges toward a stored pattern closest to an input, commonly under Hamming distance.
  • Boltzmann machines: Boltzmann machines assign binary neuron states probabilistically according to energy differences, temperature, weights, and thresholds, and are typically generative models.In the infinite-running-time limit, configurations follow a Boltzmann distribution.

3. Other models

This section surveys additional ML models and computational tools relevant to quantum machine learning. It covers regression, decision trees, hypothesis minimization, boosting, feature representations, optimization, and linear algebra.

  • Regression: Regression methods approximate continuous labeling functions, often fitting parameters by minimizing least-squares error.Linear regression is a typical example of this function-approximation approach.
  • Decision trees: Decision trees classify or regress by routing data according to feature values, with tree depth and node degree reflecting the feature structure.They are expressive but difficult to train without constraints.
  • Hypothesis learning: Classification can be formulated as selecting a hypothesis from a family H that minimizes error or loss over the data.SVM hypotheses are hyperplanes in kernel space, whereas neural-network hypotheses are parameterized by network structure and weights.
  • Boosting: Boosting constructs a stronger composite classifier by training weak learners on differently distributed datasets and optimizing their combination weights.Changing sampling frequencies makes weak learners emphasize different parts of the input space.
  • Computational tools: ML also uses optimization algorithms and linear-algebra tools, including particle swarm, genetic, evolutionary, stochastic-gradient, matrix-decomposition, QR, and LU methods.These tools commonly arise in training learning models and solving related computational problems.

B. Mathematical theories of supervised and inductive learning

Learning theory formalizes supervised learning and studies its limits through sample, model, and computational complexity. PAC and VC frameworks relate training data, hypothesis classes, and performance beyond observed examples.

  • Learning theory provides formal tools for identifying the limits of learnability, complementing practical models such as neural networks and SVMs.
  • 1. Computational learning theory: Computational learning theory formalizes supervised learning by quantifying the oracle or sample complexity required to approximate unknown concepts.
  • No Free Lunch theorems show that learning models cannot be meaningfully compared without assumptions about environments or datasets.
  • 1. Computational learning theory: PAC learning uses sampled examples to produce a hypothesis whose error is within ϵ of the best concept in the class, except with probability δ.
  • 2. VC theory: VC theory bounds the deviation between empirical and total risk using model VC-dimension, sample count, and failure probability.

C. Basic methods and theory of reinforcement learning

Reinforcement learning studies how agents learn to behave optimally through interaction with unknown environments, commonly modeled as Markov decision processes. Its theory covers reward-based policies, Q-learning, exploration, and increasingly autonomous extensions.

  • Partially observable settings and episodic-compositional memory extend interactive learning toward more autonomous agents and general intelligence.
  • Reinforcement learning addresses optimal behavior in unknown environments by allowing agents to explore an MDP through actions, states, and rewards.
  • MDPs represent finite states and actions, probabilistic action-dependent transitions, and rewards assigned to transitions.
  • Policies assign action probabilities by state, while finite- and infinite-horizon expected rewards provide alternative figures of merit.
  • Q-learning updates action-value estimates from immediate rewards and subsequent maximum values, converging to optimal Q-values under suitable exploration and learning-rate conditions.
  • Optimal Q-values determine an optimal policy by selecting the highest-valued action, although the update rule alone does not specify the learning policy.
  • No Free Lunch results require restrictions on environment classes, such as finite, time-independent MDPs, for perfect learning guarantees.

III. QUANTUM MECHANICS, LEARNING, AND AI

The section surveys how quantum mechanics, learning, and AI intersect, emphasizing both quantum applications of ML and the use of ML to support quantum information processing. It highlights metrology, Hamiltonian estimation, and quantum-control design as settings where optimization and learning methods address complex experimental and computational tasks.

  • Quantum computation does not automatically produce qualitative progress in AI, motivating a more specific examination of how quantum information and learning interact.The section distinguishes general advances in quantum computation from advances that directly affect learning or AI.
  • The survey adopts an inclusive view of ML encompassing statistical learning, black-box optimization, and hard optimization problems, while emphasizing pioneering interdisciplinary QIP applications.Because broad-scope ML work cannot be covered completely, the review prioritizes pioneering studies and works explicitly presenting their methods as ML.
  • ML techniques help optimize complex quantum-metrology measurement strategies and control parameters under experimentally motivated constraints.These planning problems include identifying optimal strategies for estimating properties of quantum states, processes, and Hamiltonians.
  • 2. Phase estimation settings: Differential evolution was reported as superior and more computationally efficient than earlier particle-swarm approaches for non-convex phase-estimation planning.The phase-estimation strategy seeks improved measurement planning beyond a Heisenberg scaling of O(1/N).
  • 3. Generalized Hamiltonian estimation settings: Bayesian experimental design and sequential Monte Carlo support generalized Hamiltonian estimation with controls, probabilistic parameters, and stochastic noise.The generalized setting estimates hyperparameters governing conditional parameter distributions P(θ|ζ).
  • B. Design of target evolutions: ML optimization can design quantum target evolutions and gates both offline and through runtime interaction with tunable physical systems.Quantum-control optimization selects control fields to produce desired evolutions, but greedy methods can fail when reasonable constraints are imposed.

2. On-line design

On-line learning and reinforcement learning can control complex quantum systems and experiments, while also helping discover physical insights and design novel experiments. The surveyed examples span adaptive quantum-memory control, measurement-based computation, many-body state preparation, and automated experimental discovery.

  • On-line design: On-line quantum experiments use feedback, favoring reinforcement learning and planning when the experiment need not be fully specified beforehand.Experimental constraints also distinguish these settings from conventional optimization.
  • On-line design: ML and RL agents can control quantum devices, preserve quantum memory, combat noise, generate entanglement, and target desired evolutions.The same learning process can implicitly reveal information about the underlying physics.
  • Controlling complex processes: Recurrent neural networks generate pulse sequences for dynamical decoupling that minimize final noise and outperform well-known sequences.With finite pulse intervals, optimal sequences depend on the interval, noise Hamiltonian, and total evolution time.
  • Controlling complex processes: In measurement-based quantum computation, an RL agent learns adaptive measurements that compensate for unknown local fields acting on an entangled resource state.The agent selects a different measurement after each observed measurement outcome.
  • Learning how to experiment: Automated experimental design produced novel highly entangled states and enabled machine discovery of useful optical devices.Related work also reports respectable and sometimes near-optimal reinforcement-learning performance for target-state preparation.
  • Machine learning in condensed-matter and many-body physics: Unsupervised learning can identify many-body phases and discover order parameters without access to the system Hamiltonian.Neural-network quantum states also represent equilibrium and dynamical properties, with hidden-layer size controlling the representable Hilbert-space subset and supporting quantum-state tomography.

V. QUANTUM GENERALIZATIONS OF MACHINE LEARNING CONCEPTS

Quantum generalizations of machine learning replace or extend classical data and learning settings with quantum states and quantum processing constraints. The surveyed work connects quantum state discrimination, sample complexity, template matching, and general learning-context frameworks.

  • Quantum generalizations: machine learning of quantum data: Quantum information generalizes classical data to quantum states while imposing restrictions such as no-cloning and no-deleting, alongside new processing options.This motivates extending supervised-learning concepts to quantum datasets.
  • Quantum generalizations: machine learning of quantum data: Quantum supervised learning studies labeled datasets {(ρ_i, y_i)}, where quantum states ρ_i replace classical inputs x_i.The paper distinguishes quantum data from stochastic classical data despite similarities between their learning problems.
  • Quantum generalizations: machine learning of quantum data: For probabilistic labels, independently sampled examples are not equivalent to multiple copies of one sample, and full information about a distribution requires infinitely many samples in principle.The same distinction appears for quantum states and motivates links to state discrimination.
  • Quantum generalizations: machine learning of quantum data: State discrimination can be formulated as supervised learning: given a quantum state promised to belong to a classically specified set {ρ_i}, identify its label.Template matching extends this setting by assigning an input according to its largest Uhlmann fidelity with template states.
  • Other known optimality results for (restricted) template matching: Template matching compares fully quantum, classical optimal, and estimate-and-discriminate strategies, with another measurement matching the optimal quantum strategy exactly.The intuitive estimate-and-discriminate strategy is not optimal for learning in the cited finite-template setting.
  • Quantum generalizations: machine learning of quantum data: Quantum-learning frameworks classify scenarios by data type, computational resources, and learning goal, including classical ML and quantum-capable learning.Related results establish sample-complexity lower bounds by reducing classification problems to quantum state-discrimination settings.

f. Quantum inductive learning

Quantum inductive learning generalizes learning beyond classical data and concepts to quantum states, operations, measurements, and interactive environments. The surveyed models define knowledge operationally through prediction, implementation, or policy performance, and reveal both classical-quantum complexity parallels and separations.

  • Learning quantum states: Quantum-state learning treats a state as a concept and knowledge as predicting outcome probabilities for arbitrary measurements.Predicting two-outcome measurements can suffice for full tomographic reconstruction.
  • Learning quantum processes: Quantum learning also includes storing and later retrieving unknown unitary operations, with knowledge defined as the ability to implement the unitary later.The task uses a storing phase followed by retrieval on a new input state.
  • Learning measurements: Measurement learning estimates an unknown measurement using probe states and complexity measures related to VC dimension.The examples are pairs (ρ, Tr(ρE)), with the measurement fixed.
  • Quantum-generalized reinforcement learning: Quantum POMDPs represent environment beliefs as quantum states and actions as quantum instruments, with rewards given by expected values of positive operators.The model extends classical partially observable decision processes to quantum belief dynamics.
  • Quantum-generalized reinforcement learning: For finite horizons, policy-existence complexity is the same classically and quantumly, whereas goal reachability is decidable classically but undecidable quantumly.The goal-reachability separation is maximal, although its immediate learning consequences remain uncertain.

A. Learning efficiency improvements: sample complexity

Quantum learning can improve sample or query efficiency in restricted settings, especially with coherent quantum examples or structural assumptions. These advantages disappear in standard distribution-free PAC and agnostic models, while weaker learning notions and computational hardness assumptions restore separations.

  • Quantum PAC learning: Quantum PAC learning with coherent example oracles efficiently learns some concept classes that are not known to be efficiently classically PAC learnable.The first quantum generalization uses coherent superpositions of labeled examples.
  • Quantum PAC learning: For uniform distributions, quantum algorithms learn DNF formulas and k-juntas with quantum resources derived from coherent examples.The k-junta result uses O(k log(k)/ϵ) uniform quantum examples and O(2^k) uniform queries or related resources as specified in the passage.
  • Distribution-free PAC: Distribution-free quantum PAC learning offers no sample-complexity advantage over classical PAC learning, and agnostic learning likewise shows no classical-quantum separation.The same sample count suffices for a classical PAC learner for any ϵ and δ.
  • Quantum predictive PAC learning: Standard PAC learning therefore has the same learnable concept classes classically and quantumly, but weaker predictive models can produce exponential separations.The Predictive Quantum model requires only one or polynomially few hypothesis evaluations.
  • Learning from membership queries: Quantum membership-query improvements are at most low-degree polynomial in general unless structural promises are imposed on the oracle.For concept class C, the passage gives D(C) = O(nQ(C)^3).
  • Learning from membership queries: Under computational hardness assumptions, some concept classes are efficiently quantum learnable but not efficiently classically learnable unless Blum integers can be classically factored.Factoring Blum integers is described as not known to be classically solvable but solvable on a quantum computer.

2. Capacity via quantized Hopfield networks

Quantized Hopfield networks use quantum annealing to replace classical local recall with global optimization over an energy landscape. The surveyed work reports exponential storage capacity under random-memory assumptions, while noting comparisons with classical proposals remain unresolved.

  • Classical Hopfield foundations: Classical Hopfield content-addressable memories store binary patterns in a weight matrix and retrieve them through neuron updates toward energy minima.The network uses sign-valued patterns and asynchronous perceptron-style updates under typical analyses.
  • Classical Hopfield foundations: Standard Hopfield capacity is typically sub-linear in n, with the Hebbian rule scaling as O(n/2ln(n)) and Storkey’s rule improving this capacity.The passage states that broad classical capacities are typically sub-linear in n.
  • Quantum recall: Quantum recall adds an input-dependent Hamiltonian that lowers the energy near the input pattern, making the nearest stored pattern a likely global minimum.This reframes retrieval as an optimization problem suitable for quantum annealing.
  • Quantum recall: Adiabatic evolution from a simple initial Hamiltonian to the problem Hamiltonian obtains the ground state when the evolution is sufficiently slow.The trajectory is H(t) = Λ(t)H_init + H_p, with Λ(0) large and Λ(1) = 0.
  • Quantum capacity results: Under random-memory assumptions, quantum-annealed Hebbian Hopfield networks were reported to have exponential storage capacity.The same work investigated compatibility with D-Wave Chimera architectures and found potential for demonstrable near-term improvements.
  • Quantum capacity results: The reported quantum capacity contrasts with standard classical capacities, but the relationship to exponential capacities proposed for fully classical systems remains unresolved.The review explicitly notes that the advantages of the quantum proposals remain to be elucidated.

1. Speed-up via adiabatic optimization

Quantum annealing approaches quantum-enhanced ML by mapping difficult training objectives, especially binary-classifier optimization, onto QUBO or Ising ground-state problems. The review highlights non-convex loss functions, anomaly detection, and broader annealing-based learning applications, while noting hardware and computational limitations.

  • Speed-up via adiabatic optimization: Quantum ML optimization commonly maps training problems onto QUBO or Ising ground-state finding, enabling annealing-based approaches to binary-classifier learning.QUBO and Ising formulations provide the optimization targets for available annealing architectures.
  • Speed-up via adiabatic optimization: Practical annealing systems have restricted connectivity and limited interaction precision and accuracy, while general Ising ground-state finding is functional NP-hard.Annealers may nevertheless provide heuristic or approximate solutions, but these constraints limit direct speed-up claims.
  • Speed-up via adiabatic optimization: Boosting and hyperplane classification can share quantum optimization techniques because both optimize weighted classifier components under loss and regularization terms.The classifier objective is expressed as argmin_w L(w; D) + R(w).
  • Speed-up via adiabatic optimization: Non-convex loss functions can be physically realizable on quantum architectures and may improve boosting on noisy data compared with convex-loss approaches.The reviewed q-loss construction is motivated by both non-convexity and implementability in a quantum system.
  • Beyond boosting: Quantum optimization was also explored for anomaly detection, including computationally challenging software verification and validation problems.The proposed learning step uses quantum optimization to learn software characteristics.
  • Beyond boosting: Annealing architectures extend beyond boosting to Bayesian network structure learning and deep neural-network training through QUBO reduction or sampling.These applications broaden annealing-based quantum ML beyond binary-classifier optimization.

c. Beyond boosting

Beyond boosting, the review surveys quantum algorithms for amplitude amplification, amplitude encoding, and linear-algebra-based ML. These methods report speed-up potential for training, clustering, regression, PCA, and related tasks, but their benefits depend on data-access assumptions, conditioning, sparsity, and extracting useful classical outputs.

  • Beyond boosting: Quantum amplitude amplification can quadratically reduce training-point complexity, with exponential improvements in neuron count in some regimes.The same technique also yields quadratic speed-up and error-probability reduction for perceptron training.
  • Beyond boosting: Quantum linear-system algorithms can scale logarithmically with system size, but the apparent exponential advantage requires efficient state preparation, favorable condition numbers, and useful measurable outputs.The output is a quantum state, so reconstructing a complete classical vector can eliminate the improvement.
  • Beyond boosting: Quantum linear regression produces a state proportional to the solution vector and can estimate fit quality efficiently, while its exponential-improvement potential requires polylogarithmic condition number and sparsity.The stated regression complexity is O(κ4d3 log(N)/ϵ).
  • Beyond boosting: The reviewed speed-up claims are conditional because state preparation, qRAM access, sparsity, conditioning, and classical readout can dominate the overall computation.The survey therefore describes exponential improvements as potential rather than unconditional computational speed-ups.
  • Beyond boosting: Amplitude-encoded quantum routines support k-means clustering with complexity O(M log(MN)/ϵ), assuming oracle access to normalized state vectors.The distance-to-centroid computation is the main cost in the stated clustering approach.
  • Beyond boosting: Amplitude encoding and related quantum linear-algebra methods extend to PCA and support processing of high-dimensional data through quantum states representing eigenvectors or model parameters.PCA-like recovery samples large eigenvalues and corresponding amplitude-encoded eigenvectors.

VII. QUANTUM LEARNING AGENTS, AND ELEMENTS OF QUANTUM AI

The review extends quantum information processing beyond data analysis and optimization to general learning and AI settings. It considers quantum-mechanical agents, environments, and interactions as a quantum generalization of broad agent-environment learning frameworks.

  • VII. QUANTUM LEARNING AGENTS, AND ELEMENTS OF QUANTUM AI: The review positions reinforcement learning as a mathematically clean model for learning by interaction within this broader quantum-agent perspective.The passage flags a qualification concerning reinforcement learning without elaborating it here.
  • VII. QUANTUM LEARNING AGENTS, AND ELEMENTS OF QUANTUM AI: Quantum learning-agent research treats the agent, environment, and their interaction quantum-mechanically as a generalization of broad AI learning frameworks.This section moves beyond traditional ML techniques for understanding data or optimizing models.

A. Quantum learning via interaction

Projective Simulation (PS) provides a learning-agent framework in which episodic memory supports reinforcement learning, while its stochastic-walk deliberation offers natural routes to quantization. Quantum random walks can yield quadratic speed-ups in deliberation, although behavioral learning efficiency may remain unchanged.

  • Projective Simulation: Projective Simulation represents episodic experience as a structured network of clips and deliberates through stochastic walks over that memory.Clips may encode percepts, actions, or structures built from clips; h-values determine transition probabilities between clips.
  • Learning dynamics: The basic PS agent learns by increasing h-values on transitions involved in rewarded behavior, while dissipation prevents divergence and accelerates relearning after rule changes.The dissipation parameter γ limits maximal efficiency but improves adaptation when the game rules change.
  • Quantum enhancement: The framework is attractive for quantization because its homogeneous internal dynamics are based on random walks over the PS network.Quantum-walk constructions target the deliberation process while preserving the agent’s interaction behavior.
  • Quantum enhancement: Quadratic speed-ups arise from the difference between classical inverse spectral-gap scaling and quantum eigenphase-gap scaling in the rPS deliberation process.The quantum method obtains the coherent stationary-distribution encoding more rapidly than classical mixing in the relevant constructions.
  • Quantum enhancement: Quantum rPS and classical rPS are behaviorally equivalent, so faster internal deliberation does not by itself improve learning efficiency measured by interaction steps.The review distinguishes computational speed-ups in internal processing from efficiency defined through agent-environment interactions.

B. Quantum agent-environment paradigm for reinforcement learning

A quantum agent-environment paradigm formalizes agents, environments, memories, communication, and interaction while retaining a meaningful history for evaluating learning. Within this framework, some environments permit quantum-enhanced learning, whereas other quantum implementations reproduce the classical specification without improvement.

  • Quantum agent-environment paradigm: The quantum agent-environment paradigm models agents and environments as sequential unitary maps with private memories and a shared communication register.The agent acts on its memory and the communication register, while the environment acts on its own memory and that register.
  • Scope: The framework is presented as a basis for characterizing the scope and limits of learning agents in quantum environments and for classifying quantum learning settings.Its classification complements the usual supervised-learning perspective.
  • Scope: The paradigm includes standard quantum machine-learning settings as special cases, including environments represented by quantum database or memory-access maps.The simpler standard quantum machine-learning setting has an environmental map without internal memory.
  • Quantum agent-environment paradigm: Because quantum interaction histories are not generally readable without disturbance, the framework uses a more detailed measurement description to evaluate learning reliably.Classical histories can be read from a diagonal communication register, but quantum histories may be entangled with other systems.
  • Quantum enhancement: For every classical environment specification, a consistent quantum implementation can be constructed that prohibits quantum improvements.This result establishes a boundary on claims of generic quantum advantage for learning agents.
  • Quantum enhancement: Under suitable assumptions, deterministic episodic environments can be quantum-accessible, allowing an agent to search in superposition before classically tested interaction.The proposed construction uses an oracularized environment, a rewarding sequence, agent simulation, and subsequent classical execution.

b. Provable quantum improvements in RL

Quantum reinforcement learning provides provable enhancements for interactive learning under restricted assumptions about agent–environment access and luck-favoring performance. The review situates these results within broader frameworks for quantum-enhanced agents and quantum artificial intelligence, while emphasizing unresolved scope and practical limitations.

  • Provable quantum improvements in RL: Quantum agents can use Grover search to find winning sequences quadratically faster, then use the first winning instance to pre-train a luck-favoring agent.Under these conditions, the resulting quantum-enhanced agent provably outperforms the basic classical agent.
  • Provable quantum improvements in RL: These are the first examples of quantum improvements in learning figures of merit for reinforcement-learning contexts.The result establishes a provable learning advantage rather than only an advantage in exploration.
  • Provable quantum improvements in RL: The construction requires quantum access to suitably quantized environments and restricts agent–environment pairs to those where past performance predicts improved future performance.The latter condition is called luck-favoring performance in the review.
  • Limitations and outlook: The practical minimum requirements and the broader scope of possible improvements remain unresolved because the assumed quantum control is restrictive.The review presents these results as early examples whose assumptions limit immediate practical applicability.
  • Agent–environment framework: The agent–environment paradigm encompasses reinforcement learning, robotics, and broader AI settings, while conventional supervised learning can also be embedded within it.The review distinguishes whether classical learning tasks require quantum or classical access, including cases involving quantum databases.
Loading 1709.02779v1…