14
$\begingroup$

If one wants to start building a quantum computer from scratch inside simulations (like how people get to build a classical computer from scratch in the Nand2Tetris course), is it possible?

If yes, what would be some possible approaches?

Also, what will be the limits of such a simulated machine, given a specific amount of classical computing power? For instance, if we were to pick your average desktop/laptop, what will be the limit? If we take a supercomputer (like Titan) then what would be the limit?

$\endgroup$
6
$\begingroup$

The first part of your question seems like a duplicate of an existing QC SE post: Are there emulators for quantum computers?.

I'm not completely sure what you mean by building a quantum computer from scratch inside simulations. However, yes, you can make software simulations of a quantum computer using your average laptop/desktop. The exact "limit" will depend on the computer specifications.

Since a quantum computer does not violate the Church-Turing thesis, in theory it is definitely possible to simulate a quantum computer using an ideal Turing machine. The obvious approach to simulate such a system requires exponential time on a classical computer and the space complexity is an exponential function of the number of quantum bits simulated. Say, you simulate a $n$-bit quantum computer, you'd need to store about $2^{n}$ bits of information in your classical computer at every instant. Moreover, implementation of quantum gates will again take a huge amount of resources in terms of time and space complexity. An implementation of a quantum gate operating on $n$-qubits would have to store about $4^{n}$ (because you can represent all quantum gate operations as a matrix of size $2^{n}\times2^{n}$) bits of information.

You can sort of estimate the "limit" depending on the specifications of the classical computer. For example if the (accessible) memory size of your classical computer is around $1$ TB I'd expect you can simulate a $\log_4(8\times 10^{12})\approx 21$ bit quantum computer (to be on the safe side let's say $20$). However, keep in mind that classical computers would take much larger time to access all the individual bits of information, compared to an actual quantum computer (depending on the hardware of the quantum computer). So it's going to be slower than an actual quantum computer! Some other limitations are that after each action of a $n$-qubit gate you need to keep track of which output qubits are entangled, which is a NP-hard problem. Also, measurement cannnot be accurately simulated on a classical computer, because classically there is no truly random number generator.

$\endgroup$
  • $\begingroup$ You can actually simulate a bit more qubits if you use only 1 and 2 qubit gates to decompose your big unitary, and act on a pure state. With 8GB of RAM you can easily do 25 qubits in double precision. $\endgroup$ – vsoftco Jul 27 at 2:26
5
$\begingroup$

Well, I'm working on a simulator of a quantum computer currently. The basic idea of quantum computing, of course, is gates represented by matrices applied to qubits represented by vectors. Using Python's numpy package, this isn't that hard to program in the most basic sense.

From there, one might expand upon, of course, the interface. One might also consider trying to make it a simulator of a nonideal quantum computer, that is, taking into account decoherence times and error correction.

Then, you get into heavily uncharted territory. How do you construct the instruction set for a quantum computer? Who knows. You'll have to figure out. You'll also have to figure out your version of assembly, and even your version of higher level programming languages.

So, limitations of a classical computer in this? Well, this is a really complicated question (and worth asking separately, imho) but here's a quick summary:

  • we don't know if quantum computers are actually better than classical computers; the algorithms for classical computers could just not be good enough yet (quantum supremacy)
  • let's say, as seems decently likely, that quantum computers are better than classical computers. that improvement will depend heavily on the problem - quantum computers might see, for example, a much higher speed improvement in finding prime factorizations than in checking email. (see also this P.SE q/a.)
  • to provide some sort of numerical value, if we consider the current fastest algorithm for classical prime factorization finding, i.e., the general number sieve, we have an O-time of $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)$ which is clearly rather gross. Shor's algorithm, on the other hand, works in $O((\log N)^2(\log \log N)(\log \log \log N))$ which is obviously a lot faster.
  • I can run a bunch of qubits on my computer as long as I keep them in the $|0\rangle$ or $|1\rangle$ states - i.e., effectively classical. So in some senses, your question is again, kind of ill-defined.
$\endgroup$
4
$\begingroup$

I feel like this answer mostly rests on an underlying misunderstanding of what it means to "simulate" something.

Generally speaking, to "simulate" a complex system means to reproduce certain features of such system with a platform that is easier to control (often, but not always, a classical computer).

Therefore, the question of whether "one can simulate a quantum computer in a classical computer" is somewhat ill-posed. If you mean that you want to replicate every possible aspect of a "quantum computer", then that is never going to happen, just like you are never going to be able to simulate every aspect of any classical system (unless you use the same identical system of course).

On the other hand, you certainly can simulate many aspects of a complex device like a "quantum computer". For example, one may want to simulate the evolution of a state within a quantum circuit. Indeed, this can be exceedingly easy to do! For example, if you have python on your computer, just run the following

import numpy as np
identity_2d = np.diag([1, 1])
pauliX_gate = np.array([[0, 1], [1, 0]])
hadamard_gate = np.array([[1, 1], [1, -1]]) / np.sqrt(2)

cnot_gate = np.kron(identity_2d, pauliX_gate)
H1_gate = np.kron(hadamard_gate, identity_2d)

awesome_entangling_gate = np.dot(cnot_gate, H1_gate)

initial_state = np.array([1, 0, 0, 0])
final_state = np.dot(awesome_entangling_gate, initial_state)
print(final_state)

Congratulation, you just "simulated" the evolution of a separable two-qubit state into a Bell state!

However, if you try to do the same with, say, 40 qubits and a nontrivial gate, you are not going to be able to pull it off this easily. The naive reason is that to even just store the state of an $n$-qubit (non sparse) state you need to specify ~$2^n$ complex numbers, and this start taking a lot of memory very quickly. I say "naive" here because in many cases there may be tricks that allow you to avoid this problem$^{(1)}$. This is why many people work on trying to find clever tricks to simulate quantum circuits (and other types of quantum systems) with classical computers, and why this is far from trivial to do$^{(2)}$.

Other answers already touched on various aspects of this hardness, and the answers to this other question already mention many available platforms to simulate/emulate various aspects of quantum algorithms, so I will not go there.


(1) An interesting example of this is the problem of simulating a boson sampling device (this is not a quantum algorithm in the sense of a state evolving through a series of gates, but it is nonetheless an example of a nontrivial quantum device). BosonSampling is a sampling problem, in which one is tasked with the problem of sampling from a specific probability distribution, and this has been shown (under likely assumptions) to be impossible to do efficiently with a classical device. Although it was never shown to be a fundamental aspect of this hardness, a certainly nontrivial issue associated with simulating a boson sampling device was that of having to compute an exponentially large number of probabilities from which to sample. However, it was recently shown that indeed one does not need to compute the whole set of probabilities to sample from them (1705.00686 and 1706.01260). This is not far in principle from simulating the evolution of a lot of qubits in a quantum circuit without having to store the whole state of the system at any given point. Regarding more directly quantum circuits, examples of recent breakthrough in simulation capabilities are 1704.01127 and 1710.05867 (also a super-recent one, not yet published, is 1802.06952).

(2) In fact, it has been shown (or rather, strong evidence has been provided for the fact) that it is not possible to efficiently simulate most quantum circuits, see 1504.07999.

$\endgroup$

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.