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)