12

This is a soft question, but I find it to be a very pertinent one...

Algorithms for Grover's search and Simon's problems seem to come completely out of the blue, and I find it very hard to understand what their thought process was when it came to devising such algorithms; how they came up with a framework and the step-by-step thinking.

Is there a "quantum algorithmist's" toolkit? How does one go about creating an algorithm for a problem on which there is little literature?

Alan Whitteaker
  • 147
  • 7
  • 1
    This is a good question. My understanding is that as you suggest, this is very hard to find intrinsically "new" algorithms. However what people do is to combine quantum algorithms with a proven speedup in order to find new applications. For instance, we know that quantum computer can efficiently find the period of some function. Then what one can see is if there is a classical problem hard for classical computers which can be rephrased as a problem of period finding. So in a sense the quantum algorithm wouldn't be "fully new", but we would see that period finding has a "new" application. – Marco Fellous-Asiani Jul 05 '23 at 21:21
  • Basically I think that what people finding quantum algorithm often do is to try to put together known quantum routine in order to find new applications for them. And once it is done it would become a "new quantum algorithm". Much more rarely, an "intrinsically new" quantum algorithm would be found (i.e. an algorithm which cannot be expressed as a combination of already known quantum algorithms). All that being said I am not an expert on quantum algo so it is better to see if you get a better answer on this. – Marco Fellous-Asiani Jul 05 '23 at 21:23

1 Answers1

8

Many people having given a lot of thought about these kinds of questions - I really like Aharanov's discussion in a Qiskit article here.

Recalling some history, we may have:

  • Feynman took a guess that his quantum computer might help simulate (Bosonic) quantum systems, as he properly intuited that quantum mechanics is not amenable to classical simulations;
  • Deutsch initially, and later Deutsch and Jozsa, were motivated to explore quantum Turing machines and their implications for the Church-Turing thesis and especially what we now call the extended Church-Turing thesis;
  • Bernstein and Vazirani intended to formalize that intuition, and along the way found good oracle separations between BPP and BQP;
  • Simon really thought that quantum circuits were no big deal, but ended up finding his algorithm;
  • Shor picked up Simon's paper and suspected that Simon's exploitation of periodicity was important for the discrete log problem initially and factoring later;
  • Grover discovered his algorithm after learning of quantum computing from Shor, and had some thoughts about diffusion with quantum operators;
  • Aharanov, Jones, and Landau knew of the relationship, noted by Witten, between the Jones polynomial and topological quantum field theory; and
  • Lloyd recounts his work with Harrow and Hassidim, and the "well d'uh" observation (his sentiment) that quantum mechanics is linear, and inverting a matrix is linear, so a fast quantum algorithm for matrix inversion could work.

There seems to be different motivations for each of these. Perhaps it's hard to construct a "toolkit" from the above - but, as hinted by @Marco Fellous-Asiani in the comments, many of these algorithms are now subroutines for other algorithms!

For example even considering its many particular limitations, the linear systems (HHL) algorithm makes a good capstone in a course on quantum algorithms, as it includes (1) state preparation such as at least one of (a) adiabatic preparation, (b) amplitude amplification, or (c) the Grover-Rudolph protocol to prepare the initial state $|b\rangle$, execution of (2) the Quantum Phase Estimation (QPE) algorithm which includes (d) Hamiltonian simulation to simulate $A$ controlled with a clock register along with (e) the inverse Quantum Fourier Transform (iQFT) of the clock register to determine the phases, (3) the classical-to-quantum algorithm rotation of an ancilla qubit, (4) post-selection on the ancilla, and (5) phase kick-back with uncomputation of the QPE including (f) a (forward) QFT of the clock register and (g) Hamiltonian simulation controlled off the clock register. Further the HHL algorithm is often followed by (6) a SWAP test on two states so-prepared, so as to calculate the inner product thereof.

I also think the old adage of "1% inspiration, 99% perspiration" has to apply to quantum algorithm discovery. Shor took about a year about six months to formalize his initial discrete-log algorithm after coming across Simon's preprint.

Remember quantum algorithms are generally pretty good at characterizing global properties of functions - for example, periodicity as exploited in Shor's algorithm. So, might be able to have a quantum algorithm to tease out that property very efficiently. Knowing a little (or a lot) about linear algebra certainly helps.

Mark Spinelli
  • 11,947
  • 2
  • 19
  • 65
  • 2
    Actually, I came up with my algorithm only around six months after seeing Simon's preprint, although I started thinking about quantum computation when I saw Vazirani give a talk on his paper with Bernstein around a year before that. – Peter Shor Aug 05 '23 at 23:33
  • 1
    Thank you @PeterShor! Can I ask separately- where you thinking about factoring/dl right away, after Vazirani’s talk? Or were you inspired to think of discrete log/factoring only after coming across Simon’s paper? There were some “jokey” Usenet postings around then, and Deutsch and Jozsa do mention factoring in their paper (but in the context of trying to clarify what’s meant by an oracle, and not with a sentiment that quantum computers could be applicable to factoring). – Mark Spinelli Aug 06 '23 at 00:13
  • 2
    I certainly considered looking for a factoring algorithm after seeing Vazirani's talk, but I wasn't actually able to make any progress until after seeing Simon's preprint. – Peter Shor Aug 06 '23 at 01:54