I was wondering whether Simon's algorithm could be run on a D-wave machine. The Simon's algorithm is a promise problem. On the other hand the D-wave machine can run only quadratic unconstrained binary optimization problems. So, we need to convert the Simon's algorithm into an optimization problem. Is that possible?

Simon's algorithm is special because of its query complexity. Hypothetically, each query may correspond to a clock cycle. In that case, the difference between the number of cycles on a classical and a quantum computer will be different. On a D-wave computer we don't run a program over clock cycles. But it is true that the evolution of the Hamiltonian is traced over iterations and it could be correspondences to hypothetical clock cycles. Is there any way we could redefine the query complexity in the context of D-wave computer?

D-wave's famous Chimera architecture is a bipartite graph. Can we create an instance of Simon's algorithm on the bipartite graph?


Short answer: No.

There are really two separate issues to unpack here:

  1. Even if it worked exactly as advertised (which, as you might have heard, is somewhat disputed at present... :-) ), D-Wave's machine, by the company's own account, is only for adiabatic optimization. There's no particular reason to think that it could implement (e.g.) Shor's factoring algorithm, or other algorithms in the usual quantum circuit model.

  2. Even if you had a standard, universal quantum computer---so, not any of D-Wave's current or planned devices, but a "gate model" QC capable of running Shor's factoring algorithm and so forth---even then, Simon's algorithm in particular requires that the QC make quantum queries to a hypothetical black box. So in order to run Simon's algorithm, you need some explicitly-computable function that "instantiates" the black box. Right now, however, no one has a very clear idea whether there exist such explicitly-computable functions that satisfy the Simon promise, for which a classical algorithm couldn't also use the explicit descriptions to solve Simon's problem efficiently. Note that Shor's and Simon's algorithms are very similar at some level. The main advantage of Shor's over Simon's is that, with the former, we do know an explicitly-computable function---namely, the modular exponentiation function---that "instantiates" the abstract periodic black box (and that, moreover, has some practical importance...).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.