concept

complexity

The measure of computational resources required, which doubles with each added qubit in a simulation.
75 related articles

Description

Complexity, in the context of quantum computing, refers to the exponential growth of computational resources needed to simulate a quantum system on a classical computer. As each qubit is added, the state space doubles, so a system of n qubits requires 2^n complex amplitudes to describe fully. This exponential scaling is the fundamental reason why quantum computers are so hard to simulate classically — even a few hundred qubits exceed the memory of any conceivable classical machine. This complexity is both a challenge and an opportunity: it makes quantum systems difficult to understand, but it also underpins the potential of quantum computers to solve problems that are intractable for classical computers.

History

The exponential complexity of quantum simulation was first articulated by Richard Feynman in 1982, who proposed quantum computers as a way to simulate quantum systems efficiently. The formal complexity-theoretic framework was developed by David Deutsch and others in the 1980s–1990s.

How it works

The complexity arises from quantum entanglement and superposition. A classical simulation must track the probability amplitudes of all possible states, which grow as 2^n. For n=50, this is about 10^15 amplitudes, already beyond practical classical memory. Quantum computers exploit this complexity by manipulating these amplitudes directly through quantum gates, performing operations that would require exponentially many classical steps. The complexity also manifests in the difficulty of error correction, as quantum states are fragile and require redundancy to protect against decoherence.

In practice

This complexity is the basis for quantum advantage in simulating molecules, materials, and other quantum systems, with applications in drug discovery, cryptography, and optimization.

Fun fact

A quantum computer with just 300 qubits would require more classical bits to simulate than there are atoms in the observable universe.

Concept graph →

Related articles · 75

Quantum Physics2026-08-161 minarXiv:2608.15795express
Complex quantum system revealed through small parts
Quantum systems made of many particles are the basis of future computers and secure networks. But the more particles there are, the harder it is to understand how they are arranged: the number of possible states grows like an avalanche. The usual approach, measuring everything, takes an incredibly long time.
Quantum Physics2026-08-111 minarXiv:2608.10663express
Quantum Bridge Between Nodes
An ordinary random network is like a road map: to connect four cities with a complex interchange, you need to lay down many highways. In the quantum world, things are different.
Quantum Physics2026-08-032 minarXiv:2608.02773express
A Quantum Code That Isn't Afraid of Errors
A quantum computer is like an orchestra where each musician-qubit easily loses the rhythm. The slightest noise, and the melody of computation turns into cacophony. To keep the orchestra playing in harmony, you need a conductor who instantly spots wrong notes and corrects them without stopping the performance.
Quantum Physics2026-07-312 minarXiv:2607.29582express
Quantum First Aid for Power Grids
An electrical grid stuffed with power electronics resembles a huge orchestra without a conductor. Each converter, each line adds its own note, and sometimes the instruments start playing out of tune.
Quantum Physics2026-07-261 minarXiv:2607.23773express
How to Tell a Tangled Ball from a Thread
The quantum world is full of strange connections. Two particles can become “entangled”: the state of one instantly affects the other, even if they are kilometers apart. But how do you know if they are truly entangled? It's like a ball of yarn: at first glance, you can't tell whether it's a single tangled ball or just a mess of loose threads.
HEP Theory2026-07-232 minarXiv:2607.21734express
Complexity Gets Tangled Midway
Water turns to ice at zero degrees — sharply, with no intermediate states. Something similar happens to complexity when we take a random quantum state of an entire system and look only at a part of it. As long as that part occupies less than half the system, its complexity grows smoothly. But as soon as the fraction crosses 50%, a jump occurs.
cs.SE2026-07-112 minarXiv:2607.10347express
Quantum System Confuses Blueprints, but Engineers Don't
Quantum devices are no longer lab curiosities. They are assembled, tuned, and repaired like ordinary hardware — except inside them, it's not just current but intricate tangles of particles that can exist in multiple states at once. Engineers draw schematics, programmers write code, physicists calculate effects.
Quantum Physics2026-07-071 minarXiv:2607.06071express
Quantum Mpemba effect: hot cools faster, but only near absolute zero
The Mpemba effect is a mystery where hot вода sometimes freezes faster than warm water. Usually this is attributed to how вода loses heat and энтропию (a measure of disorder). But in a glass of water, chaos prevents a precise model. Physicists built a quantum model: a particle in a well with two depressions separated by a barrier.
Galaxies2026-07-052 minarXiv:2607.04121
Triple Black Hole Waltz: How Chaos Spawns Mergers
At the heart of almost every galaxy slumbers a supermassive black hole — the invisible conductor of a stellar orchestra. When galaxies collide, their central monsters draw closer, entwining in a gravitational dance. Sometimes a third partner joins the duo, and then a triple waltz begins, its outcome unpredictable.
Hybrid Intelligence: Quantum Hearing Distinguishes Topological Phases
Once Richard Feynman saw in quantum systems a challenge for classical computers. Now we face the inverse problem: understanding what exactly the quantum processor has simulated. Among the states it births are veritable 'black boxes'—topological phases of matter.
General Relativity2026-06-182 minarXiv:2606.20975express
Quantum Computer Solves Einstein's Equations for the First Time
Strike a tuning fork with a mallet — it vibrates, and the sound gradually fades. A black hole behaves much the same way when disturbed: it emits gravitational waves — ripples in spacetime itself — and then settles down.
General Relativity2026-06-111 minarXiv:2606.14806express
Gravity: Classical or Quantum?
Gravity seems simple: it keeps us on the ground and makes planets orbit. But if it were classical (described by Einstein's equations as the curvature of spacetime, while all matter follows the quantum laws of the Standard Model) then an ordinary quantum bit (qubit) falling freely…
HEP Phenomenology2026-06-101 minarXiv:2606.12404express
How Neutrinos Get Entangled in Stellar Cores
In the scorching heart of a dying star, an invisible stream is born — a neutrino gas. The particles race through matter almost without stopping, but when their density is enormous, they start to feel each other. Old calculations described this as a jostle in a crowd: each shove changes direction, but no connection arises between passersby.
Quantum Physics2026-06-041 minarXiv:2606.06316express
Quantum sieve catches one-in-a-million glitches
Picking out a single faulty microchip from a million, without any clue what the fault looks like, is a classic needle-in-a-haystack problem. A classical computer would test each chip one by one.
Quantum Physics2026-06-011 minarXiv:2606.02715express
A Trap for 11,000 Atoms: A Step Towards a Quantum Computer
An invisible trap made of laser light held 11,000 atoms — a record for quantum engineering. Previously, physicists wrestled with a few dozen of these particles; now the count runs into the thousands. Each atom becomes a qubit — a quantum bit that is both zero and one at once, like a spinning coin balanced on its edge.
Quantum Physics2026-05-292 minarXiv:2605.31442express
Quantum Roulette with a Winning Ticket
Imagine a library where instead of books, you have every conceivable combination of a few dozen quantum particles. The number of combinations grows like a snowball: add one particle, and the volume doubles. For fifty particles, there are more shelves than atoms in the visible universe.
General Relativity2026-05-281 minarXiv:2605.30405express
Universe as a Precise Mechanism: No 'Boltzmann Brains'
An eternal Universe where the measure of disorder (энтропия) grows is, for most of its time, a homogeneous void. In it, complex structures occasionally assemble by chance, such as fleeting consciousnesses — ‘мозги Больцмана’.
Quantum Physics2026-05-221 minarXiv:2605.23584express
Neutrino flavor changes on schedule
Neutrinos are nearly elusive particles that permeate everything around us. In a dense cloud, such as during a star explosion, they begin to collectively change their type, or 'flavor.' This process is like a crowd of people synchronously changing the color of their clothes, but not all at once — rather in waves.
Machine Learning2026-05-201 minarXiv:2605.21164express
Quantum Assistant Detects Rare Frauds
In the ocean of bank transactions, fraud is rarer than neutron stars in space, just 0.1% of all operations. A conventional detector gets used to the clean flow and loses vigilance. Enter Q-SYNTH, a hybrid system with a quantum generator. It creates plausible fake transactions itself, drawing on scraps of real data.
Atomic Physics2026-05-201 minarXiv:2605.21250express
Ion Trap Mimics Processes in Living Cells
Energy transfer in photosynthesis is like a children's slide: it bends under the weight of one, reshaping the path for the next. That's what happens in a leaf: an excited molecule instantly reshapes the 'landscape' of its neighbors. Physicists reproduce this effect using ions suspended in a vacuum trap.
Quantum Physics2026-05-173 minarXiv:2605.17418express
The Platypus Paradox: When Two Channels Beat One
Two simultaneous interpreters sit in the same booth. The first translates from English into Russian but swallows half the words. The second goes from Russian into French, and also loses half. If you put them together, you'd expect a mess: the losses would add up, and only a quarter of the meaning would reach the listener. But what if they start correcting each other?
Quantum Physics2026-04-302 minarXiv:2605.00205express
Quantum and the Cell: Three Roads at the Crossroads
Three craftsmen work in the same workshop. The first tries to figure out whether tiny hourglasses are built into nature's own machinery. The second attaches a laser pointer to a microscope to see details invisible to the naked eye. The third, conversely, takes living threads and carefully weaves them into fragile quantum circuits.
Quantum Physics2026-04-291 minarXiv:2604.26813express
The Magic That Electrons Stole
Quantum computers promise to solve problems that regular computers can't. But where is the line? The authors of a new study stumbled upon a surprising case: electrons paired up behave like a well-behaved orchestra. Even if you add a bit of "magic"—a special quantum resource: their behavior remains predictable.
Mesoscale2026-04-211 minarXiv:2604.19304express
Magnetic Walls — The Key to Quantum Computers
Imagine a line of dominoes: when the first one falls, it pushes its neighbor, and a wave rushes down the chain. The boundary between fallen and standing dominoes is a perfect image of a magnetic wall. In microscopic magnetic films, these walls separate zones with different magnetizations.
Quantum Physics2026-04-182 minarXiv:2604.16953express
Body Heat as a Clue: A Quantum Look at Breast Cancer
The hot air above asphalt shimmers, betraying the heated surface. Medical thermography works in a similar way: the skin over a tumor is often slightly warmer than healthy skin — by just fractions of a degree. Computer programs try to catch this difference and determine whether it's dangerous.
Quantum Physics2026-04-141 minarXiv:2604.13176express
Quantum computer catches cosmic particles
Qubits in a superconducting quantum computer are like tightly stretched strings. When a particle from space or from a radioactive decay flies by, it strikes these strings and they start to vibrate. This vibration disrupts the fragile quantum states, and computations go awry.
Galaxies2026-04-132 minarXiv:2604.12053express
A Galaxy Loses Its Memory in the Blink of an Eye
Drop two identical pebbles from a mountain peak: one lands a centimeter to the left, and a minute later they end up in different valleys. A galaxy is the same mountain, only with billions of pebbles and a slope that stretches over millions of years. The authors of a new study simulated a disk of 40 million point-like stars and tested how quickly it forgets where it started.
Quantum Physics2026-04-081 minarXiv:2604.07452express
Neutrinos Get Entangled Like a Crowd in a Cramped Room
Inside an exploding star, neutrinos race so densely that they start to influence each other. Their quantum states become entangled, like threads in a tight ball where you can no longer tell which is which. Ordinary computers struggle with this task, as the number of possible states grows avalanche-like.
Quantum Physics2026-04-081 minarXiv:2604.07639express
Quantum Rainbow: How a Tiny Computer Sorts Mountains of Data
A classical computer sorts data like a person meticulously sifting through grains of sand of different colors. A quantum processor takes its cue from nature: just as a droplet of water splits sunlight into a rainbow, revealing all hues at once, this new algorithm instantly grasps the essence of vast information arrays.
Quantum Physics2026-04-071 minarXiv:2604.06322express
Quantum Computers Will Challenge Gravity
The biggest puzzle in physics is how to reconcile spacetime curvature with quantum mechanics. At the Planck length, billions of billions times smaller than an atom, the rules break down. This frontier was discovered by Max Planck.
Mesoscale2026-04-011 minarXiv:2604.01063express
18 Qubits on a Single Chip
Eighteen tiny cells line up in two rows on a piece of germanium. Each cell is a quantum dot — a trap for a single electron whose spin acts as a qubit. Previously, such systems could only be assembled in small numbers, but here we have an entire lattice working as a single ensemble.
General Relativity2026-04-011 minarXiv:2604.01283express
Quantum Brushstrokes on the Canvas of the Cosmos
It all started with tiny quantum flickers on the primal canvas. Inflation — an avalanche-like expansion proposed by Alan Guth — stretched those brushstrokes to the scale of galaxies.
Strongly Correlated2026-03-301 minarXiv:2603.28125express
Magnetic Monopoles on Quantum Ice
Magnetic monopoles are like halves of a magnet that cannot exist alone in ordinary materials. But in spin ice, they appear in pairs connected by an invisible thread — a Dirac string. Previously, such monopoles were only seen in artificial systems at room temperature, but their quantum motion remained a mystery.
Quantum Physics2026-03-301 minarXiv:2603.28627express
Quantum Abacus: Cracking Codes with 10,000 Atoms
Instead of millions of rigidly fixed particles — 10,000 atoms, working as beads on a quantum abacus. Each bead can be both zero and one at the same time. But the key is: if an error creeps into the calculation, the atoms can be physically moved: as if you could rearrange the abacus on the fly so that the glitch doesn't ruin the result.
Quantum Physics2026-03-201 minarXiv:2603.20372express
Quantum Physics2026-03-161 minarXiv:2603.15804express
Double Signal: Quantum Noise Retreats
A quantum bit (qubit) is like a barely discernible whisper in a hum of voices. A regular amplifier makes the whisper louder, but along with it, the hum as well, making it harder to hear the essence. Physicists have created a clever device that generates two identical signal-whispers at different frequencies — the original and its echo.
Quantum Physics2026-03-031 minarXiv:2603.03496express
Quantum Physics2026-02-251 minarXiv:2602.22211express
Iceberg Quantum Codes: How Errors Make Computers Smarter
Like an iceberg, the visible part of the code is the data, while beneath the surface lies a massive foundation of auxiliary particles. They quietly monitor noise and fix errors without touching the information. This approach squeezes many protected logical qubits into a modest number of physical ones. The experiment ran on a 98-ion processor inside an electric trap.
Chemical Physics2026-02-212 minarXiv:2602.18821express
The Quantum Kitchen of Water
A pot of water on the stove is just water, but inside each molecule, a continuous dance goes on. Hydrogen and oxygen atoms jitter, even at absolute zero, because that's how the quantum world works. These jitters change how much heat water stores and how it flows.