Posted on December 30, 2022, By Brian N. Siegelwax
A: They’re all easy.
Just kidding. Not all quantum algorithms are easy. But, I‘ve been asked what I think are the hardest ones. Additional criteria are that the algorithms should be practical, scalable, and not textbook like Shor’s Factoring Algorithm and Grover’s Algorithm. Also, what would be the difference between running them on real hardware and on a simulator?
The List
For me, one algorithm stands above all others. Therefore, my list of the hardest algorithms includes just one: amplitude encoding. And while you may argue that amplitude encoding shouldn’t count here, after all it is input state preparation for other algorithms, it can stand alone in generative algorithms and I’m counting it. It is, without a doubt, the hardest problem I’ve solved to-date.
Is it practical?
Absolutely. Besides its aforementioned role in state preparation, which is important for many algorithms, it can be used to model human cognition. I’ve used it to compose music, but it also has applications in generating language and art. I can imagine its applicability to robotics, as well.
Is it scalable?
Maybe. This is part of the quest for quantum memory, aka QRAM, because how can we possibly encode 1,000,000 amplitudes onto just 20 qubits? That’s a classical pre-processing nightmare, and we’re only talking about 20 qubits. Fortunately, I have a cheat pending publication, but that’s beyond the scope of this article. In a nutshell, though, my cheat is to use less qubits because, again, encoding amplitudes onto large numbers of qubits is not currently feasible.
Is it textbook?
Not at all, and that’s why it took me so long to figure it out. I could only find mentions of it, but nothing explaining how to do it. Many even said it couldn’t be done, but I now think many of them were referring to it at scale. Others have definitely figured out other ways of doing it. But, again, I still know of no tutorial for precise control of individual amplitudes.
Real vs simulation?
Like with all quantum algorithms, amplitude encoding is noisy on real hardware. A simulator can make easy work out of it as long as your qubit count is low, but at 10 qubits using my laptop I have time to grab a snack and freshen my cup of coffee. It’s not practical to simulate much more than that. In contrast, real hardware makes easy work out of any-sized encoding, just so long as we can figure out how to do that.
Conclusion
Obviously we all learn differently. Each algorithm might be more intuitive to some over others. There are algorithms that I still need to deep dive, after which my answer might very well change. But, at this moment, I personally can’t put any other algorithm into the same class as amplitude encoding.
Comments