6
$\begingroup$

I'm wondering whether even if we cannot create a fast quantum computer, simulating quantum algorithms can be a reasonable method for classical algorithms.

In particular, I'd like to see any results of classical algorithms that have been sped up by using a quantum simulation as a subroutine. Second, the next logical step would be to 'cut out the middleman' and see if we can remove the simulator. Perhaps this can even be done semi-automatically!

So, is there any result or research on this? Suggestions are welcome.

To be clear, I'm asking whether there exists any problem such that running a simulation of a quantum computer, on a classical computer, can offer any improvement (time or memory) over (trying to) solve the same problem on a classical computer without running any sort of simulation of a quantum computer.

Second, I am wondering how one then would attempt to adapt this algorithm such that all 'useless' parts of the quantum algorithm and the simulation are removed, hopefully improving the method even further.

|improve this question
$\endgroup$
  • $\begingroup$ So are you asking if a quantum computer can do a better job at simulating a quantum computer, than a classical computer? $\endgroup$ – Niel de Beaudrap Mar 26 '18 at 21:56
  • 2
    $\begingroup$ Perhaps you would like to revise the title, and the second paragraph, to avoid the sort of misunderstanding I have suggested. ("... in classical simulation": simulation of what? "... see if we can remove the simulator": and replace it with what, exactly?) $\endgroup$ – Niel de Beaudrap Mar 26 '18 at 22:28
  • 1
    $\begingroup$ This reminds me of "quantum-inspired evolutionary algorithms", which are heuristics that use representations at least reminiscent to multi-qubit states, but I'm not sure if the actual computations done would constitute a simulation of a quantum computer or if "quantum" is just used like a buzzword. I'm actually supposed to carefully read a paper dealing with such methods this week, so perhaps that will put me in a position to write an answer. $\endgroup$ – Kiro Mar 27 '18 at 5:54
  • 1
    $\begingroup$ @Kiro If you can take the time to share the papers or look into it and answer, I would be most satisfied $\endgroup$ – Discrete lizard Mar 27 '18 at 7:06
  • 2
    $\begingroup$ This looks pretty clear to me - you're asking if there exists any problem such that running a simulation of a quantum computer, on a classical computer, can offer any improvement (time or memory) over (trying to) solve the same problem on a classical computer without running any sort of simulation of a quantum computer, right? It does raise an interesting question about, if it does exist, would it then be considered a classical algorithm? Or would it be classified as 'classical with quantum influences'? Nevertheless, the question looks clear to me $\endgroup$ – Mithrandir24601♦ Mar 27 '18 at 21:30
3
$\begingroup$

I will attempt to address the following question only.

I'm asking whether the method of 'running' quantum algorithms on a 'quantum computer' 'simulated' on a classical computer would be able to outperform normal classical algorithms (preferably for problems that not obviously involve quantum simulation)

The closest thing to this that I am aware of are heuristic methods that employ natural computing, in particular the ones that take inspiration from quantum physics for the development of novel problem-solving techniques. These are known as quantum inspired algorithms. Please notice that: i) I do not claim that such methods could be rigorously shown to be superior to conventional algorithms, but it seems that they can be at least competitive; ii) the algorithms may or may not actually simulate a quantum computer, the faithfulness to the original source of inspiration varies.

I will briefly outline the framework of a particular type of a quantum-inspired evolutionary algorithm (QIEA). A more complete treatment may be found in chapter 24 of the book "Natural computing algorithms" by Anthony Brabazon et al [1]. Concrete examples can be found for example in arXiv.

The basic ingredients of a conventional evolutionary algorithm (EA) are a population of individuals $P(t)$, an update rule for the population, and a fitness function $f$. Here, each individual in $P(t)$ represents a possible solution to some problem, and $f$ quantifies how good the solution is. After initialization, for each step $t$ one evaluates $f$ on every individual in $P(t)$, records best ones and updates $P(t)$. This is iterated until a stopping criterion is reached, and the best found individual(s) are returned. In the simplest case, the update rule could be just random variation of individuals, but it can also be more complicated and engineered to introduce selection pressure towards better values of $f$.

In a QIEA, solutions are represented by bit strings of a fixed length, say, $m$. A quantum population $Q(t)$ is used, where each quantum individual consists of $m$ qubits. At each $t$, classical population $P(t)$ is determined from $Q(t)$ by "measuring" the qubits. $P(t)$ is ranked by $f$ and best results are recorded. $Q(t)$ is updated by acting on each qubit with a local gate, and iteration is continued. Often for $Q(0)$, all qubits are set to balanced superposition $(1/\sqrt{2},1/\sqrt{2})^T$, making each particular solution equally likely in the beginning.

As the quantum individuals remain essentially in a product state of $m$ qubits, there is no entanglement involved at any point, making QIEA not very quantum. On the other hand, we can effectively simulate the evolution of $Q(t)$ and make as many measurements as we want without needing extra qubits. The claimed advantage is over conventional EAs, based on supposedly needing fewer individuals or being better at maintaining diversity as the population evolves, as even a fixed $Q(t)$ can lead to many $P(t)$. All in all, QIEA by its design is meant to be run only as a simulation.

As a final remark, suppose that we wish to make QIEA more quantum without making it intractable. Can we? Perhaps. Consider the update rule of QIEA as a quantum circuit. It is rather boring, with a qubit register of size $m$ and a local gate acting once on each qubit. One could try to introduce some tractable quantumness to QIEA by taking the update circuit to be some Clifford quantum circuit, mentioned and outlined for example here and here. I do not know if this could offer any benefits at all, and as far as I know, this hasn't been tried.

[1] S. M. Anthony Brabazon, Michael O’Neill, Natural Computing Algorithms. Springer-Verlag Berlin Heidelberg, 2015.

|improve this answer
$\endgroup$
1
$\begingroup$

The question here seems to be: "can a classical computer be more efficient by simulating a quantum computer?" and "what research has been done on this?"

I think it's important, first, to point out that no one is 100% sure that a quantum computer is even actually better than a classical computer, whether or not we have the fastest possible algorithms for a classical or quantum computer for really any particular problem, and so forth.

I found an article from October 2017 that details an experiment IBM did simulating a 56 qubit quantum computer on a supercomputer. Here's what the study author said:

For instance, whereas a perfect 56-qubit quantum computer can perform the experiments "in 100 microseconds or less, we took two days, so a factor of a billion times slower"

(See their paper on arXiv for more information.) I also found a paper submitted to arXiv in February of 2018 which simulates a 64 qubit quantum computer, building on the work of IBM. They also estimate a 72 qubit circuit could be simulated.

What seems to be prevalent in all of this, though, is that these simulations are for help in comparison to quantum computing results and times, and none of them claim to show quantum computing "useless" or "replicable". So, my final answer would be no, this is not a thing.

|improve this answer
$\endgroup$
  • $\begingroup$ I think to say "I think it's important, first, to point out that no one is 100% sure that a quantum computer is even actually better than a classical computer" is not correct since we have already quantum algorithms that are much better than classical ones. So, if one can build a quantum computer able to run these algorithms we can see that quantum computers are better than classical ones. Another thing is to say that the quantum computer can take some "metric of time" to run these algorithms. $\endgroup$ – Gustavo Banegas Mar 27 '18 at 2:51
  • 2
    $\begingroup$ @GustavoBanegas We have quantum algorithms that are better than the best known classical algorithms, but we don't have proofs that the quantum algorithms are better than any possible classical algorithm. (Well, we do in settings like query complexity and communication complexity, but not for decision problems or sampling problems.) $\endgroup$ – Jalex Stark Mar 27 '18 at 4:29
  • $\begingroup$ "The question here seems to be: "can a classical computer be more efficient by simulating a quantum computer?" and "what research has been done on this?" Unfortunately, this is not the question, I'm sorry this might have looked like this. Also, I think this is already askes somewhere, so perhaps you can move your answer there? $\endgroup$ – Discrete lizard Mar 27 '18 at 4:43
  • 2
    $\begingroup$ @JalexStark Indeed, I understand the difference. Thank you. Also, I think that it needs to be consider some things such as "architecture" that a QC will run and how it will affect the performance of the QC. $\endgroup$ – Gustavo Banegas Mar 27 '18 at 11:35
  • $\begingroup$ @Discretelizard could you maybe edit to clarify your question then? $\endgroup$ – heather♦ Mar 27 '18 at 19:13

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.