The geometry of quantum learning

DOI10.1007/S11128-009-0129-6MaRDI QIDQ989901zbMATH OpenOpenAlexFDO

Authors Markus Hunziker, David A. Meyer, Ji-Hun Park, James Pommersheim, Mitchell J. Rothstein

Publication date 23 August 2010

Published in Quantum Information Processing (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/quant-ph/0309059

zbMATH Keywords

quantum algorithmsProcrustes problem

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: Concept learning provides a natural framework in which to place the problems solved by the quantum algorithms of Bernstein-Vazirani and Grover. By combining the tools used in these algorithms--quantum fast transforms and amplitude amplification--with a novel (in this context) tool--a solution method for geometrical optimization problems--we derive a general technique for quantum concept learning. We name this technique "Amplified Impatient Learning" and apply it to construct quantum algorithms solving two new problems: BATTLESHIP and MAJORITY, more efficiently than is possible classically.

Recommendations

• Quantum learning algorithms for quantum measurements
• How Many Query Superpositions Are Needed to Learn?
• Improved bounds on quantum learning algorithms
• Quantum algorithms for learning symmetric juntas via the adversary bound
• Optimal quantum sample complexity of learning algorithms

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1179314 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• A theory of the learnable
• Improved bounds on quantum learning algorithms
• Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
• Matrix Analysis
• On quantum detection and the square-root measurement
• On the mathematical foundations of learning
• Optimal multiple quantum statistical hypothesis testing
• Poly-locality in quantum computing
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Complexity Theory
• Quantum algorithms revisited
• Quantum complexity theory
• Quantum detection and estimation theory
• Reversing quantum dynamics with near-optimal quantum and classical fidelity
• STACS 2004
• Statistical decision theory for quantum systems
• Strengths and Weaknesses of Quantum Computing

Cited in

(7)

• Optimal quantum sample complexity of learning algorithms
• Quantum search for the dating market
• Quantum learning algorithms for quantum measurements
• Two-sided bounds on minimum-error quantum measurement, on the reversibility of quantum dynamics, and on maximum overlap using directional iterates
• On the uselessness of quantum queries
• Improved algorithms for quantum identification of Boolean oracles
• Improved bounds on quantum learning algorithms

This page was built for publication: The geometry of quantum learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989901)