Quantum magic: What QC can and cannot do

Quantum computers are often hyped as the ultimate supercomputers that will eventually replace our current machines. In reality, they are highly specialized tools. They don’t process information faster in a traditional sense; rather, they process information differently, using the principles of quantum mechanics¹ (like superposition² and entanglement³⁴) to solve specific types of problems.

The gist is that quantum computers excel at solving certain complex quantum problems by utilizing vast amounts of entanglement. It is often assumed that any highly entangled problem of size $N$ will require an exponential amount of resources for a classical computer to solve. However, this is a major misconception. Some massively entangled systems can actually be simulated quite efficiently on standard classical machines.

Entanglement is a necessary ingredient, but it is not sufficient on its own. Ultimately, the true measure of what makes a problem fundamentally impossible for a classical computer—and where a quantum computer truly achieves its advantage—is a complex mathematical resource known in the field as magic.

So, what exactly is magic?

In quantum computing theory, magic (or a “magic state”) isn’t a mystical term; it’s a specific, mathematically measurable resource that defines how “non-classical” a quantum system is, typically quantified using a metric called Stabilizer Rényi Entropy⁵.

To get an intuitive sense of what magic is, it helps to understand what it is not. Magic is entirely independent of entanglement. People often assume that if a quantum system is highly entangled, it must be impossible for a classical computer to simulate. This is not true. For example, consider a giant GHZ (Greenberger–Horne–Zeilinger) state. A GHZ state connects many qubits so that they are maximally entangled (if you measure one, you instantly know the state of all the others). However, the mathematical description of this state is incredibly rigid and simple. Because of this simplicity, a standard classical computer can simulate a massive, highly entangled GHZ state with very little effort. It has maximum entanglement, but zero magic. A state only becomes classically hard to simulate when it is generated by a “universal” quantum circuit.

Classical computers can efficiently simulate basic quantum operations known as Clifford gates: $CNOT$ (controlled $X$ gate), $H$ (creates equal superpositions), and $S$ (rotates by 90 degrees) gates. The $S$ gate is (up to a global phase) a rotation by $90$ degrees around the $z$ axis repressented by $R_z(\pi/2)$. You can build highly entangled states using only Clifford gates, but a classical computer will always be able to keep up. To achieve true quantum advantage, you have to introduce a non-Clifford gate, such as the $T$ gate, which is (up to a global phase) $R_z(\pi/4)$, i.e., two $T$ gates make for an $S$ gate.

Adding a $T$ gate to the mix makes the circuit universal, allowing it to explore the full, complex computational space of quantum mechanics. The $T$ gate is what injects “magic” into the system. As you add more magic, the time and memory required for a classical computer to simulate the system increase exponentially. Therefore, a problem’s potential for true quantum advantage directly relies on how much of this “magic” is required to solve it⁶.

Because they rely on such specific mathematical conditions rather than brute processing power, quantum computers are highly specialized tools, not general-purpose replacements. With that in mind, here is a breakdown of where they truly shine and where they fall short.

What Quantum Computers ARE Good at

As today’s quantum hardware is still in its infancy, most systems are incredibly fragile and limited by systemic “noise” or “decoherence.” They typically require extreme cooling and total isolation, as even a stray cosmic ray or temperature shift can destroy the quantum state⁷. To overcome this fragility, researchers are actively developing Quantum Error Correction (QEC) to group volatile “physical qubits” into single, stable “logical qubits.”

These environmental limits are not strictly inherent; for instance, Nitrogen-Vacancy (NV) center quantum computers can operate at room temperature. However, current hardware constraints mean the following capabilities represent near-future potential rather than what you can flawlessly achieve on a physical machine today. The mathematics and algorithms behind them, however, are proven.

Essentially, any classical problem that can be efficiently formulated as a quantum problem will have some level of quantum advantage. Quantum computers excel at problems involving highly entangled states, linear formulations, and vast numbers of possibilities⁸.

• Simulating Nature & Material Science: Classical computers struggle to simulate even simple molecules accurately because the number of electron interactions creates a highly entangled problem requiring exponential resources. Quantum computers operate using the same quantum rules as nature—a concept first proposed by physicist Richard Feynman in 1981—making them theoretically perfect for simulating chemistry and physics⁹. This capability is expected to revolutionize how we discover life-saving drugs¹⁰, create better batteries, and develop stronger, lighter materials. For a practical look at how researchers are currently modelling condensed matter physics and bridging the gap between quantum algorithms and chemistry, check out our blog post.
• Factoring Large Numbers & Breaking Classical Encryption: Large-scale quantum computers will eventually be able to break standard RSA encryption (which protects much of the internet) because of their ability to find the prime factors of massive numbers exponentially faster than classical algorithms. This is done by finding periodicity (repeating patterns in data) via the Quantum Fourier Transform (QFT)¹¹, which is the mathematical engine behind the famous Shor’s Algorithm¹²¹³. Conversely, this same field of study is driving the creation of “quantum-safe” encryption methods that are theoretically unhackable¹⁴¹³.
• Linear Problems & The HHL Algorithm: Because the governing mathematics of quantum mechanics is strictly linear (quantum states act as vectors, and quantum gates act as matrices), quantum computers are exceptionally natural at solving classical linear algebra problems. The famous Harrow-Hassidim-Lloyd (HHL) algorithm proves that because quantum hardware natively “speaks” the language of linear algebra, it can solve massive, complex systems of linear equations exponentially faster than the best classical supercomputers¹⁵.
• Searching Data & Complex Optimization: Grover’s Algorithm¹⁶⁸¹⁷ provides a quadratic speed-up, allowing a quantum computer to search an unsorted database much faster than a classical computer (finding a target in 1,000 steps rather than 1 million). This type of quantum speed-up can also be applied to complex optimization problems, such as finding the absolute most efficient route for thousands of delivery trucks, optimizing financial portfolios, or mapping out complex manufacturing supply chains. For a concrete example of this in logistics, check out our recent blog post where we explore solving the Vehicle Routing Problem using quantum annealing.

What Quantum Computers ARE NOT Good at

A common misconception is that quantum computers will eventually be on our desks, running video games or web browsers at lightning speed. This is not the case.

• Everyday Computing Tasks: Quantum computers are terrible at running word processors, loading websites, or sending emails. For basic, sequential calculations and everyday software, your smartphone is infinitely more practical and efficient¹⁸ than a quantum computer.
• Replacing Classical Supercomputers: They aren’t just “faster classical computers.” In fact, a quantum computer cannot even operate on its own; it will always require a classical computer to act as its guide, compiling algorithms and orchestrating the exact sequence of physical gate operations. If a problem doesn’t require quantum mechanics, isn’t highly entangled, or doesn’t have a specific mathematical structure (like linearity) that a quantum algorithm can exploit, a quantum computer offers little to no advantage¹⁹.
• Big Data Storage: While it might seem like quantum computers would be revolutionary for storing massive databases—since superposition theoretically allows you to encode $2^N$ values using only $N$ qubits—the reality of quantum mechanics makes this highly inefficient. The fundamental bottleneck is retrieval. According to Holevo’s theorem, you can only reliably extract exactly $N$ classical bits of information from $N$ qubits. To extract the full $2^N$ encoded data, you would have to perform state tomography. Because a single measurement only yields partial information and immediately destroys the superposition, retrieving the full data requires you to flawlessly rebuild and measure the exact same quantum state countless times, making qubits completely impractical for standard big data storage.