The time complexity of quantum circuit

Question

I want to figure out how to evaluate the time complexity of a quantum circuit.

An simple understanding is that if there are more quantum gates in a quantum circuit. The time complexity is higher. (under the assumption that the scale of input is fixed)

For example, I have n quibit and created a series of quantum gates. then I can write down the circuit mathematically by a series of matrix multiplication. An example is three CNOT gate one-by-one. Then the number of matrices is 3.

Now I want to evaluate the time complexity for excuting this quantum circuit(algorithm).

How to evaluate it? Can I assume that the time complexity is proportional to the number of matrices above? If so, does that mean that when I want to design an quantum algorithm, I need to consider the number of quantum gates for constructing this circuit?

But according to my understanding, an quantum algorithm is just a unitary matrix, so do I need to consider a method to decompose this matrix into the sum of as few tensor prodcuts of gates as possible. But this is a pure mathmatical question.

And I know that every unitary matrix can be decomposed to a series of basic quantum gates by the universal theorem, but I am not sure about the number of gates used for it or how to evaluate the time-complexity. And the decomposition in the proof of this theorem may not be the best decomposition.

Is my understanding of this correct or not?

Answer 1

There are several ways how to compute complexity of a quantum circuit. Number of gates to be executed and how this number is dependent on number of qubits is definitely good starting point. Once number of gates scales exponentially with number of qubits then such algorithm can be hard to run on a quantum computer.

However, not only total number of gates is important. The complexity of the circuit also depends on number of special single-qubit T gates. This gate does not belong among so-called Clifford gates. Hence, it cannot be simulated efficiently on a classical computer and moreover, it is also time consuming to run such gate on a quantum computer. Additionally, there is another measure of complexity of a quantum circuit which is number of two-qubit CNOT gates. Although CNOT is Clifford gate, because of its multi-qubit nature, its costs are higher than in case of single-qubit gates.

Overall, when designing a quantum circuit, we try to minimize number of T and CNOT gates. What is more, we look for circuits for which number of gates scales polynomially in number of qubits. Number of gates clearly implies time complexity of an algorithm. For example, once the number scales exponentially, time complexity is also exponential.

On top of that, you should also consider how does your native gates set looks like. In other words, what are costs of decomposing your gates into this native ones (see some examples in classical article Elementary gates for quantum computation).

Here are several other links that can help you to better understand how to calculate the complexity (or "quantum costs") of your circuit:

• What is the definition of an "efficient" algorithm?
• Why do we care about the number of T gates in a quantum circuit?
• T gates and T factories
• Why are non-Clifford gates more complex than Clifford gates?

And in article Circuit for Shor's algorithm using 2n+3 qubits you can find an example how complexity of a given circuit (in this case for Shor algorithm) is actually calculated.