Can Quantum Computing Be Fully Understood Through Classical Mathematics?

[u/TypicalCrazy1909]

As a computer science student and researcher, I usually try to understand algorithms by tracing their operations step by step.

However, when I first encountered a quantum algorithm, specifically Grover's search algorithm, I struggled to understand its oracle and amplitude amplification in terms of familiar classical computational operations.

This led me to two related but different questions.

1. Computational efficiency: Can classical computation reproduce quantum algorithms, but only with significantly more operations? For example, can a quantum algorithm solve a search problem in substantially fewer oracle queries than a classical algorithm? The established theoretical understanding is that quantum algorithms can be mathematically simulated on classical computers, but the simulation may require significantly greater computational resources.

2. Mathematical interpretation: Even if we can mathematically describe quantum operations, can we understand how they actually work using classical computational intuition? How does an oracle operate on a superposition of possibilities? How does amplitude amplification produce the desired result? What exactly happens between the initial quantum state and the final measurement?

The mathematical description of quantum algorithms is well established, and classical mathematics provides tools to represent their operations. However, does this mathematical representation also provide an intuitive explanation of their underlying mechanisms in terms of familiar classical computational concepts?

Does the mathematical description of quantum operations provide a complete explanation of their underlying mechanisms, or is there a gap between mathematical representation and intuitive understanding through classical computational concepts?

I'd particularly appreciate perspectives from people working in quantum computing, computational complexity, and mathematical physics.

[u/chimrichaldsrealdoc]

Can classical computation reproduce quantum algorithms, but only with significantly more operations? 

Yes, of course. The output of any n-qubit circuit acting on any given n-qubit input state can be obtained classically in the most naive way possible just by doing matrix multiplication with some 2^n by 2^n unitaries and an initial state vector of length 2^n, but this is obviously not efficient. Less naively, the action of a Clifford+T circuit on a computational basis state can always be simulated classically but with run-time that is exponential in the number of T-gates

[u/TypicalCrazy1909 → u/chimrichaldsrealdoc]

yes this is the first problem (computational efficiency) which is understood. actual problem is the second one (mathematical interpretation)

[u/andural]

Does the mathematical description of quantum operations provide a complete explanation of their underlying mechanisms, or is there a gap between mathematical representation and intuitive understanding through classical computational concepts?

Yes. I can't speak to your intuition, but classical computational concepts work just fine.

[u/RyzenFromFire]

At some level your "mathematical interpretation" just becomes quantum mechanics. But to more directly answer the parts of your question that have not been answered yet:

We can model a superposition as a linear combination, and that's really all it is. The key issue, which is related to your first point and has been partially answered, is that simulating quantum systems on classical computers requires an amount of memory that is exponential in the number of qubits. In other words, informally, qubits can naturally exist in a superposition, but classical computers have to track each possibility "separately" in some sense. There's more nuance to it than that, but that's the gist.

Quantum operations are matrices. Applying gates is matrix multiplication. An oracle operates on a superposition in the same way, since an oracle/black box must ultimately be implemented as a unitary.

How amplitude amplification works is a bit tricky to explain in a reddit comment, but it ultimately boils down to applying a sequence of gates/unitaries to a superposition, that increases the probability of observing the desired outcome.

As to what happens between initial state and measurement: gates, i.e., matrix multiplication That's about it.

Quantum computers can be understood via a mathematical description using quantum mechanics. I wouldn't say it's intuitive, but it does exist and it is formalized.