22
$\begingroup$

I've read in many books and articles that because Schrödinger's equation is reversible, quantum gates have to be reversible. OK. But, classical physics is reversible, yet classical gates in classical computers are not all reversible ! So the reversibility of Schrödinger's equation doesn't seem to be the right reason for quantum gates to be reversible.

Or, maybe it is because quantum computers compute "quantumly", whereas classical computers do not compute "Newtonly" but mathematically. Or if I try to put it in another way : the classical equivalent of a "quantum computer" would be an "analog computer". But our computers are not analog computers. In an analog computer, the gates would have to be reversible. So in a way a quantum computer is an "analog quantum computer"

But maybe I'm wrong Thanks

$\endgroup$
3
  • 1
    $\begingroup$ It’s not so much about being analog or digital… there is a connection between information and entropy. Also you can have systems that are physically reversible and computations that are logically reversible. $\endgroup$
    – UVphoton
    Apr 20, 2022 at 1:53
  • 2
    $\begingroup$ Does this answer your question? Where does the irreversiblity came from if all the fundamental interaction are reversible? $\endgroup$
    – Roger V.
    Apr 20, 2022 at 8:46
  • $\begingroup$ I don't think it's a duplicate of the linked question. Knowing the thermodynamic origins of irreversibility doesn't immediately answer the question of why you'd want to avoid irreversibility when building a quantum computer specifically. After all, we don't need to avoid it when building a classical computer. I think this is a good question. $\endgroup$
    – N. Virgo
    Apr 21, 2022 at 5:45

7 Answers 7

16
$\begingroup$

Though your language is vague and handwavy, I would say you pretty much got it right. Classical physics is reversible at a microscopic level when you look at ALL degrees of freedom. However, we don’t look at all degrees of freedom in classical computers. As we flip bits in our laptops or smartphones we generate entropy and heat. This helps explain why we are able to generate irreversible classical gates.

As another answer mentioned, we could make reversible classical computers, however, if we did that, those would be more like analog classical computers than digital classical computers we have now. So this is sort of putting your “regular classical computers compute digitally, not Newtonianly” statement into different language.

Quantum computers, on the other hand, are different. (1) It is critical to control every quantum degree of freedom in a quantum computer to avoid decoherence as any decoherence contributes to computing errors (this is true in classical computing too, but because of the digital nature you are highly non linearly insensitive to environmental noise in a classical computer). (2) quantum computers DO compute Schrodingerly, so in a sense, even so-called digital quantum computers are kind of like analog computers. You kind of sense this in that if you change the state of a qubit slightly from one state to another you are creating a state that is quantum logically different than the original state. In a classical computer you are permitted to change the state of a bit by some amount but you still have the same logical bit.

These two reasons help explain why quantum computers are so prone to error. That said, researchers across the field of quantum information are working on quantum error correction protocols to mitigate quantum computers' sensitivity to environmental noise. As these techniques become more advanced, it may become the case that digital quantum computers do become more resilient and begin to look more like digital classical computers (which themselves do use classical error correction protocols).

It’s worth mentioning that even though I call digital quantum computers as being kind of analog, there is still a contrast between these and what I would truly call analog quantum computers or quantum simulators. In digital quantum computers you have a register of quantum two levels systems over which you have full control of each qubit and on which you perform discrete gates. In an analog quantum computer or quantum simulator, you have a bank of quantum systems which may have more than two states (maybe internal spin degrees of freedom plus external motional degrees of freedom), you likely don’t have complete control over each element of the system. And you perform simulations by tuning continuous interactions between the elements (likely the interactions are not between two specific elements, but rather many at a time). The advantage of quantum simulators is that they can much more easily access large systems with complex and highly connected interactions, a challenging task for digital quantum computers.

edit: As the comments and other answers point out: It is possible to have a reversible classical computer which still operates based on "gates" and "bits" and is thus still a digital classical computer despite being reversible. This will, however, be a different architecture for computing than we are typically familiar with for classical computers because familiar gates such as the AND gate would be impossible. (at least without ancillary bits I guess? I've never studied reversible classical computing so I can't speak very well to it.)

$\endgroup$
1
  • 3
    $\begingroup$ A reversible classical computer doesn't necessarily have to be an analog one. In fact there would be good reasons to build reversible digital computers in some situations (if it were practical to do so), since they would be able to achieve Landauer's bound on the power needed for computation. $\endgroup$
    – N. Virgo
    Apr 21, 2022 at 5:50
7
$\begingroup$

This answer is complimentary to some of the others, but I felt it necessary to more specifically address some of the OP's concerns.

  1. The "special power" of a quantum computer is not that it is reversible. However, we need effective reversibility (in the form of unitary operations) to preserve pure quantum information, which is important.
    • Yes, we can build a classical computer whose computations are reversible, but that does not alter the complexity class of problems it is expected to solve quickly. However, reversible classical computers theoretically have no lower bound on energy comsumption, and in practice may be more energy-efficient than non-reversible ones.
    • Reversing classical information you store on a computer does not mean you reverse the entire time evolution of all the particles in the computer: you only need to be able to reverse the logical degrees of freedom. So no need to discuss analog computers. In fact...
  2. It is far harder to reverse an analog classical computation than a digital one.
    • Analog computers are plagued by noise, which both diminishes their ability to solve hard problems consistently and to be reversed.
  3. In quantum computers, we also have to fight against noise to produce dynamics that are close to unitary (and therefore reversible).
    • While a closed system evolves unitarily by Schrödinger dynamics, to control the system dynamics we have to interact with it: to a degree, the system must be open, which exposes it to noise. One way to model this is to move to a density matrix evolving under a master equation that supports non-unitary time evolution.
    • Quantum computers require precise control and a fault-tolerant protocol to correct for noise. While there are plenty of ideas for both, to date they have not been married together and scaled up for large-scale quantum computation addressing "useful problems" better than a classical computer. (But in theory, it can be done, unlike in any devised analog computer!)
$\endgroup$
6
$\begingroup$

As noted by @Jagerber48, both Newtonian mechanics and quantum mechanics are reversible if you account for all degrees of freedom. However, for classical computers, we are typically dealing with "big" systems that have many degrees of freedom. Even though the transistors of classical computers are microscopic or even nanoscale, they are "big" in the sense that they still include many degrees of freedom (thousands of atoms and electrons) and the motion of these electrons and atoms are coupled (through phonons) to the astronomical number of atoms in the macroscopic silicon chip.

There are more ways to distribute energy into many tiny degrees of freedom (motion of atoms) than to put all of the energy in a single macroscopic degree of freedom, for example, the up-and-down motion of a bouncing basketball. So the Second Law of Thermodynamics says that energy will tend to flow from this single macroscopic degree of freedom into the small degrees of freedom (the basketball will stop bouncing leaving it and environment nearby slightly warmer). The loss of energy to the microscopic degrees of freedom is effectively irreversible since the likelihood of the energy going back into the up-and-down motion of the ball is so low as to be zero and it will never happen as long as you can stand to wait.

Billiard Ball Computers

Reversible classical computers have been designed assuming no friction or inelastic collisions. These are sometimes called billiard ball computers because they involve balls bouncing off each other to create logic gates. Macroscopic systems can be set up so that friction is small and loss of energy to small degrees of freedom is low enough that several steps of reversible computing can be done. In practice, air hockey tables work better than billiard table, due to their lower friction. I have seen demonstrations of multiple logic gates realized by colliding discs on air hockey tables (surprisingly, I can't seem to find videos of this on YouTube).

As we get smaller, less massive, and colder, quantum mechanics limits the number of degrees of freedom that are accessible. For cold gas atoms, collisions are very nearly reversible because the quantum mechanics says that there are certain energy states and you have to have certain amount energy to go into a higher state. So cold gas atoms can bounce off each other elastically: electronic degrees of freedom remain "frozen" (there isn't enough energy for the electron to reach an excited state). It usually takes a lot of energy to reach excited nuclear states, so the degrees of freedom in the nucleus are even more frozen. Cold gas atoms could therefore be used to construct a reversible classical computer capable of many operations before the irreversibility became a problem; however, such a computer probably wouldn't be practical (how would you even build it?).

As noted in another answer, the quantum analog of friction (losing energy associated with macroscopic degrees of freedom to smaller degrees of freedom) is decoherence. Decoherence keeps you from being able to do quantum calculations, so quantum computers, by their nature, must be in the reversible regime.

$\endgroup$
6
$\begingroup$

Note that classical computing can also be made reversible. Take for example AND gate. As pointed in one of the answers, if the result is 0 you are unable to decide which of the inputs is 0. However, if you copy input to output, i.e. the gate will have three outputs - copy of two inputs and actual AND output, then the gate is perfectly reversible.

In quantum computing, any operation (measurement and qubit reset being exceptions) is described by a unitary matrix (this comes from Schrodinger equation). Since for any unitary holds $UU^\dagger = U^\dagger U =I$, the $U$ is invertible ($U^{-1} = U^\dagger$) and hence you have an operation which is naturally reversible.

$\endgroup$
1
  • 1
    $\begingroup$ I would also add that in classical computing the inputs are not "erased" by the logic gate. Hence an "AND" gate is somewhat still reversible because the mapping $01 \to 1$ still has the inputs $01$ activated when the output $1$ is displayed and is in a sense still reversible (it is related to your answer). $\endgroup$
    – StarBucK
    Apr 20, 2022 at 12:43
3
$\begingroup$

Irreversibility comes from friction. Frictionless classical systems are (theoretically) reversible.

Practical computer design exploits friction to remove unwanted perturbations to the computer's state. Imagine that 3V is supposed to represent a "1", but for some reason a "1" at a particular node in the circuit is at 2.5V. The circuitry drives the node toward 3V, while its friction damps out the oscillations around 3V that would occur in a frictionless, reversible circuit.

In quantum systems, the analog of friction is called decoherence. For quantum computer designers, it's a problem. The whole point of quantum computing is that you theoretically get to explore a large number of state trajectories simultaneously in superposition. If the computer decoheres into a particular state prematurely, you lose the superposition. This is what makes quantum computers so fiddly: quantum computer designers cannot use irreversibility as a stabilizing tool.

$\endgroup$
2
$\begingroup$

Its partly about energy dissipation, information theory and entropy. Also circuit design and practicality. There is a thing called the von Neumann Landauer limit that for irreversible operation for one bit you have to dissipate $kT\ln2$ of energy. Current transistor expend much much more energy per bit. In the future though perhaps one can approach that limit. So people do think about and design reversible gate using classical devices. Some argue that these types of logic may help some computer architectures, even when the individual devices are not near the the theoretical limit.

People interested in these types of topics talk about adiabatic computing and charge reversible computing and the amount of entropy increase circuit operations have.

The quantum gates I think are reversible because it is a coherent system, but once the wave function collapses you probably have an increase in entropy if you have performed the equivalent of a logic operation.

$\endgroup$
1
$\begingroup$

Reversibility if and only if there exists a one-to-one mapping between output and input signals.

Consider a conventional AND gate:

enter image description here

If the gate's output lead has a signal, we know both input leads had a signal. However, if there is no output signal, we only know that one or both of the input leads had no signal, not which one(s), so we cannot map backwards from output to input.

On the other hand, a NOT gate has a one-to-one mapping of inputs to outputs and is thus reversible. If there's no output signal, we know there was an input signal; and if there is an output signal, we know there was no input signal.

$\endgroup$
1
  • 3
    $\begingroup$ True, but does not seem to have much to do with OP's question (first sentence)? $\endgroup$
    – AnoE
    Apr 20, 2022 at 9:11

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.