The geometry of quantum learning

DOI10.1007/S11128-009-0129-6zbMATH Open1194.81045arXivquant-ph/0309059OpenAlexW2122964527MaRDI QIDQ989901FDOQ989901

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)

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.

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

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

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)

Cites Work

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

Cited In (6)

• Quantum search for the dating market
• Two-sided bounds on minimum-error quantum measurement, on the reversibility of quantum dynamics, and on maximum overlap using directional iterates
• Title not available (Why is that?)
• 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)