Could quantum advantage be achieved using quantum simulator?

Quantum simulators (e.g. PennyLane’s built-in simulator default.qubit) can be installed in classical computers and we can implement quantum algorithms with them. I guess quantum simulators are actually performing matrix multiplications when simulating quantum operations. Even quantum entanglement can be simulated using the matrix representation of CNOT gate. If this is the case, how quantum simulators are different from classical computers which do the same thing, and is it possible to achieve any quantum advantage using them?

Hey @gojiita_ku, you can simulate a quantum computer on a classical computer but the resources used for the simulation are exponential. The size of the system grows as 2^n with n qubits. Thus, very quickly it becomes unrealistic to simulate larger systems. Real value of quantum computing comes from its use in simulating large quantum systems or the various quantum algorithms like Shor’s that require a very large number of qubits. This can not be done on a simulator as the system is too big.
You can try it out yourself. Increase the number of qubits in the default.qubit simulator and you’ll find that it becomes slower and slower.

2 Likes

Hi @ankit27kh, thanks so much for your explanation! I agree that the resources for simulating a quantum computer on a classical computer are exponential and it would be unrealistic to simulate large quantum systems.

Recently I read this tutorial from Qiskit, which is about applying QAOA and VQE to solving portfolio optimization problems. A classical method is also provided as a benchmark model in this tutorial. Following this tutorial, I performed a set of experiments. When the number of assets is small (e.g. 4), it takes much longer time for QAOA to solve the problem than classical method. Then I increased the number of assets without changing other hyper-parameters and checked the running times of both QAOA and classical method. I found when the number of assets reaches about 25, QAOA starts to run faster than classical method. When the number is 29, QAOA can demonstrate about 3X speedup over classical method. It seems like QAOA has a polynomial time complexity while classical method has an exponential time complexity. All experiments were conducted in my local classical computer. So can we consider this speedup as a quantum advantage obtained from a quantum algorithm itself rather than the quantum simulator?

What I mean is as follows. Quantum simulators can not provide quantum advantage, due to the required exponential resources. But quantum algorithms, even implemented on classical computers, can still help achieve quantum advantage when solving certain problems.

1 Like

Hey @gojiita_ku !

Demonstrating a quantum advantage involves a real-world task being performed on a real quantum device that would otherwise be impossible on a classical one. Indeed, implementing quantum algorithms on a quantum device to solve some task that would otherwise be impossible classically would constitute demonstrating a “quantum advantage”. In that sense, quantum algorithms certainly help! Unfortunately, merely simulating quantum algorithms doesn’t suffice.

1 Like

Hi @isaacdevlugt, thanks for your reply!

So what do you mean by merely simulating quantum algorithms?

And back to my case. Do you think the QAOA implemented on a quantum simulator (e.g. qiskit simulator) demonstrates a quantum advantage?

What I mean by “merely simulating” is that simulations don’t cut it for demonstrating quantum advantage. It has to be the real thing (i.e. use a real device and explicitly demonstrate a quantum computer doing something that a classical computer cannot).

To your QAOA question, unfortunately the answer is no :frowning_face: .

@isaacdevlugt. Ok, I got what you mean. Since the running time speedup is obtained on a classical computer rather than a quantum computer, it can not be considered as a quantum advantage. Am I correct?

But can I say my experiments show that the QAOA simulated on a classical computer has a better performance in terms of time complexity than the classical method?

Since the running time speedup is obtained on a classical computer rather than a quantum computer, it can not be considered as a quantum advantage. Am I correct?

Essentially, yes!

But can I say my experiments show that the QAOA simulated on a classical computer has a better performance in terms of time complexity than the classical method?

Absolutely! Simulating quantum algorithms classically can sometimes be better than other classical methods.

1 Like

This can be done for a very small size system. I am now doing this via calling quantum simulator. I can only run 4000+ training pairs with a QDL network with [5,1,5] architecture in a computer with 192 GRAM. If I change to [5,2,2,5], it short of memory and the program stop without finishing the whole process. Notice that the architecture is amplitude encoding and the actual training pairs I have is about 100,000++. Hope this experience can benefit you.

1 Like

Hi @SuFong_Chien, thanks for your sharing. What do you mean by QDL network? Could you please explain this network more specifically or share some links for it?

QDL is quantum dep learning. [5,1,5] means this architecture is with 3 layers, one input layer (2^5 inputs) , one hidden layer and one output layer (2^5 outputs).

What does the one represent if you tried 5 2 2 5 I assume that would be 2 hiddens because there are two middle numbers, but then what does the actual number represent?

[5,2,2,5] means this architecture consists of 4 layers, 1 input layer, 1 output layer, 2 hidden layers. It represents 2^5=32 inputs links to two quantum neurons in the 2nd layer, and etc. The neurons are represented by unitaries. In order to have better understanding for the qml, you can read the papers by Dr. Kerstin Beer (https://github.com/qigitphannover/DeepQuantumNeuralNetworks).

@SuFong_Chien Thanks for your explanation! I guess the quantum advantage of QDL lies in the higher performance in terms of accuracy (e.g. recognition accuracy for face recognition task) rather than computation efficiency. Did you compare the performance of your QDL models with classical deep learning models and observe any improvement?

Sometimes, it is difficult to compare since they are not in the same structure. However, physicists have tried to do that by looking at the effective dimension and Fisher information matrix. There are few very good papers have been published. One of them is https://scholar.google.co.uk/citations?view_op=view_citation&hl=en&user=-v3wO_UAAAAJ&citation_for_view=-v3wO_UAAAAJ:d1gkVwhDpl0C.

2 Likes