3 ms·
I would add one more to this, which I would argue is the main reason: (0) For a quantum algorithm/simulation to be classically verifiable, it needs additional
by qnleigh 2y ago
I would add one more to this, which I would argue is the main reason:
(0) For a quantum algorithm/simulation to be classically verifiable, it needs additional structure; something that leads to a structured, verifiable output despite the intermediate steps being intractable to simulate classically. That additional structure necessarily adds complexity beyond what can be run on current devices.
To pick an arbitrary example I'm familiar with, this paper (https://arxiv.org/abs/2104.00687 https://arxiv.org/abs/2104.00687) relies on the quantum computer implementing a certain cryptographic hash function. This alone makes the computation way more complex than what can be run on current hardware.