The speed of quantum and classical learning for performing the k-th root of NOT

Abstract

We consider quantum learning machines -- quantum computers that modify themselves in order to improve their performance in some way -- that are trained to perform certain classical task, i.e. to execute a function which takes classical bits as input and returns classical bits as output. This allows a fair comparison between learning efficiency of quantum and classical learning machine in terms of the number of iterations required for completion of learning. We find an explicit example of the task for which numerical simulations show that quantum learning is faster than its classical counterpart. The task is extraction of the k-th root of NOT (NOT = logical negation), with k=2^m and m \in N. The reason for this speed-up is that classical machine requires memory of size log k=m to accomplish the learning, while the memory of a single qubit is sufficient for the quantum machine for any k.

4 pages, 4 figures

References in corpus (4)

• Improved Bounds on Quantum Learning Algorithms
• Quantum pattern recognition with liquid-state nuclear magnetic resonance
• Quantum learning by measurement and feedback
• Quantum Machines

Cited by in corpus (11)

• Quantum speedup for active learning agents
• Demonstration of quantum advantage in machine learning
• A quantum speedup in machine learning: Finding a N-bit Boolean function for a classification
• Quantum-enhanced deliberation of learning agents using trapped ions
• Strategy for quantum algorithm design assisted by machine learning
• Experimental quantum pattern recognition in IBMQ and diamond NVs
• A Quantum Model for Autonomous Learning Automata
• Entanglement detection with classical deep neural networks
• Protocol for secure quantum machine learning at a distant place
• A model of interacting quantum neurons with a dynamic synapse
• Entanglement Detection with Quantum-inspired Kernels and SVMs