7 ms·
> 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 un
by 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 agoThat'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.