# Why can't we simulate a Qubit using classical computer?

I am completely a noob in terms of quantum computing, have watched several videos to understand what Quantum computers are trying to achieve.

I am a programmer of classical computers. We have a concept called Duck typing :

Duck typing in computer programming is an application of the duck test—"If it walks like a duck and it quacks like a duck, then it must be a duck"—to determine whether an object can be used for a particular purpose.

So if we jot down the properties of a qubit, why can't we simulate it with our classical computer, and then array them to create further stronger computers?

• We can simulate a quantum computer. However, the simulation will generically be exponentially costly in the number of qubits. In particular, it is no problem at all to simulate a single qubit. Nov 22 '21 at 5:49
• Try to write some codes to simulate the measurement, you'll find you need $2^n$ commands to simulate the measurement result. Nov 22 '21 at 6:05

First of all, yes, we can simulate qubits. It is proven, that quantum Turing machine is equivalent to the classical one, so anything that can be computed on the quantum system, can be computed on the classical one (and vise versa).

However, there are some problems:

1. To represent $$n$$ qubits you need a vector with $$2^n$$ complex numbers, so this vectors quickly become quite large.
2. More over, to perform one "computational step", you need to multiply this vector by the corresponding unitary operator, which will be the matrix with $$2^n \times 2^n$$ complex numbers. The quickest matrix to vector multiplication algorithm is $$O(N^2)$$ which in our case becomes $$O(2^{2n})$$ for $$n$$ qubit system.

The whole idea of quantum computation is that for some tasks we can come up with an algorithm, which will require a small (usually, polynomial) number of quantum "computational steps".

Program for measuring in x direction with GHZ states. Try changing the value of max_dim and see the run time.

clear all; clc;
max_dim = 11;
for dim = 1:max_dim
% GHZ state
rho = zeros(2^dim, 2^dim); rho(1,1) = 0.5; rho(1,2^dim)= 0.5; rho(2^dim, 1) = 0.5; rho(2^dim, 2^dim) = 0.5;
up = 1/sqrt(2)*[1;1]; down = 1/sqrt(2)*[1;-1];
P = zeros(2^dim,1);
for i = 1:2^dim
measure = 1;
temp = i - 1;
for j = 1:dim
if mod(temp,2) == 0
temp = temp /2;
measure = kron(up,measure);
else
temp = floor(temp/2);
measure = kron(down,measure);
end
end
P(i) = measure'*rho*measure;
end
end

• Its not clear what this example is meant to show, or how it addresses the question? You are populating the vector $P$ with length $2^n$ so of course the result is exponential runtime. But this would still be the result if $P$ were populated by running the measurements on a quantum computer Nov 22 '21 at 17:03
• furthermore if you let $w$ be the function computing hamming weight of the binary representation of an integer, then for this GHZ example we have that $P_i = ( (-1)^{w(i)} + 1 ) / 2^n$ can be computed quickly. This suggests that the run time scaling for this program is due to inefficient implementation; maybe a better example would be some random density matrix Nov 22 '21 at 17:04
• @forky40 x-direction measurement and GHZ state is only an example. If you want to simulate measuring in an arbitrary direction, you need to know the probability to get different results first, then you can simulate the measurement process. Nov 23 '21 at 0:22

It is possible, and there are already existing simulators. For example, Microsoft released Q# back in 2017 in order to work on quantum algorithm, it came with a simulator as well, built on top of classical .NET:

In order to invoke the quantum simulator, another .NET programming language, usually C#, is used, which provides the (classical) input data for the simulator and reads the (classical) output data from the simulator.

source: wikipedia