<p>Short answer: No.</p>

<p>There are really two separate issues to unpack here:</p>

<ol>
<li><p>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 <i>adiabatic optimization.</i>  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.</p></li>
<li><p>Even if you had a <i>standard, universal quantum computer</i>---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, <i>Simon's algorithm</i> 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 <i>also</i> 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 <i>do</i> know an explicitly-computable function---namely, the modular exponentiation function---that "instantiates" the abstract periodic black box (and that, moreover, has some practical importance...).</p></li>
</ol>

CC BY-SA 3.0
2014-02-06T19:50:10.300Z
2014-02-06T19:50:10.300Z
Scott Aaronson
<p>I was wondering whether <a href="https://en.wikipedia.org/wiki/Simon%27s_problem" rel="nofollow">Simon's algorithm</a> could be run on a <a href="https://en.wikipedia.org/wiki/D-Wave_Systems" rel="nofollow">D-wave</a> 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?</p>

<p>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?</p>

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

<cc.complexity-theory><quantum-computing><quantum-information>
Running Simon's algorithm on D-wave machine
Omar Shehab
# Running Simon's algorithm on D-wave machine

(Asked by: username_0 on 2014-02-05)

I was wondering whether [Simon's algorithm](https://en.wikipedia.org/wiki/Simon%27s_problem) could be run on a [D-wave](https://en.wikipedia.org/wiki/D-Wave_Systems) 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?

**Tags:** cc.complexity-theory, quantum-computing, quantum-information

---

## 1 answers

### Answer by username_1 on 2014-02-06. Score: 7 | Accepted answer

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...).


---

