3
$\begingroup$

A general classical gate accepting $m$ inputs and producing $m$ outputs has total $2^{2^m}$ number gates (which may or may not have names.) Thus number of gates functions are finite.

But QC allows to have infinitely many quantum gates (unitary operations).

  • Does this fact of having infinite number of gates for n-qubits serves any advantage over classical computers?
  • If yes, does this implies that to solve a particular problem, there should exist a combination of gates (a circuit)?
$\endgroup$

2 Answers 2

1
$\begingroup$

A classical bit is a binary piece of information - I.e it can be 0 or it can be 1 (we can choose also up/down, true/false - it doesn’t matter). Exactly 2 states for a classical bit.

A qubit can be in a quantum state out of infinite amount of possible states (though in the end it collapses to a single value out of possible 2, just like the classical bit). A quantum state of a single qubit is well represented using the a sphere called the Bloch sphere - any point on the surface of the sphere corresponds to a possible quantum statevector of a single qubit. Think of quantum gates as a movement of the statevector on the surface of the sphere. Since there are infinitely many points on the surface of the sphere there are infinitely many “movements” or “rotations” we can perform to the statevector - any such rotation is equivalent to a quantum gate. Practically, the physical ability to perform “little” rotations is limited, so there aren’t infinitely many possible gates - there are many, but it is a finite amount.

Having explained that - to my knowledge - that’s not the ingredient giving quantum computation advantage over classical computation. The power of quantum computation arises from sophisticated manipulations of 3 important quantum properties - superposition, entanglement and interference.

About that:

If yes, does this implies that to solve a particular problem, there should exist a combination of gates (a circuit)?

Not everything is computable. However, if a problem is computable on a classical computer then it is computable (theoretically) on a quantum computer, and there is some sequence of quantum gates that implements the desired computation.

$\endgroup$
2
  • $\begingroup$ I think it is important to address the false assumption that quantum computers have an infinite amount of quantum gates available. With the current technology, we can only approximate the real line as a finite set of numbers $\endgroup$
    – MonteNero
    Aug 16, 2022 at 21:51
  • 1
    $\begingroup$ You’re right. Added a note about that. Thanks $\endgroup$
    – Ohad
    Aug 16, 2022 at 22:46
3
$\begingroup$

No, it doesn't really help.

Consider that, when using quantum error correction, the gate set is finite (for example: CNOT, H, T). It's not possible to have a fault tolerant gate set that is infinitely large, because the separation between the intended gates needs to be bounded away from zero in order for the code distance to be bounded away from zero. But no one is saying fault tolerant quantum computers are fundamentally less powerful.

To achieve arbitrary gates in quantum error correction, you approximate the target gate by decomposing it into a sequence of the available gates. The approximation can be made exponentially more accurate by increasing the length of the decomposition. So, for example, in practice, you'd never need more than 50 gates to approximate all single qubit gates to a level that would be indistinguishable from perfect.

So, at best, having an infinite single qubit gate set gains you a factor of 50 over having a discrete single qubit gate set. It doesn't give you any sort of asymptotic advantage that grows with problem size.

$\endgroup$

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.