Is there a (natural) formalism that neatly and insightfully includes classical and quantum computation?

I have a mostly sound basis in quantum mechanics (as a physics grad), and a much less sound but still non-zero understanding of the foundations of computation - Turing machines and transition functions, and something something lambda calculus. While the maths of each doesn't seem too bad, they're pretty different from each other, with the smooth vector spaces, unitary operators, and projections of the quantum world seeming to have little in common with the chunky discrete bits and gates of classical computers beyond analogy.

So is there some common ground between them, a maximal mathematical core $x$ so $x + y = $ classical computation and $x + z = $ quantum computation?

  • 1
    $\begingroup$ Classical computation is a subset of quantum computation. By the time you're done using QM to express quantum computation, the formalism is perfectly capable to express classical computation. For the details, see any introductory quantum-computing textbook $-$ the usual go-to is Nielsen & Chuang, but there are other good ones. $\endgroup$ – Emilio Pisanty Dec 10 '19 at 10:05
  • $\begingroup$ I've read a smattering of Nielsen & Chuang for other reasons, and in retrospect, yeah, I guess I can see how that would work. It still seems a bit unsatisfying though for reasons that are a bit tricky to explain. I guess it's that embedding classical computation in quantum stuff feels kinda clunky and messy - classical non-reversible gates seem very neat and natural, but become awkward in the quantum formalism, and the whole vector space structure becomes pointless, moot (especially the complex structure), which is at odds with the internal purity of classical computation. $\endgroup$ – user6873235 Dec 10 '19 at 10:24

Classical computation is a subset of quantum computation. To see it, just consider circuits in which all gates and operations are permutation matrices, the inputs are product states of the type $|q_1,...,q_n\rangle$ with $q_i\in\{0,1\}$, and the measurements are in the computational basis. You then get back a deterministic device that can only perform classical reversible computation. Just stop looking at some of the outputs and you can perform arbitrary logic gates.

You just don't hear about it very often in the context of quantum computation because this is exactly the kind of thing you want to avoid: quantum computers are useless in the regime in which classical devices can perform the same things.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.