Quantum Computing without Quantum Computers: Database Search and Data
Processing Using Classical Wave Superposition
- URL: http://arxiv.org/abs/2012.08401v1
- Date: Tue, 15 Dec 2020 16:21:53 GMT
- Title: Quantum Computing without Quantum Computers: Database Search and Data
Processing Using Classical Wave Superposition
- Authors: Michael Balynskiy, Howard Chiang, David Gutierrez, Alexander
Kozhevnikov, Yuri Filimonov, and Alexander Khitun
- Abstract summary: We present experimental data on magnetic database search using spin wave superposition.
We argue that in some cases the classical wave-based approach may provide the same speedup in database search as quantum computers.
- Score: 101.18253437732933
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum computing is an emerging field of science which will eventually lead
us to new and powerful logic devices with capabilities far beyond the limits of
current transistor-based technology. There are certain types of problems which
quantum computers can solve fundamentally faster than the tradition digital
computers. There are quantum algorithms which require both superposition and
entanglement (e.g. Shor algorithm). But neither the Grover algorithm nor the
very first quantum algorithm due to Deutsch and Jozsa need entanglement. Is it
possible to utilize classical wave superposition to speedup database search?
This interesting question was analyzed by S. Lloyd. It was concluded that
classical devices that rely on wave interference may provide the same speedup
over classical digital devices as quantum devices. There were several
experimental works using optical beam superposition for emulating Grover
algorithm. It was concluded that the use of classical wave superposition comes
with the cost of exponential increase of the resources. Since then, it is
widely believed that the use of classical wave superposition for quantum
algorithms is inevitably leading to an exponential resources overhead (number
of devices, power consumption, precision requirements). In this work, we
describe a classical Oracle machine which utilizes classical wave superposition
for database search and data processing. We present experimental data on
magnetic database search using spin wave superposition. The data show a
fundamental speedup over the digital computers without any exponential resource
overhead. We argue that in some cases the classical wave-based approach may
provide the same speedup in database search as quantum computers.
Related papers
- An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Machine Learning [14.955338558971787]
A provable exponential quantum speedup has been a central research goal since the seminal HHL quantum algorithm for solving linear systems.
We present the first such provable exponential separation between quantum and quantum-inspired classical algorithms.
arXiv Detail & Related papers (2024-11-04T13:49:26Z) - Limitations of Noisy Quantum Devices in Computational and Entangling
Power [5.178527492542246]
We show that noisy quantum devices with a circuit depth of more than $O(log n)$ provide no advantages in any quantum algorithms.
We also study the maximal entanglement that noisy quantum devices can produce under one- and two-dimensional qubit connections.
arXiv Detail & Related papers (2023-06-05T12:29:55Z) - 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) - 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 Computing for Location Determination [6.141741864834815]
We introduce an example for the expected gain of using quantum algorithms for location determination research.
The proposed quantum algorithm has a complexity that is exponentially better than its classical algorithm version, both in space and running time.
We discuss both software and hardware research challenges and opportunities that researchers can build on to explore this exciting new domain.
arXiv Detail & Related papers (2021-06-11T15:39:35Z) - Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems.
We propose an algorithm to implement imaginary time propagation on a quantum computer.
arXiv Detail & Related papers (2021-02-24T12:48:00Z) - Space Complexity of Streaming Algorithms on Universal Quantum Computers [13.941598115553957]
The space complexity of some data stream problems, such as PartialMOD and Equality, is investigated on universal quantum computers.
The quantum algorithms for these problems are believed to outperform their classical counterparts.
arXiv Detail & Related papers (2020-10-31T16:16:35Z) - 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) - Electronic structure with direct diagonalization on a D-Wave quantum
annealer [62.997667081978825]
This work implements the general Quantum Annealer Eigensolver (QAE) algorithm to solve the molecular electronic Hamiltonian eigenvalue-eigenvector problem on a D-Wave 2000Q quantum annealer.
We demonstrate the use of D-Wave hardware for obtaining ground and electronically excited states across a variety of small molecular systems.
arXiv Detail & Related papers (2020-09-02T22:46:47Z) - An Application of Quantum Annealing Computing to Seismic Inversion [55.41644538483948]
We apply a quantum algorithm to a D-Wave quantum annealer to solve a small scale seismic inversions problem.
The accuracy achieved by the quantum computer is at least as good as that of the classical computer.
arXiv Detail & Related papers (2020-05-06T14:18:44Z)
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.