Hot answers tagged

4

As far as I know, there are four possibilities for having a quantum advantage in Bayesian machine learning: Gaussian processes: there is a known quantum speed-up for Gaussian processes that you can easily test on IBM Q [1,2]. The idea is to use HHL (quantum algorithm for matrix inversion) in order to compute the inverse of the kernel matrix, which is used ...


3

No. Without entanglement we can always write the system as the product state of individual qbits, and those qbits are just a pair of complex numbers. We can thus simulate the quantum system on a classical computer in polynomial time & space, and would not gain any benefit from execution on a quantum computer. There are methods of analysis by which a ...


2

The speed up is not expressed by the exponentially many basis states that a quantum system can be in. The speedup comes from being able to recombine the probability amplitudes associated to the these basis states so that a measurement can output the correct result of the computation with sufficiently high probability. If the exponentially many basis ...


2

$N$ qubits have $2^N$ basis states, and $2^N$ probabilities (to be in each of basis states). The question "does the number of probabilities express the exponential speed-up ?" does not make sense to me.


2

The Context The algorithm Ewin Tang originally examined and dequantized was the quantum recommendation system algorithm by Kerenidis & Prakash. Many QML algorithms, including the quantum recommendation system algorithm, exploit the quantum linear systems algorithm (QLSA), which was posted on arXiv in 2008 by Harrow, Hassidim, and Lloyd (that's why it'...


1

You can find details about the algorithm optimality and complexity in the original paper by Harrow, Hassidim and Lloyd: Quantum algorithm for solving linear systems of equations, mainly in parts III and appendix 5. An article Quantum Circuit Design for Solving Linear Systems of Equations may be interesting for you as well. It contains a "practical" example ...


1

Sometimes, mainly in popular articles and books, it is stated that $n$ qubits can be in all $2^n$ possible zero-one combinations simultaneously (the superposition of these combinations) and any calculation on this register is done with all these combinations. This is used as an explanation for speed-up brings by a quantum computer. However, this is ...


1

The Kerenidis-Prakash algorithm was groundbreaking, until Ewin Tang fixed the ground back up: Quanta Magazine: Major Quantum Computing Advance Made Obsolete by Teenager.


1

I found the answer in these notes: For an ​NP​-complete problem like CircuitSAT, we can be pretty confident that the Grover speedup is real, because no one has found any classical algorithm that’s even slightly better than brute force. On the other hand, for more “structured” ​NP​-complete problems, we ​do​ know exponential-time algorithms that are ...


Only top voted, non community-wiki answers of a minimum length are eligible