Are all quantum computers feedforward networks?

[Agrippa]

TL;DR Summary

I am trying to understand how advanced quantum computers have in fact become as well as how advanced they can in principle become. To probe these issues, I am asking the group whether or not quantum computers are restricted to feedforward processing?

Hi! I am trying to understand how advanced quantum computers have in fact become as well as how advanced they can in principle become. To probe these issues, I am asking the group whether or not quantum computers are restricted to feedforward processing, both currently and in principle?

Here is the context to my two questions:

Examples of feedback and feedforward networks:
The simplest feedback network is a system of two binary nodes (A and B) that swap their states at each time-step. For example, If A is on (off) at t1, it will turn B on (off) at time t2, and vice versa. The simplest feedforward network cuts the connection from B to A, so that only A affects B.

Are current quantum computers restricted to feedforward networks?
It is possible to build the simplest feedback network (classically). Though you will need another node C that acts as input to AB to initiate the swap. This is called a Fredkin gate. I was shocked to discover that a quantum Fredkin gate has already been built. However, on further analysis, the quantum computer only acts like a Fredkin gate (by implementing its truth table), but it does so in purely feedforward manner. So I'm wondering, does anyone know of any examples of feedback processing in quantum computers?

Are quantum computers restricted in principle to feedforward networks?
Here is a (speculative and undercooked) reason to suspect quantum computers are restricted to feedforward networks. To achieve feedback connectivity, one would need to first use feedforward processing to yield a superposition of classical feedforward activity. But then how could this superposition be made to interact with the earlier parts that triggered the feedforward processing?

 

[f95toli]

The short answer to your question is "no, they are not".
The longer answer to your question really depends on the type of QC you are thinking of (gate based, analogue, only measurement based QC etc) and if you are referring to only QC that already exist, or QC that we (hopefully) will be able to eventually build. What you can and can not do will obviously change dramatically if you had a fully error corrected QC.

Note also that there are also a higher level question: defining what a quantum computer (or more generally q quantum processor unit) "is" turns out to be quite tricky; circuit based models do not always work very well IRL even for gate based machined and this has some practical consequences once you want to start defining abstraction layers in the SW and HW stacks

 

[Agrippa]

Thanks! I understand the difficulty in defining "quantum computer", but I think finding an answer to my question would help with this.

I am asking the question for any quantum computer, whether gate based, analogue, or measurement based. I am asking both for already built and merely physically possible quantum computers.

I think measurement based quantum computers are all feedforward networks. They involve quantum feedforward processing, then a measurement, then the outcome used as input into new quantum feedforward processing.

I'm not sure about gate-based or analogue. I would like to know.

Perhaps one way to have feedback processing in a quantum computer would involve a Schroedinger's cat set-up, replacing that cat with a classical computer implementing classical feedback processing. The computer would be in a superposition of doing one sort of feedback processing and another sort (or none at all).

But for this to be a quantum computer, it seems that the two branches of this superposition would have to recombine to yield an outcome/computation. This seems impossible.

But there may be other ways of achieving quantum feedback processing, would be great to find out.

 

[Strilanc]

You definition of "feed forward" sounds vague enough that everything is feed forward. Do you consider classical computers feed forward? After all, they're made up of logic gates whose input determines their output but whose output does not determine their input. Or, at the software level, the new value of a variable is determined by the old values but not vice versa.

Quantum computers are no more fundamentally feed forward than classical computers are.

 

[Agrippa]

Do you consider classical computers feed forward? After all, they're made up of logic gates whose input determines their output but whose output does not determine their input.

That doesn't seem correct. For example, here is a simple classical circuit with a feedback loop:

http://bibl.ica.jku.at/dc/build/html/sequentiallogic/sequentiallogic.html#feedback-loops

Classical computers are therefore not typically feedforward.

But I'm yet to see any quantum computer (broadly defined) that is anything other than feedforward.

You definition of "feed forward" sounds vague enough that everything is feed forward.

I'm trying to use standard definitions here e.g.
https://en.wikipedia.org/wiki/Feedforward_neural_network

 

[atyy]

I'm trying to use standard definitions here e.g.
https://en.wikipedia.org/wiki/Feedforward_neural_network

You can unroll (through time) a recurrent neural network so that it looks like a feedforward neural network.
https://machinelearningmastery.com/rnn-unrolling/
http://nikhilbuduma.com/2015/01/11/a-deep-dive-into-recurrent-neural-networks/

 

[Agrippa]

You can unroll (through time) a recurrent neural network so that it looks like a feedforward neural network.
https://machinelearningmastery.com/rnn-unrolling/
http://nikhilbuduma.com/2015/01/11/a-deep-dive-into-recurrent-neural-networks/

Theoretically you can, because both type of networks are universal function approximators.

But my question is not about what is theoretically possible, it is about what is physically possible, hence why I post this in quantum physics thread.

Unfolding ("unrolling") typically requires that the unfolded feedforward network has many more nodes. In physical systems, this leads to more mass, energy, heating etc. i.e. a barrier to function replication.

 

[atyy]

Would you consider quantum feedback to be what you are asking about?
https://en.wikipedia.org/wiki/Quantum_feedback
http://tcct.amss.ac.cn/newsletter/201108/images/MatthewJames.pdf
https://arxiv.org/abs/quant-ph/0402017

 

[Agrippa]

Would you consider quantum feedback to be what you are asking about?
https://en.wikipedia.org/wiki/Quantum_feedback
http://tcct.amss.ac.cn/newsletter/201108/images/MatthewJames.pdf
https://arxiv.org/abs/quant-ph/0402017

Thanks, those are extremely helpful links!
They seem to suggest that there are two types of "feedback" processes in quantum computation:

1) Measurement based feedback:
The quantum system takes input, evolves, then is measured... the experimenter then uses the measurement outcome as new input into the quantum system (and that's the feedback).

2) Coherent quantum feedback:
A quantum system exhibits "classical" feedback connectivity, but only because the quantum system is separable into subsystems that interact (feedback) coherently, without become entangled.
(A couple of great examples are described here: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.62.022108).

As mentioned above, I discount 1), since the feedback involves the observer collapsing the system with a measurement - I'm looking for feedback connectivity within the system, before the observer collapses the system.

So, I was fascinated to read about 2). That is indeed a kind of observer independent feedback connectivity in a quantum system! But it's not what I had in mind - it's not sufficiently quantum. While it does uses quantum systems, their "quantumness" is not really used: nothing is entangled and there are no superpositions of computations.

So we might distinguish:

3) Superpositions of classical feedback processing?
This would involve putting the system into a superposition of classical feedback processes. For example, we might put the system mentioned in 2) above in a superposition of undergoing feedback connectivity and not undergoing it.

Is this category possible? Or does decoherence prevent us from recombining the branches of the superposition in a computationally useful way?

 

[Strilanc]

That doesn't seem correct. For example, here is a simple classical circuit with a feedback loop:

http://bibl.ica.jku.at/dc/build/html/sequentiallogic/sequentiallogic.html#feedback-loops

Why do you think quantum computers can't have the same types of loops? Just put a loop in the quantum circuit conditioned on a measurement result. Quantum computers can do everything classical computers can do, so of course they can loop.

 

[Agrippa]

Why do you think quantum computers can't have the same types of loops? Just put a loop in the quantum circuit conditioned on a measurement result. Quantum computers can do everything classical computers can do, so of course they can loop.

I think the distinction made in my previous post helps here, we can distinguish three types of quantum feedback connectivity:

1) measurement-based (measurement outcomes are also input)
2) coherent feedback (separable quantum systems simulate classical feedback)
3) superpositions of classical feedback

Category 1) is what I think you're getting at when you say "conditioned on a measurement result". But this is not a real feedback loop in the quantum system itself if the observer is an essential component of the loop.

Category 2) does indeed show that "quantum" computers are capable of feedback loops. However, their quantumness plays no role (no superpositions, no entanglement, just classical feedback simulated by separable quantum systems interacting coherently).

Category 3) is what I ultimately had in mind, I guess. But the worry here is that decoherence will prevent us from recombining the branches of the superposition in a computationally useful way.

 

[Strilanc]

There's nothing fundamental that prevents you from making a quantum CPU with a quantum program counter, a quantum instruction decoder (for reversible instructions), a quantum RAM, etc. Nothing prevents you from then loading a superposition of programs and inputs, ticking the CPU some number of times, then reading off the results.

The problem is that the overhead of decoding an arbitrary instruction that operates on data loaded from QRAM, compared to doing a fixed instruction, is *really really ridiculously high*. Instead of doing a single CZ between two qubits, you have to do hundreds of thousands of CSWAPs and Toffolis and other expensive operations in order to move the data out of QRAM (keep in mind the address may be a superposition! If you didn't touch all data that would mean certain addresses were not allowed), select the correct result from the quantum ALU which by the way performed every supported operation (again, you need to do all of them because in some branches of the superposition the other ones might be relevant), etc, etc, etc, etc.

The same thing is true classically, by the way. This is why CPUs are thousands of times less efficient than chips specialized to a certain task.

Anyways, in order to avoid paying these ridiculous overheads, we try to move as much logic into the classical control system as possible (because quantum operations are much more expensive than classical operations). Most quantum protocols can be reduced to quantum subroutines whose instructions can be precomputed classically, instead of being decoded under superposition, so that's what we do. As a result, almost everything you see in textbooks is about isolated quantum subroutines instead of monolithic quantum systems that handle everything themselves. As it turns out, being able to do arbitrary program execution is utter massive overkill for most quantum algorithms. Also it would be a pain to sync them back up at the end (e.g. the program counter has to agree between the various branches in order for them to interfere).

A concrete example of a quantum system that has what I would consider a feedback loop is the way that photonic hardware companies intend to implement the surface code. They intend to use delay lines that literally loop qubits back around to interact with other qubits at a later time. Yes they still use classical hardware to control the thing, but I really think that's splitting hairs.

I'll also note the deferred measurement principle, which basically says that all classical feedback can be replaced with quantum controlled operations.

 

[Agrippa]

Above I distinguished what I take to be the three possible ways that a quantum computer could realize feedback connectivity. And I argued that category 3 (superpositions of classical feedback) is the truly interesting one, since the feedback processing is fully in the computer itself (unlike category 1) and it is truly quantum (unlike category 2). I then suggested that category 3 is infeasible because decoherence will prevent us from recombining the branches of the superposition in a computationally useful way.

If I've understood, you address category 3 and make the following three points.

First, it seems you agree that a challenge in implementing category 3 is decoherence, as you say:

Also it would be a pain to sync them back up at the end (e.g. the program counter has to agree between the various branches in order for them to interfere).

Second, you have suggested another challenge in implementing category 3, where you say:

Instead of doing a single CZ between two qubits, you have to do hundreds of thousands of CSWAPs and Toffolis and other expensive operations in order to move the data out of QRAM

This is interesting. Is the idea that the system that moves the data out of RAM must not entangle with that data, and this is what requires all the CSWAPS and Toffolis?

Third, you have suggested that despite these two challenges, category 3 has indeed already been physically implemented:

A concrete example of a quantum system that has what I would consider a feedback loop is the way that photonic hardware companies intend to implement the surface code. They intend to use delay lines that literally loop qubits back around to interact with other qubits at a later time. Yes they still use classical hardware to control the thing, but I really think that's splitting hairs.

This may well be what I'm looking for! However, there's not quite enough here for me to research the example. Would you be able to provide more information e.g. links or even just some search terms? I would like to identify a real concrete example and verify whether it really does fall under category 3.

 

[f95toli]

You need as was mentioned above be a bit more specific about what you are asking about. Decoherence (And parameter fluctuations) is the main limitation for just about everything we are doing with the current (small to medium NISQ QPUs) generation of machines but this will (hopefully) no longer be an issue once a fully error corrected machines becomes available .

Such as machine would open up many new possibilities in terms of algorithms and topology so we can be pretty sure that a large number of designs will be implemented and tried.

My main point is that asking about "fundamental" properties of QC while at the same time worrying about decoherence is a bit strange, in a "perfect" QC there is no decoherence.

 

[Agrippa]

You need as was mentioned above be a bit more specific about what you are asking about. Decoherence (And parameter fluctuations) is the main limitation for just about everything we are doing with the current (small to medium NISQ QPUs) generation of machines but this will (hopefully) no longer be an issue once a fully error corrected machines becomes available .

Such as machine would open up many new possibilities in terms of algorithms and topology so we can be pretty sure that a large number of designs will be implemented and tried.

My main point is that asking about "fundamental" properties of QC while at the same time worrying about decoherence is a bit strange, in a "perfect" QC there is no decoherence.

Fair enough. The main questions here have transformed thanks to the feedback. In my original post, I asked two questions:

1. Are current quantum computers restricted to feedforward networks?
2. Are quantum computers restricted in principle to feedforward networks?

atyy answered both questions with a resounding "no", by pointing me towards quantum coherent feedback:
https://journals.aps.org/pra/abstract/10.1103/PhysRevA.62.022108

This (together with one of your earlier posts that mentioned measurement-based QCs) then lead me to
distinguish between three types of quantum feedback connectivity:

(1) measurement-based (measurement outcomes are also input)
(2) coherent feedback (separable quantum systems simulate classical feedback)
(3) superpositions of classical feedback

I don't consider (1), since it isn't feedback connectivity in the quantum system itself (which is what I'm trying to understand). Rather, the feedback just involves the experimenter feeding measurement results back into the quantum system.

What I think (!) I've learned about (2) is that current quantum computers can realize this kind of feedback connectivity, but it is oddly classical: the components of the quantum computer remain separable (they do not entangle). For example, the ion trap example here implements a swap gate by coherently evolving three systems from |ψ>|0>|φ> to |φ>|0>|ψ>.

Category (3) seems like a truly quantum type of feedback connectivity. Is it possible in principle? It must be: since the previous example of coherent feedback is possible, it must also be possible in principle to put a system in a superposition of implementing different kinds of coherent feedback connectivity.

So, the only remaining question (assuming everything so far is correct) is how feasible category (3) is, and especially, are there any existing examples. The decoherence challenge should perhaps be called the recoherence challenge, because the real difficulty (I think!) is category (3) won't count as a quantum computer unless the two branches of the superposition can be recombined in some computationally useful way.