concept

computational cost

The resources (time, memory) required to perform a computation or simulation.
46 related articles

Description

Computational cost refers to the resources—such as time, memory, and energy—required to perform a computation or simulation. In physics and computer science, it is a critical measure of feasibility: a problem may be theoretically solvable but practically impossible if the cost grows too quickly with size. This concept is central to understanding why quantum computers are needed for certain tasks, as classical simulations of quantum systems often have exponential computational cost.

History

The formal study of computational cost began in the 1960s with the work of computer scientists like Juris Hartmanis and Richard Stearns, who introduced complexity classes. The idea of using computational cost to argue for quantum computers was popularized by Feynman in the early 1980s.

How it works

Computational cost is often analyzed using complexity theory, which classifies problems by how the required resources scale with input size. For example, a problem that takes polynomial time (like sorting a list) is considered tractable, while one that takes exponential time (like simulating a large quantum system classically) becomes intractable for even moderate sizes. Quantum computers aim to reduce this cost for specific problems by exploiting superposition and entanglement.

In practice

Computational cost analysis guides the design of algorithms and hardware, from optimizing classical simulations in materials science to determining which problems are worth pursuing on quantum computers, such as simulating molecular dynamics for drug discovery.

Fun fact

The famous 'traveling salesman problem'—finding the shortest route through many cities—has a computational cost that grows factorially, meaning even with all the world's computers, it remains unsolvable for just a few hundred cities.

Concept graph →

Related articles · 46

Quantum Physics2026-08-092 minarXiv:2608.10027express
Thermal Computers: The Price of Precision
A conventional computer computes by shuttling electric charges along wires. But can you compute with heat? A network of pipes carrying hot and cold water can perform simple logic operations if the pipes are connected in the right order.
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.
General Relativity2026-07-292 minarXiv:2607.27344express
A Universe Without Clocks: Time from Geometry
Clocks in the Universe are tricky things. Usually, in calculations of the birth of the world, a special scalar field plays the role of a clock — something like an invisible fluid filling all of space. It ticks, and physicists watch how the world changes relative to that ticking. But these clocks are man-made, introduced for convenience. The authors of the new work took a different path.
cs.CY2026-07-151 minarXiv:2607.14353express
Why artificial intelligence repeats old mistakes
Technological disasters like Chernobyl rarely strike without warning. They gestate for years: organizations ignore warnings, their complexity mirroring the rise of entropy — a measure of relentless chaos that builds up unnoticed until it avalanches.
Quantum Physics2026-07-072 minarXiv:2607.06404express
Quantum Code, Carbon Copy
A quantum computer is like an orchestra without a conductor: each qubit is a musician, and the slightest slip throws off the entire symphony. To keep the music from turning into cacophony, quantum error-correcting codes were invented.
cs.DB2026-06-303 minarXiv:2607.00254
Quantum Physics2026-06-192 minarXiv:2606.21664express
Quantum Games Crack a Classic Math Theorem
In 1953, mathematician Alexander Grothendieck proved a theorem that became a cornerstone in the theory of tensor products. It states that for ordinary function spaces, two natural norms, the projective and the injective, are equivalent up to a universal constant. In other words, two ways of measuring the 'size' of combinations of vectors give similar results.
Wet Water and a Thinking Processor
In the 1990s, philosopher John Searle devised a thought experiment: a person sits in a room and, without knowing Chinese, follows instructions to produce correct answers in Chinese. From the outside, it seems they understand the language, but inside, it's just mechanical rule-following.
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.
Strongly Correlated2026-05-261 minarXiv:2605.27484express
How magnets change the nature of a quantum transition
A long chain of atoms, each a tiny magnet. They talk to each other and to a common field, like musicians in an orchestra who hear both the conductor and their neighbors. When the external field changes, the orchestra either plays out of sync or all instruments come in together: that's a quantum phase transition.
Quantum Physics2026-05-241 minarXiv:2605.25302express
Causality: Why It Can't Be Measured
The quantum world plays a strange game with causality. If in everyday life salt is always added to soup before serving, here the ingredients end up in the bowl at the same time, and the chef doesn't remember the order. Physicists asked: can we measure this 'recipe'? The answer is no.
Quantum Physics2026-05-082 minarXiv:2605.08351express
Quantum Events Without a Script
In the kitchen, the sequence of actions is strictly dictated by the recipe: first chop, then fry, and nothing else. In quantum physics, the role of the recipe is played by causality — one event causes another, and they cannot be swapped. But in recent years, theorists have devised clever scenarios where the order of events seems to 'hang' in uncertainty.
Machine Learning2026-05-061 minarXiv:2605.08212express
AI assistant tackles cosmology's trickiest math
The Universe's expansion is accelerating, and maybe gravity doesn't work the way we think. Physicists come up with alternative theories, but to test them, they need to calculate how ripples after the Big Bang grew into galaxies. Such calculations involve long equations with hundreds of terms, where it's easy to get lost.
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-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.
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-261 minarXiv:2603.25519express
Quantum Bitcoin Mining: Why Stellar Energy Won't Help
Bitcoin mining is like a lottery: miners sift through billions of numbers to find one lucky winner. A regular computer does this blindly, burning electricity. A quantum computer could sort through possibilities faster, like finding a needle in a haystack by shaking the whole stack at once. The authors of a new study calculated what such a quantum "shaker" would actually cost.
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.
Statistical Mech2026-02-162 minarXiv:2602.15185express
Complexity on the Edge of Order and Chaos
A magnetic film divided into tiny arrow-shaped cells behaves like a crowd in a square. While it's cold, all arrows point in the same direction — perfect order. Heat the film, and the arrows start darting around like pedestrians who have lost their purpose. Somewhere between these extremes, there is a moment when the system stops being uniform but hasn't yet dissolved into random noise.
Quantum Physics2026-02-061 minarXiv:2602.06544express
Light Learns to Count
Light races through a maze of mirrors and beam splitters, but at the end of its journey, it doesn't just flash on a detector: it transforms itself. In the new photonic computer, nonlinear modules have been added to the familiar linear circuits, and now light can perform any quantum operation, not just a subset.
HEP Theory2026-02-042 minarXiv:2602.04949express
Complexity on Graphs: How Quantum Walks Speed Up Time
A quantum walk is like a drunk person who turns randomly at every intersection. Except instead of streets, there are graph nodes, and instead of steps, there are quantum transitions. Scientists have discovered that such a walk has a hidden measure — Krylov complexity.
Quantum Physics2026-01-281 minarXiv:2601.20818express
Quantum Computers Learned to Repair Themselves
Quantum computers have gained a built-in self-repair mechanism. The new two-dimensional scheme works like living tissue: each qubit-cell interacts with neighbors by local rules, automatically suppressing random disorder — entropy. Unlike previous methods, it doesn't require constant measurements, which themselves generate errors.
Quantum Physics2026-01-242 minarXiv:2601.17580express
Quantum Computer Errors Learn to Fix Themselves
A quantum computer is like an orchestra where each musician plays their own part but sometimes hits a wrong note. To keep the music from turning into cacophony, you need a conductor who corrects mistakes in time. In quantum computing, the role of the conductor is played by error-correcting codes.
Quantum Physics2026-01-121 minarXiv:2601.08068express
Quantum computers save not just time, but also energy
When making popcorn, a microwave uses electricity only to heat the kernels. A gas stove heats the entire burner and the air around it. The same difference applies between a photonic quantum chip and a classical supercomputer when solving a problem devised by Scott Aaronson.
Optics2026-01-041 minarXiv:2601.01399express
Light Computes in Four Dimensions
A conventional computer sees the world flat: numbers are just points on a line. But a color image or a 3D scene demands more — four numbers that describe both position and rotation. Such quadruples are called quaternions, and until now electronics handled them clumsily, breaking them apart and reassembling them. The new chip changes the approach.
Quantum Physics2025-12-171 minarXiv:2512.15001express
Quantum Cold: How Wires Don't Get in the Way of Computing
An orchestra plays inside a giant refrigerator. The musicians are qubits, the elementary cells of a quantum computer. To play in harmony, they need silence: thermal noise drowns out the melody. That's why the heart of a quantum processor is cooled to nearly absolute zero — minus 273 degrees Celsius.
Quantum Physics2025-12-161 minarXiv:2512.14842express
Noise Helps Quantum Computers
To quickly dissolve sugar, you don't need to stir carefully — just shake the glass. A similar principle works in quantum systems: noise, usually considered a disturbance, speeds up the transition to a thermal state.
Quantum Physics2025-12-151 minarXiv:2512.13908express
Magic on a Chip: Growing Quantum States
Quantum computers require magical states — special helper particles for error-free operation. Previously, they were obtained through repeated purification, akin to endless distillation of alcohol: each step added энтропию (disorder), like weeds in a garden, and consumed resources.
Quantum Physics2025-10-301 minarXiv:2510.26547express
Quantum Leap: A Day Instead of 22 Years
Turning CO₂ into fuel is like finding the one perfect way to pack billions of items into a suitcase. A classical computer tries options one after another, taking decades, while a quantum computer sees all combinations at once.
Quantum Physics2025-10-291 minarXiv:2510.25838express
Quantum Chip Outperforms Supercomputers: Two Hours vs. Years
The task resembles a giant maze with a single exit among billions of dead ends. A conventional computer checks each corridor step by step — taking centuries. A quantum processor launches a wave that seeps through all paths at once. The correct route echoes back, amplifying, and the answer is found in hours. That’s exactly how the “peak” circuits worked in the new experiment.
Quantum Climber: Leaping Across Optimization Canyons
Three thousand meters above sea level, a sheer cliff face. A classical climber picks a single route and crawls up step by step, often getting stuck in a local minimum: a small niche with no upward path. A quantum climber acts differently: it can leap across a canyon and land in a neighboring energy basin where the route is better.
Bicycle Architecture: A Quantum Computer from Modules
A quantum computer is like an orchestra: each musician plays their part, but the slightest false note ruins the symphony. The physical qubits it is built from are noisy and error-prone. To protect computations, they are combined into logical qubits using quantum error correction.
Non-Hermitian Gates: The Price of Imaginary Speed-Up
In 2019, a group of theorists asked a simple question: what would happen if you embedded a single irreversible element into an ordinary quantum computer, a gate that slightly "eats" probability? The answer was devastating. Any such gate, no matter how weak, instantly turns the machine into a device capable of solving problems in the class PostBQP = PP.
Memory in Optomechanics: A Laser Conductor Teaches Light and Sound to Remember
In a dark room, a resonator catches light the way a spiderweb catches dew drops. A laser pulse bursts in, and the mechanical membrane starts to vibrate in sync, leaving a trace in the very fabric of the system. That is how memory is born: not in a silicon cell, but in the dance of photons and phonons.
Light in a Cryostat: How Imperfect Converters Build Quantum Bridges
A superconducting quantum processor is like a microscopic metropolis locked in a cryogenic fridge: streets of superconducting lines, blocks of qubits. Each resident demands silence and cold, but expanding the city inside a single cryostat is like stacking skyscrapers in a cramped courtyard — wires heat the environment, noise builds up, coherence threatens to collapse.
A Quantum Sieve for the Power Grid
Every day, the power grid faces a puzzle: which power plants should be switched on to reliably meet demand without breaking the bank? For 15 generators and 24 hours, the number of possible schedules exceeds 2.3×$$10^{108}$$, more than the number of atoms in the visible universe. No classical supercomputer can sift through all of them, so dispatchers settle for a compromise.