I’ve come to realize that making the best use of quantum computing in the future requires knowledge of quantum algorithms, so I’ve been focusing the last couple of weeks on better understanding those. It’s interesting that there already exist many such quantum algorithms that take advantage of quantum mechanics. To me, it seems like quantum programming will require knowledge and experience of when to use which algorithm, like machine learning programmers need to know when it is more useful to apply different algorithms, depending on what data is available or the intended goal. I’ve been wanting to read this book by Ike, an MIT professor, so waiting for the term to end so that the library copies become available. At least I’ll make an effort to skim it…
I’ve also been reading through the IBM Jupyter notebooks on how to use their qiskit, specifically the one for optimization. In there, they talk about how you could use quantum computing to solve the traveling salesman problem, a classic one in optimization research. It’s interesting that the brute force method for N > ~20 is unsolvable on traditional computing, but if I understand the IBM notebook correctly, it could be brute-forced with (N - 1)^2 qubits — so for example, if N = 20, that would be 361 qubits. Assuming the challenges with error correction as the number of qubits increases can be overcome, that seems like it might be a year or two in the future.
Until I read the Wikipedia article on the traveling salesman problem, I also didn’t realize that people have come up with alternate algorithms that can tackle up to 85,900 cities — amazingly better than the brute force method. While using traditional computing to implement these algorithms seems CPU intensive (i.e. using a supercomputer), it also boggles my mind that to solve this on a quantum computer, you might need 84,999^2 (7.2 trillion) qubits?!?!?! Given the state of technology, that seems decades away or impossible …. it makes me wonder if there are also alternate, quantum versions of these non-brute force methods that would make the required number of qubits more realistic. Kind of like there is a quantum Fourier transform to mirror the traditional discrete Fourier transform. More reading required!