10
$\begingroup$

When explaining a quantum algorithm, many revert to 'circuit-speak' by drawing a diagram of how qubits split off into transformations and measurements, however, rarely if not never would someone explaining a classical math algorithm revert to its representation in binary circuits. I would understand that this is because transforms and such don't exist in the binary world, but:

Doesn't this unnecessary focus on the computational details relating to computing-computing, rather than the mathematical/statistical/optimization problem that the circuitry merely only underlies, detract from the main problem/application at hand? Is the classical mindset just that intuitive and aligned to general human thought, that quantum circuits, on the other hand, will remain to be a standard explanation strategy?

$\endgroup$
  • 1
    $\begingroup$ "..rarely if not never would someone explaining a classical math algorithm revert to its representation in binary circuits" Actually, this was quite common among those involved in the development of computers in the 50's and 60's. In fact, it's how I learned to program (c. 1970). I've always assumed that the reason was that they were more familiar with electronic circuit logic, and because it represented a lower level logic that could explain the behavior of the higher level logic of CPUs and programs. $\endgroup$ – RBarryYoung Nov 19 at 20:26
13
$\begingroup$

You might find this analogy helpful: the development of quantum algorithms is still in the Booth's multiplication algorithm stage; we haven't quite reached dynamic programming or backtracking. You'll find that most textbooks explain the Booth's algorithm using the following circuit.

Multiplier circuit

That is in fact, the method in which the multiplication logic is implemented in most modern processors (with some minor modifications depending on the version). However, this kind of representation quickly becomes tedious when you move to on algorithmic techniques like looping and recursion which may involve multiple multiplication and division steps, among others. It would be crazy for textbooks to explain more advanced algorithms using hardware-level implementations like this. Not to mention that the basic hardware circuitries vary with the processor. If you've ever done assembly language programming this should resonate.

Classical algorithm textbooks like the CLRS evade this problem by framing the algorithms without any particular processor in mind. The basic algorithmic procedures like addition, multiplication, looping, etc. are all considered as black boxes. If you're interested to see the processor-specific implementation of a CLRS algorithm you could certainly write it up in some high-level language like C and then convert it to assembly. Fortunately, compilers do that tedious conversion on our behalf!

Now the interesting part is that the basic building blocks of quantum algorithms are not addition or multiplication as such, but rather operations like Fourier transform and amplitude amplification. Quantum algorithms are largely framed in terms of these basic transformations that are very easy to visualize using quantum circuits (at least, if we're using the gate model). It's really much more about convenience and much less about intuition.

Rest assured that if a textbook ever states a generalized quantum equivalent of the Dijkstra's algorithm it wouldn't be showing you all the gates required to implement it, but rather in terms of the elementary quantum operations whose hardware implementations would largely vary depending on the quantum processor you're using. The bottom line is that we're still in the assembly language stage of quantum computing.

$\endgroup$
  • $\begingroup$ looking forward to when quantum algorithms move beyond the Booth's multiplication algorithm/assembly language stage and compilers start working on our behalf. but thinking operations like Fourier and amplification would still require circuit diagrams. thanks $\endgroup$ – develarist Nov 19 at 15:37
  • $\begingroup$ Great answer. As far as I can tell, it matches my experiences described in my comment to the OP. $\endgroup$ – RBarryYoung Nov 19 at 20:28
  • 3
    $\begingroup$ Great answer, the only thing I would disagree with is that quantum algorithms are still in the Booth's multiplication algorithm stage. If you look at the papers referenced at Quantum Algorithms Zoo you will find many that use pseudo-code and have no circuits. $\endgroup$ – Kliuchnikov Vadym Nov 20 at 17:30
  • 1
    $\begingroup$ @KliuchnikovVadym That is true, yes. However, those algorithms are generally not found in introductory textbooks and aren't beginner-level as such. I wanted to give the OP a broad overview; your answer on the other hand emphasizes on the aspect you mentioned. $\endgroup$ – Sanchayan Dutta Nov 20 at 18:24
  • 1
    $\begingroup$ @develarist, here are a couple of examples of pseudo-code use in quantum machine learning: Quantum Perceptron Models, Generative training of quantum Boltzmann machines with hidden units $\endgroup$ – Kliuchnikov Vadym Nov 22 at 3:55
6
$\begingroup$

The state of quantum computing technology is still in its infancy, so implementation details are generally important when considering quantum algorithms. Number of gates, number of operations, types of gates (e.g. Clifford vs. non-Clifford) are often necessary information to evaluate the feasibility and value of a quantum algorithm.

In many cases quantum algorithms are still being optimized, and there are often competing approaches with different trade-offs being considered and iterated. As a result, even publications describing very complex algorithms often include circuit diagrams implementing novel functions to improve efficiency (e.g. Fig. 1: controlled SELECT).

The quantum circuit model is also one of the more intuitive ways to depict quantum computations. Quantum circuits are a restricted form of tensor networks (see e.g. here), which are often used more broadly in both physics and classical computing (particularly in machine learning).

Microsoft seems to be one of the leaders in terms of developing the level of abstraction of quantum computation that you seem to be referring to, embodied in Q#. However, effective abstraction is not always straightforward or necessarily more intuitive (see e.g. here).

$\endgroup$
4
$\begingroup$

In classical computing, both circuit diagrams and pseudo-code are used to explain algorithms. The choice between circuits and pseudo-code depends on the context. If the goal is to explain a highly optimized implementation of an algorithm on FPGA, a circuit diagram is probably more suitable. For example, see this paper on AES implementation on FPGA. Pedagogical explanation of AES uses pseudo-code.

Similarly in quantum computing, if one wants to explain a highly optimized implementation of a modular adder, they resort to showing circuit diagrams. Papers focused on more high-level quantum algorithms frequently contain no quantum circuit diagrams and use pseudo-code instead. A good example of such a paper is Quantum algorithm for linear systems of equations. If you look through papers referenced at Quantum Algorithm Zoo, you will find many that have no circuit diagrams in them.

It seems that many people get the impression that 'circuit-speak' is so common because quantum computing is taught from the ground up. Quantum circuits are one of the first concepts many get exposed to when learning quantum computing.

$\endgroup$
1
$\begingroup$

There are no classical registers in Quantum Computing

Another contributing factor I believe is that in classical computers you can have a well defined "current state at a given time" (stored notably in CPU registers and DRAM memory in modern systems), and this state changes with time (each CPU clock) in a controlled way.

Therefore, it is easier to map sequential description of an algorithm back to classical real hardware.

In quantum computing however, it is my understanding that you cannot save the "intermediate state of a computation" and operate on it in a later step: you set the inputs, and measurements, and information flows in a single indivisible step to the end of the circuit.

Therefore, unless we are treating quantum circuits as black boxes between classical registers, sequential algorithm descriptions don't make much sense.

So a more likely useful description of quantum computing looks more like the combinatorial logic blocks (i.e. blocks with no registers and therefore no state) in hardware description languages such as Verilog and VHDL, which are just textual descriptions of a graph of circuits.

For example, in a Verilog combinatorial block, when you say:

a = b + c

it doesn't mean "on the next clock cycle of the algorithm, the register a will be worth b + c" like in say C or Python.

It rather means: a is a wire, b is a wire, c is a wire, + is an adding circuit with b and c as inputs and a as output. As soon as b or c change, a also immediately changes.

$\endgroup$
  • $\begingroup$ you're saying classical uses sequential algorithm descriptions while quantum uses sequential logic blocks. both have the word sequential in them so what is the difference? And are these types of circuit graphs (the topic here), versus algorithm pseudocodes? As for classical registers, I have seen bits placed within circuit diagrams next to qubits in many algorithms though, and besides that I wasn't asking why classical circuits aren't used to describe quantum algorithms, but why classical circuits aren't used to describe classical algorithms as abundantly as quantum does quantum $\endgroup$ – develarist Nov 20 at 14:02
  • $\begingroup$ @develarist oops, I messed up sequencial and combinatorial, was meant to be combinatorial logic, fixed that. But basically: sequencial description is often more intuitive for classic and more implementable, but it is impossible for quantum: in quantum any algorithm description must somehow translate to a circuit. $\endgroup$ – Ciro Santilli 新疆改造中心法轮功六四事件 Nov 20 at 14:07
  • $\begingroup$ with sequential description being impossible, this is why they use circuit diagrams instead for quantum algos? $\endgroup$ – develarist Nov 20 at 14:10
  • $\begingroup$ @develarist yes, this is what I understand $\endgroup$ – Ciro Santilli 新疆改造中心法轮功六四事件 Nov 20 at 14:10
  • 2
    $\begingroup$ This is a good explanation of why existing abstractions can't be applied to quantum algorithms, but that doesn't mean there won't be new abstractions which are just as powerful as the field develops. There are already programming languages which don't express things as sequential instructions and explicit states - for instance, declarative logic languages such as Prolog or theorem assistants like Coq. $\endgroup$ – IMSoP Nov 20 at 16:09

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.