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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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