0
$\begingroup$

I heard of Toshiba's quantum-simulating algorithm, and I am wondering about the ability to simulate quantum algorithms to get faster resolutions of problems. I thought about using a simulated Shor's algorithm to find the prime factors of an integer, versus General number field sieve. With today's tools, would it be faster to simulate Shor's or to use GNFS ? And what about the evolution in the future ? Moreover, is it interesting to simulate quantum algorithm for cryptography ?

$\endgroup$

1 Answer 1

0
$\begingroup$

I heard of Toshiba's quantum-simulating algorithm, and I am wondering about the ability to simulate quantum algorithms to get faster resolutions of problems.

Simulations of quantum computations are very effective when dealing with a relatively small number of qubits. A system of 4 qubits, for exmaple, can be simulated very easily becuase this system has only $2^4 = 16$ computational basis states, and the quantum statevector of the system, let it be for example $|\psi⟩$ has only $2^4 = 16$ entries.

Indeed, simulating quantum programs on classical computers is a very useful tool (mainly for studying the domain). As long as the number of qubits being simulated is less than, let's say, 20 (it can be more in powerful classical computers but not much more) - it is an excellent tool. I don't know that Toshiba simulator but there are many.

But, as you can see, the size of the quantum statevector that describes the state of the system is $2^n$, while $n$ is the number of qubits in the systems - I.e an exponential growth. If we consider a system with $n = 100$ qubits for example, then the quantum statevector of that system is of dimension $2^{100}$. This quantum statevector has an enourmous amount of entries. If we consider a sysytem with $n = 500$ qubits than $2^{500}$ is a number much (much) larger than all atoms in the entire universe. Performing computations with such immense statevectors is not feasible.

In fact - the notion of quantum computation was sort-of born from the understanding that simulating quantum-mechanical systems is not feasible on classical computers because the complexity of such quantum mechanical systems grows exponentially.


Question:

I thought about using a simulated Shor's algorithm to find the prime factors of an integer, versus General number field sieve. With today's tools, would it be faster to simulate Shor's or to use GNFS ?

Answer:

Running Shor's algorithm for large integers is still way beyond current technology. You can run Shor's algorithm for very small integers (like 15) and you'll get good results in both classical simulators and quantum computers. Maybe with strong classical computers you will be able to factor some bigger integers, but still those integers will be relatively small. The reason is that Shor's algorithm requires a nice amount of (logical) qubits for its functionality, and as we already figured out - the efficiency limit of classical simulations is somewhere around few dozens of qubits.

On the other hand, some very large semi-prime integers (200+ digits long) were factored using classical techniques like the GNFS so with today's quantum tecnology - GNFS is very much faster.


Question:

And what about the evolution in the future ?

Answer:

There are great efforts nowadays to build better and better quantum computers, while the goal is to achieve large scale fault-tolerant quantum computer. This holy grail is pretty far beyond our reach right now, and if someone will succeed - it will take at least several years and maybe much more.

$\endgroup$
1
  • $\begingroup$ That is a lovely response ! This helped me get a better understanding of quantum-simulation, thank you very much ! $\endgroup$
    – pwnd
    Aug 10, 2022 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.