Unfortunately, I cannot find any information on this, so I am asking in this forum if anyone knows, and if so, why this is the case?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Initially, Aharanov et al. showed that adiabatic computation is polynomially equivalent to gate-based quantum computation. There could be a significant, but still only polynomial overhead in converting the gates to the initial and final Hamiltonians (and vice-versa). I myself only understand portions of the proof - it appears related to the earlier ground-breaking results on the QMA-hardness of $n$-local Hamiltonian simulation - but I think people mostly treat the result as a theoretical statement without ever putting the reductions down to actual practice. For example researchers might say something like "we give an efficient quantum algorithm to prepare the ground state of $|\psi_0\rangle$ of some local Hamiltonian $\mathcal H$, therefore by the results of Aharanov et al. there is a similarly efficient adiabatic algorithm".
As for the particular problem of factoring large numbers, I'm not aware if anyone has taken Shor's circuit and run it through all of the machinery of Aharnov et al.. Nonetheless, one approach by Peng et al. and entitled "A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation" was able to factor $N=21$ adiabatically, merely by finding an $(x,y)\in\mathbb{N}^2$ to minimize $f(x,y)=(N-xy)^2$. But, there's no clarity as to whether an adiabatic algorithm for that particular cost function would necessarily scale polynomially, and Peng et al. don't explore this in much detail.
In conclusion, by Aharanov et al. yes there must be an adiabatic algorithm to efficiently factor large numbers based on an adiabatic algorithm; I don't think it's ever actually been put down or described in detail. By Peng et al. there is a simple cost function for factoring that can be run adiabatically but there's only handwaving about the actual efficiency of their cost function, and I would expect Aharanov et al.'s reduction to lead to a much more complicated cost function.
answered Apr 15, 2023 at 14:58
$\begingroup$
$\endgroup$
4
As stated correctly in the answer by Mark, it has been known since around 2004 that "Adiabatic quantum computation is equivalent to standard quantum computation".
What the authors of that paper mean by "equivalent", is that adiabatic quantum computing has the power to simulate a circuit-based (that's what they mean by the word "standard") quantum computer with overhead that grows only polynomially with the problem size, and likewise a circuit-based quantum computer can simulate an adiabatic quantum computer with overhead that only grows polynomially with the problem size.
Therefore, Shor's algorithm can be performed on an adiabatic quantum computer. D-Wave in fact has a universal quantum computer, but I haven't seen them extend that universal quantum computer to have more than two qubits.
answered Apr 15, 2023 at 19:11
user1271772 No more free timeuser1271772 No more free time
14.2k2 gold badges26 silver badges75 bronze badges
-
1$\begingroup$ Out of curiosity are you aware of anyone using the method of that paper to convert Shor’s circuit (or, say, even the modular exponentiation part) to an initial and final Hamiltonian, for use in an adiabatic algorithm? $\endgroup$ Commented Apr 15, 2023 at 20:09
-
2$\begingroup$ @MarkS Not off the top of my head. Shor's algorithm is extremely difficult to implement on circuit-based quantum computers, so implementing it on a totally different type of quantum computer for which it wasn't originally meant, doesn't sound fun. Even the number 15 hasn't properly been factored on a circuit-based quantum computer in a scalable way yet (see this: cstheory.stackexchange.com/q/37113/35155 and this: quantumcomputing.stackexchange.com/q/27120/2293). I cannot imagine Shor's algorithm factoring any number that a classical computer can't factor faster, any time soon. $\endgroup$ Commented Apr 15, 2023 at 20:21
-
1$\begingroup$ Cool. Finding $(x,y)\in \mathbb N^2$ to minimize $(N-xy)^2$ adiabatically, as in Peng et al., is probably "easier" but I also doubt that that is scalable as well, because Peng et al. doesn't seem to capture anything unique about factoring. $\endgroup$ Commented Apr 15, 2023 at 20:59
-
1$\begingroup$ @MarkS The problem with trying to minimize (N - xy)^2 is that the "x" and "y" are represented in terms of binary variables b0,b1,b2,b3,...bn like follows: $x = b_0 2^0 + b_1 2^1 + b_2 2^2 +\cdots + b_n 2^n$. The coefficients grow exponentially in the size of $x$ and $y$, as you can see in the case of the $2^n$ coefficient for the binary variable $b_n$. This problem is removed in the method explained here but the disadvantage of the newer method is the need for quadratization and auxiliary qubits. $\endgroup$ Commented Apr 15, 2023 at 21:14
$\begingroup$
$\endgroup$
It might depend a little bit on what you consider an adiabatic computation. One interesting idea is to do it in a piece-wise manner, where you can directly equate each piece to a gate in the circuit model. That way, you get a very straightforward translation, although perhaps isn't exactly what someone imagines when adiabatic is discussed. If it's of interest, take a look at this paper.
answered Apr 19, 2023 at 14:35