

There is a variant of classical computers called probabilistic computers where logic gates can randomly perturb a bit. These bits are called p-bits. Since the system is random, you can’t represent it by specifying each bit value individually since you don’t know their bit values. You specify them with a vector where each entry represents the probability of the bit being a particular value. For example, you would represent a single p-bit with a two-vector where the first number represents the probability of 0 and the second the probability of 1.
You also have to use a single vector for the whole system, called the state vector. If you have two p-bits, you don’t use two two-vectors, but a single four-vector. This is because two p-bits can become statistically correlated with one another, and so you need to represent them together to keep track of correlations. If you represent each p-bit individually, you will lose information about correlations.
The state vector grows in scale exponentially because it holds the probabilities for all possible outcomes, which for N bits there are 2^N possible outcomes. If we knew the state of the machine at a given time, we could represent it with separate two-vectors for each bit giving us a complexity of 2N (linear) for all the two-vectors combined, but the fact we are ignorant of its state at a given time requires us to represent it with a single vector with a complexity of 2^N (exponential).
What even is a probability distribution? Such as, if I say, this biased coin has a 25% chance of landing heads and a 75% chance of landing tails. What does that even mean? One answer is that the probability distribution represents an ensemble. An ensemble is an idealized experiment where you flip the same coin an infinite number of times and then distribute the results. Such a distribution should precisely have the ratio 25:75. An experiment ran an infinite number of times will clearly have greater complexity than an experiment just ran one time. The exponential complexity of the statistical description is usually understood to come from the fact that it represents an ensemble and not an individual system.
It turns out that the “logic” that underlies quantum mechanics can be described the mathematics that looks exactly like the mathematics of normal probability theory, but with the introduction of negative signs. These probabilities that can be negative are called quasi-probabilities. Despite common misconception, imaginary numbers are not necessary for quantum mechanics. You can reproduce all of quantum information science just with the introduction of negative numbers alone.
When you build out a probability tree, negative numbers allow certain paths to cancel out with other paths that have positive quasi-probabilities. This cannot happen in classical probability theory as probabilities are either positive or zero and thus can only accumulate. This cancelling are called interference effects and is the hallmark of quantum mechanics. Even entanglement effects, such as shown in violations of Bell inequalities, are just interference effects across statistically correlated systems.
Here is where it gets a bit weird. Recall how we said that the exponential complexity of the state vector of a probabilistic computer is assumed to be derivative of a combination of an infinite number of samples from simpler, linear, deterministic system, which this combination we call an ensemble. It turns out that you can prove that it is impossible for a system described by quasi-probabilities to be decomposed in the same way. There is no simpler, linear, deterministic system, which an infinite number of samples from it can give you a “quasi-ensemble.”
This means either one of two things. (1) Quasi-probabilistic systems are fundamentally random, unlike classically probabilistic systems, because there simply cannot be a simpler underlying deterministic state, or (2) there does exist an underlying deterministic state, but it has similar complexity to the “quasi-ensemble” itself. That is to say, the underlying, deterministic, and physical state of the system really is exponentially complex. That is to say, as you add N qubits, the complexity of the internal dynamics of the system really does grow by 2^N.
Either conclusion you draw, the outcome is the same: Unlike classical probability theory where we assume that the exponential complexity of the statistical description is ultimately derivative of our ignorance of an underlying state, in quantum mechanics, you either have to assume such an underlying state does not exist, or that the system really is just exponentially complex, and thus, in either case, you can only work with the exponentially complex description. There is no other description to work with.
This makes it impossible to efficiently simulate quantum computers with a classical computer, since the underlying complexity grows exponentially with each qubit you have. If you have 300 qubits, then the size of the state vector is 2^300, which is greater than the number of atoms in the observable universe. Whether you believe #1 or #2, the outcome is, again, the same: there is simply no way to break this apart into an infinite number of samples of a linearly complex system. To simulate it correctly and losslessly, you must indeed use a vector of this size, and so a lossless simulation of even 300 qubits on a classical computer is impossible.
This extra complexity means that the internal dynamics of a quantum computer is much more complicated than a classical computer, much more stuff is “going on” so to speak, and so can in principle get much more compute if you can figure out how to leverage that in a useful way.
Typically quasi-probabilities aren’t actually used often in practice, because introducing negative signs into classical probability theory breaks L1 normalization unless you double-up the size of the state vector. It is more mathematically concise to also introduce imaginary numbers, which lets you keep the state vector the same size as it is in classical probability theory, but containing complex numbers. These are called probability amplitudes. That is why imaginary numbers are used in quantum mechanics. They are not necessary just more concise. What is absolutely necessary and indispensable is the negative numbers, as these are what allows certain paths on the probability tree to cancel out with other paths.
Yes, you do just work with a vector and matrices that apply to the vector. The vector either can contain quasi-probabilities or probability amplitudes. But, besides that, it pretty much just works like normal probability theory. Each entry is associated with the likelihood of a particular outcome. If you have 3 qubits, you need an eight-vector because 2^3=8, where the probability amplitudes are associated with the likelihoods of observing 000, 001, 010, 011, 100, 101, 110, or 111 respectively. Unlike stochastic matrices of a classical probabilistic computer, you use unitary matrices, also can contain complex numbers.
Besides the use of complex numbers, the mathematics is, again, pretty much identical to regular old probability theory.
It may seem “abstract” because, in classical probability theory, you assume that the state vector is an abstract idealized description of an ensemble, which is different from the underlying physical state. But in quantum mechanics, the state vector cannot possibly be merely an idealized description of an ensemble. Either such an underlying state does not physically exist, or whatever physical state does exist, it must be related to the quantum state vector with similar complexity, and indeed some physicists interpret the quantum state vector to actually be the underlying physical state of the system.
There is no agreement or academic consensus on how to “interpret” the physical meaning of the mathematics, in terms of natural philosophy. Everyone agrees on the mathematics itself and how to make predictions with it, but if you are to ask what the mathematics actually physically represents, what is “really going on” inside a quantum computer, or, as well called them, what are the “beables” of the theory, this is a rather controversial topic without agreement.
Personally, I tend to be torn between two different answers to this.
One possibility is the answer of the physicists Carlo Rovelli and Francois-Igor Pris, which takes position #1, that outcomes are truly random an there is no underlying physical state because physical states are only meaningful when defined relative to another system during an interaction, and so it makes no coherent sense to speak of the particle as having an autonomous state as a property to itself. All the “paradoxes” in quantum mechanics disappear if you stop making absolute statements about particles, like “the spin of the electron is down,” and always instead append to this relative to what.
Another answer may be something akin to David Bohm’s pilot wave theory which takes position #2, where you assume that there is an underlying, simpler, deterministic state, but that it exists alongside the quantum state. The quantum state is separate thing, a separate “beable,” which influences how the particles behave. This gives you a picture that feels fairly Newtonian. I used to be more skeptical of this approach because the physicist John Bell proved such a picture cannot be compatible with special relativity, which, if true, might make it impossible for such an approach to reproduce the predictions of quantum field theory. However, the physicist Ward Struyve demonstrated that while it is indeed not compatible with special relativity, it is false to draw the conclusion that therefore it cannot reproduce the predictions of quantum field theory, and demonstrated that this is not actually an issue.
There are many other views in the literature as well.









It’s… literally the opposite. The giant AI models with trillions of parameters are not something you can run without spending many thousands of dollars, and quantum computers cost millions. These are definitely not services that are going to fall into the hands of everyday people. At best you get small AI models.