Quantum computing can’t achieve better outcomes for general computing problems than classical computing can. It’s just possible to do particular kinds of algorithms with it (like Shor‘s Algorithm for factorising prime numbers) that classical computing can’t do. It’s still a lot of smoke and mirrors at the moment though.
Comment on How we get to 1 nanometer chips and beyond
theparadox@lemmy.world 1 day agoNot an expert but… typical computers do what they do by transmitting (primarily) electrical signals between components. Is there electricity or isn’t there. It’s the “bit” with two states - on or off, 1 or 0. Electricity is the flow of electrons between atoms. Basically, we take atoms that aren’t very attached to some of their electrons and manipulate them so that they pass the electrons along when we want them to. I don’t know if there is a way to conduct and process electrical signals without using an atom’s relationship with its electrons.
Quantum computing is the suspected new way to get to “better” computing. I don’t know much about the technical side of that, beyond that they use quantum physics to expand the bit to something like a qubit, which exploits superposition (quantum particles existing in multiple states simultaneously until measured, like the Schrodinger’s cat metaphor) and entanglement (if two quantum particles’ states are related to or dependent on each other, determining the state of one particle also determines the state of the other) to transmit/process more than just a simple 1 or 0 per qubit. A lot more information can be transmitted and processed simultaneously with a more complex bit. As I understand it, quantum computing has been very slow going.
That’s my shitty explanation. I’m sure someone will come along and correct my inaccurate simplification of how it all works and list all that I missed, like fiberoptic transmission of signals.
nightlily@leminal.space 1 day ago
Hadriscus@jlai.lu 1 day ago
Cheers ! so supposedly there has to be some tangible matter (atoms) to form the transistors ?
Quantum computing is exciting, I remember a magazine my parents had in the early 90s, that had a cover like “quantum computers ! soon !” lol
bunchberry@lemmy.world 19 hours ago
The reason quantum computers are theoretically faster is because of the non-separable nature of quantum systems.
Imagine you have a classical computer where some logic gates flip bits randomly, and multi-bit logic gates could flip them randomly but in a correlated way. These kinds of computers exist and are called probabilistic computers and you can represent all the bits using a vector and the logic gates with matrices called stochastic matrices.
The vector necessarily is non-separable, meaning, you cannot get the right predictions if you describe the statistics of the computer with a vector assigned to each p-bit separately, but must assign a single vector to all p-bits taken together. This is because the statistics can become correlated with each other, i.e. the statistics of one p-bit depends upon another, and thus if you describe them using separate matrices you will lose information about the correlations between the p-bits.
The p-bit vector grows in complexity exponentially as you add more p-bits to the system (complexity = 2^N where N is the number of p-bits), even though the total states of all the p-bits only grows linearly (complexity = 2N). The reason for this is purely an epistemic one. The physical system only grows in complexity linearly, but because we are ignorant of the actual state of the system (2N), we have to consider all possible configurations of the system (2^N).
The exponential complexity arises from considering what physicists call an “ensemble” of individual systems. We are not considering the state of the physical system as it currently exists right now (which only has a complexity of 2N) precisely because we do not know the values of the p-bits, but we are instead considering a statistical distribution which represents repeating the same experiment an infinite number of times and distributing the results, and in such an ensemble the system would take every possible path and thus the ensemble has far more complexity (2^N).
This is a classical computer with p-bits. What about a quantum computer with q-bits? It turns out that you can represent all of quantum mechanics simply by allowing probability theory to have negative numbers. If you introduce negative numbers, you get what are called quasi-probabilities, and this is enough to reproduce the logic of quantum mechanics.
You can imagine that quantum computers consist of q-bits that can be either 0 or 1 and logic gates that randomly flip their states, but rather than representing the q-bit in terms of the probability of being 0 or 1, you can represent the qubit with four numbers, the first two associated with its probability of being 0 and the second two associated with its probability of being 1. Like normal probability theory, the numbers have to all add up to 1, being 100%, but because you have two numbers assigned to each state, you can have some quasi-probabilities be negative while the whole thing still adds up to 100%.
Indeed, with that simple modification, the rest of the theory just becomes normal probability theory, and you can do everything you would normally do in normal classical probability theory, such as build probability trees and whatever to predict the behavior of the system.
However, this is where it gets interesting.
As we said before, the exponential complexity of classical probability is assumed to merely something epistemic because we are considering an ensemble of systems, even though the physical system in reality only has linear complexity. Yet, it is possible to prove that the exponential complexity of a quasi-probabilistic system cannot be treated as epistemic. There is no classical system with linear complexity where an ensemble of that system will give you quasi-probabilistic behavior.
As you add more q-bits to a quantum computer, its complexity grows exponentially in a way that is irreducible to linear complexity. In order for a classical computer to keep up, every time an additional q-bit is added, if you want to simulate it on a classical computer, you have to increase the number of bits in a way that grows exponentially. Even after 300 q-bits, that means the complexity would be 2^N = 2^300, which means the number of bits you would need to simulate it would exceed the number of atoms in the observable universe.
In practice, this increase in complexity does not mean you can always solve problems faster. The system might be more complex, but it requires clever algorithms to figure out how to actually translate that into problem solving, and currently there are only a handful of known algorithms you can significantly speed up with quantum computers.
For reference: arxiv.org/abs/0711.4770