While reading the Quantum algorithm Wikipedia entry, I noticed that the sentence "A quantum circuit consists of simple quantum gates which act on at most a fixed number of qubits", was annotated with a "why?".

  • $\begingroup$ That doesn't look like a good definition anyway. I don't see any particular reason to use the terms "simple" (without defining it) and "at most". $\endgroup$ – Sanchayan Dutta May 21 '19 at 17:34

Quantum circuits are a way to visualize a quantum operation/algorithm. As such, they are constrained by what you can reasonably express in a drawing. Simple algorithms on a small number of qubits are easy to express - for example, the ubiquitous teleportation circuit.

Algorithms on a variable number of qubits or algorithms that mix classical processing with quantum get harder to express, and the more complicated the algorithm is, the harder it gets.

This is similar to flow charts for classical algorithms - you can use them to visualize a small algorithm, maybe for educational purposes, or a high-level structure of a big algorithm, but you just can't express the internals of, say, a web-browser as a flow chart.

  • $\begingroup$ By way of agreement with @Mariia Mykhailova on this point, trying to express quantum phase estimation as a quantum circuit is already difficult, but iterative phase estimation algorithms often can't practically be expressed as circuits due to the use of classical logic as a part of the algorithm. This is why I find thinking of quantum programs as classical programs with quantum side effects (intrinsic gates) to be a much more helpful model than quantum circuits. $\endgroup$ – Chris Granade May 21 '19 at 18:06
  • $\begingroup$ @Chris I'd argue that quantum circuits aren't supposed to encapsulate classical logic, by definition. A quantum circuit is literally defined as a quadruplet $C=(V, I, O, G)$ where $V$ is the set of all qubits (including ancilla, input, and output), $I$ stands for the set of input qubits and $O$ stands for the set of output qubits. $G$ is a sequence of unitary transformations acting on a "bounded" number of qubits. This answer is kinda like saying "quantum circuits aren't useful for what they're not meant for in the first place"; isn't that obvious? I don't quite see the point here. $\endgroup$ – Sanchayan Dutta May 21 '19 at 18:28
  • $\begingroup$ [cont.] That said, it does raise an useful "practical" point. $\endgroup$ – Sanchayan Dutta May 21 '19 at 18:29
  • $\begingroup$ That's kind of my point, really: quantum algorithms in general involve classical logic, such that a construct such as quantum circuits that precludes classical logic as a matter of definition isn't the most natural tool to help understand quantum algorithms. $\endgroup$ – Chris Granade May 21 '19 at 18:31
  • 1
    $\begingroup$ @MariiaMykhailova Measurement of the non-input qubits isn't included in the standard definition of quantum circuits. As for measurement-based quantum computations (cf. one-way quantum computation), those can be mapped to equivalent quantum circuit models. Anyway, please don't get me wrong here: I do think your answer is useful to potential readers; it's more that I find the OP's question rather vague as it's based on a handwavy statement. :) $\endgroup$ – Sanchayan Dutta May 21 '19 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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