2
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ To evaluate the complexity of an algorithm, usually you define an oracle, which is nothing but a unitary that you assume to take a unit of time to run. The number of oracles in sequence defines your complexity. $\endgroup$ Commented Apr 3 at 16:41

1 Answer 1

2
$\begingroup$

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:

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.

$\endgroup$
5
  • 1
    $\begingroup$ Excellent! You mention that number of gates compared to number of qubits, I think this is a good measure for it. Do you know that, suppose we already have an algorithm (we already have the unitary matrix of this algorithm). Now we want to make a ciricuit to implement it. Is there any standard factorization method which can make the unitary matrix be decomposed to a sum of as few tensor product of basic gates as possible? $\endgroup$
    – tangyao
    Commented Apr 6 at 2:59
  • $\begingroup$ @tangyao: There is of course Solovay-Kitaev algorithm for decomposition of single-qubit gates: arxiv.org/abs/quant-ph/0505030. However, it is not very useful in practice. You can also check out the link in my answer to article Elementary gates.... During last year's many techniques for circuit decomposition were investigated, for example here: arxiv.org/abs/2101.02993. I am sure, you can Google many others... $\endgroup$ Commented Apr 6 at 5:07
  • $\begingroup$ @tangyao: If the answer is ok for you, could you please accept it? $\endgroup$ Commented Apr 6 at 5:08
  • 1
    $\begingroup$ how could I accept it? $\endgroup$
    – tangyao
    Commented Apr 7 at 7:00
  • $\begingroup$ @tangyao: It seems you found it out :-) and thank you for accepting:-) It is a habit on this site to mark an answer as accepted once you are content with the answer. Accepting the answer does not prevent others from posting another one. If you are more content with that another answer, you can of course accept it instead the previous one. $\endgroup$ Commented Apr 7 at 7:07

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.