Login
You're viewing the functional.cafe public feed.
  • Nov 18, 2026, 11:55 PM

    @dalias @alcinnz @kevingranade

    > and in my somewhat educated opinion, impossible

    From someone who worked in QC for twenty years, and who invented some of the core things that an eventual QC would need, a universe in which QC is impossible would look very different from what we currently understand the universe to look like. That's not to say that QC is absolutely possible but it would in and of itself upend much of current understanding about physics were it to turn out that QC is impossible.

    💬 2🔄 1⭐ 0

Replies

  • Nov 18, 2026, 11:57 PM

    @dalias @alcinnz @kevingranade Anyway, quantum computers are provably computers in the sense of the *weak* Church–Turing thesis (that is, in terms of computability), but aren't identical to classical computers in the sense of the *strong* Church–Turing thesis (that is, in terms of complexity).

    💬 1🔄 1⭐ 0
  • Nov 19, 2026, 12:17 AM

    @xgranade @alcinnz @kevingranade What I mean is that a QC does something different than the Church-Turing sense of computation. It does not answer a rigorous logical yes/no condition, accept/reject candidate members of a language, etc. Its results are qubits that need to be measured. This is a very different sense of computation.

    💬 3🔄 1⭐ 0
  • 💬 0🔄 0⭐ 0
  • Nov 19, 2026, 12:24 AM

    @xgranade @alcinnz @kevingranade In some sense real physical computers are like this too. They are subject, albeit with extremely low probability, to flipped bits from existing in a physical reality, on top of having some degree of finitude. But at least in an idealized form they are equivalent. I don't see any way a QC is equivalent except possibly in a limit as you approach infinitely many measurements. OTOH a QC is much better at other things.

    💬 0🔄 1⭐ 0
  • 💬 0🔄 0⭐ 0
  • 💬 0🔄 1⭐ 0