Revisiting dequantization and quantum advantage in learning tasks
- URL: http://arxiv.org/abs/2112.00811v1
- Date: Wed, 1 Dec 2021 20:05:56 GMT
- Title: Revisiting dequantization and quantum advantage in learning tasks
- Authors: Jordan Cotler, Hsin-Yuan Huang, Jarrod R. McClean
- Abstract summary: We show that classical algorithms with sample and query (SQ) access can accomplish some learning tasks exponentially faster than quantum algorithms with quantum state inputs.
Our findings suggest that the absence of exponential quantum advantage in some learning tasks may be due to SQ access being too powerful relative to quantum state inputs.
- Score: 3.265773263570237
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: It has been shown that the apparent advantage of some quantum machine
learning algorithms may be efficiently replicated using classical algorithms
with suitable data access -- a process known as dequantization. Existing works
on dequantization compare quantum algorithms which take copies of an n-qubit
quantum state $|x\rangle = \sum_{i} x_i |i\rangle$ as input to classical
algorithms which have sample and query (SQ) access to the vector $x$. In this
note, we prove that classical algorithms with SQ access can accomplish some
learning tasks exponentially faster than quantum algorithms with quantum state
inputs. Because classical algorithms are a subset of quantum algorithms, this
demonstrates that SQ access can sometimes be significantly more powerful than
quantum state inputs. Our findings suggest that the absence of exponential
quantum advantage in some learning tasks may be due to SQ access being too
powerful relative to quantum state inputs. If we compare quantum algorithms
with quantum state inputs to classical algorithms with access to measurement
data on quantum states, the landscape of quantum advantage can be dramatically
different.
Related papers
- Towards Entropic Constraints on Quantum Speedups [0.0]
Some quantum algorithms have "quantum speedups": improved time complexity as compared with the best-known classical algorithms for solving the same tasks.
Can we understand what fuels these speedups from an entropic perspective?
Information theory gives us a multitude of metrics we might choose from to measure how fundamentally 'quantum' is the behavior of a quantum computer running an algorithm.
arXiv Detail & Related papers (2024-11-05T19:00:04Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum
Circuits [82.50620782471485]
QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits.
It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness.
Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
arXiv Detail & Related papers (2024-01-10T22:33:00Z) - Quantum Machine Learning: from physics to software engineering [58.720142291102135]
We show how classical machine learning approach can help improve the facilities of quantum computers.
We discuss how quantum algorithms and quantum computers may be useful for solving classical machine learning tasks.
arXiv Detail & Related papers (2023-01-04T23:37:45Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - Iterative Qubits Management for Quantum Index Searching in a Hybrid
System [56.39703478198019]
IQuCS aims at index searching and counting in a quantum-classical hybrid system.
We implement IQuCS with Qiskit and conduct intensive experiments.
Results demonstrate that it reduces qubits consumption by up to 66.2%.
arXiv Detail & Related papers (2022-09-22T21:54:28Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Quantum search on noisy intermediate-scale quantum devices [7.147209811770232]
Grover's algorithm is designed without considering the physical resources, such as depth, in the real implementations.
We present detailed benchmarks of the five-qubit quantum search algorithm on different quantum processors, including IBMQ, IonQ, and Honeywell quantum devices.
Our results show that designing the error-aware quantum search algorithms is possible, which can maximally harness the power of NISQ computers.
arXiv Detail & Related papers (2022-01-31T22:25:58Z) - A rigorous and robust quantum speed-up in supervised machine learning [6.402634424631123]
In this paper, we establish a rigorous quantum speed-up for supervised classification using a general-purpose quantum learning algorithm.
Our quantum classifier is a conventional support vector machine that uses a fault-tolerant quantum computer to estimate a kernel function.
arXiv Detail & Related papers (2020-10-05T17:22:22Z) - A Roadmap for Automating the Selection of Quantum Computers for Quantum
Algorithms [0.39146761527401425]
Some quantum algorithms already exist that show a theoretical speedup compared to the best known classical algorithms.
The input data determines, e.g., the required number of qubits and gates of a quantum algorithm.
An algorithm implementation also depends on the used Software Development Kit which restricts the set of usable quantum computers.
arXiv Detail & Related papers (2020-03-30T12:44:10Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.