I want to know what time complexity is considered efficient/inefficient for quantum computers. For this, I need to know how many operations a quantum computer can perform per second. Can anyone tell me how to calculate it and what factors it depends on (implementation details or number of qubits etc.)?
Giving an estimate for a generic quantum chip is impossible as there is no standard implementation for the moment.
Nevertheless, it is possible to estimate this number for specific quantum chip, with the information provided online. I found information on the IBM Q chips, so here is the answer for the IBM Q 5 Tenerife chip. In the link you will find information on the chip, but nothing about timings. You need to access the version log of the chip (via a link given on the IBM Q 5 Tenerife chips page). In this version log, go to a "Gate Specification" section, you will have the following information (more explanation below):
- A time for "GD", which is 60ns in the link above.
- Multiple times for "GF" (let's take 200ns for the computations below).
- A "buffer time", which is 10ns in the link above.
But what do "GD", "GF" or "buffer time" represent? They are base physical operations, i.e. the operations that will be performed on the physical qubit. These physical operation are then used to implement some base quantum gates. You can find the decomposition of the 4 base quantum gates of the IBM Q backends in terms of these physical operations on the IBM Q 5 Tenerife chips page. I copied the illustration below.
Along with "GD" and "GF", there is a physical "FC" operation that does not appears in the timings. This is because this "FC" operation just "changes the frame of the following pulses" (citing Jay Gambeta from a conversation on the QISKit Slack), and so the "FC" operation has a cost (time of application) of 0.
The "buffer time" is just a pause time between each physical operation application.
So finally we can compute the time needed to apply each base gate on this specific backend:
- U1: 0ns
- U2: 60ns = 0ns + 60ns + 0ns
- U3: 120ns = 0ns + 60ns + 0ns + 60ns + 0ns
- CX: 520ns = 0ns + 60ns + 200ns + 60ns + 200ns
From these timings, you can deduce the number of operations per second that the ibmqx4 backend can perform.
Taking 200ns per operation as a crude approximation of the mean timing for an operation, you end up with 5 000 000 operations per seconds.
You can find the data for other backends on the qiskit-backend-information GitHub repository.
There is an important difference between physical operations and logical operations.
Physical operations that will be slightly imperfect, performed on qubits that are also imperfect. The rate at which these can be performed depends on what physical system is being used to realize the qubits. For example, superconducting qubits can perform two qubit gates (the slowest ones) in a time on the order of 100 ns (see Nelimee's answer).
By combining many physical qubits, and doing a process with lots of physical operations, we can build logical qubits. By doing error correction, these qubits and the operations done upon them can be made arbitrarily accurate. These are the kind of operations that are required to implement quantum algorithms.
There are currently too many unknowns to give you a clock rate of logical operations. Especially since even proof-of-principle logical qubits have not yet been built (not with quantum error correction codes, at least). It depends on how imperfect the physical qubits and operations are, and so how much we need to do to clean everything up. It depends on what kind of error correcting code we use, which in turn depends on the instruction set of our quantum processors (i.e., which pairs of qubits can have a two qubit gate applied on them directly). And this depends on how much noise we are willing to have, because better architectures often come at the cost of noise. So there are a lot of interdependencies, and much to be resolved.