3 ms·

True. It's too early to say whether or not quantum computers will practically outperform classical computers on machine learning tasks or any task at all. Like

True. It's too early to say whether or not quantum computers will practically outperform classical computers on machine learning tasks or any task at all. Like Shor's factoring and Grover's algorithm, machine learning problems like solving systems of linear equations have been mathematically proven to have a quantum speedup. The problem is engineering quantum computers well enough that they can outperform classical computers on these tasks. We are currently working on that and it will take a couple of decades at least. Hope is not lost. There are also a couple of theories that hybrid classical/quantum computers of the next decade or so will perform some tasks like quantum chemistry and approximate optimization (which can be used in machine learning) better than classical computers. Only time will tell.

moefh 9y ago
> solving systems of linear equations have been mathematically proven to have a quantum speedup I'm not an expert, so please correct me if I'm wrong, but my understanding from Aaronson's paper is that this is not really true in general. Unlike Shor's algorithm, which can be used to actually find the factors of some integer, HHL (the quantum algorithm that "solves" systems of linear equations) is best compared to quantum Fourier transform. That is: it can only be used to prepare a state |x> that contains the solution you want. But that's still a quantum state -- if you naively try to measure it, you'll get garbage. That doesn't mean HHL or quantum Fourier transform are useless (indeed, quantum Fourier transform is used by Shor's algorithm), it just means that they're not drop-in replacements for their classical counterparts (like Shor's algorithm is for classical factoring).
- vtomole 9y ago
  That's right. HHL doesn't find x for Ax = b. It finds the result of a scalar measurement on x. Like you said, a garbage result is generated if the state is measured naively. It's rare for quantum algorithms to be drop-in replacements for classical problems. Take Grover's algorithm. Using it to search a classical database kills the speedup due to the number of calls to memory. Therefore, it will probably be used to attack NP-complete problems instead.

moefh 9y ago

> solving systems of linear equations have been mathematically proven to have a quantum speedup I'm not an expert, so please correct me if I'm wrong, but my understanding from Aaronson's paper is that this is not really true in general. Unlike Shor's algorithm, which can be used to actually find the factors of some integer, HHL (the quantum algorithm that "solves" systems of linear equations) is best compared to quantum Fourier transform. That is: it can only be used to prepare a state |x> that contains the solution you want. But that's still a quantum state -- if you naively try to measure it, you'll get garbage. That doesn't mean HHL or quantum Fourier transform are useless (indeed, quantum Fourier transform is used by Shor's algorithm), it just means that they're not drop-in replacements for their classical counterparts (like Shor's algorithm is for classical factoring).

vtomole 9y ago
That's right. HHL doesn't find x for Ax = b. It finds the result of a scalar measurement on x. Like you said, a garbage result is generated if the state is measured naively. It's rare for quantum algorithms to be drop-in replacements for classical problems. Take Grover's algorithm. Using it to search a classical database kills the speedup due to the number of calls to memory. Therefore, it will probably be used to attack NP-complete problems instead.