5
$\begingroup$

Recent quantum supremacy claims rely, among other things, on extrapolation, which motivates the question in the title, where the word "adversarial" is added to exclude such extrapolation-based quantum supremacy claims.

To clarify the exact meaning of the question imagine that we are looking for a benchmark "Bench" useful in the following scenario. Bob (who does not have access to a quantum computer) wants to verify the Eve's claim that she has a moderately-powerful quantum computer. They follow the following generic protocol:

  1. Bob: what is your score on Bench?
  2. Eve: $N$.
  3. Bob and Eve exchange messages following the Bench protocol, e.g. Bob can send challenges to Eve, and Eve should then send responses to those challenges.
  4. Following the protocol Bench, Bob reaches the conclusion on whether Eve has passed.

If Eve indeed has the powerful quantum computer, she should be able to pass this test with high probability (aka sensitivity) and if she does not, she should not be able to pass it with "only" using a few powerful classical supercomputers / clusters with non-negligible probability $= 1 -$specificity for sufficiently large $N$. Note that specific values of sensitivity and specificity are not important, since if one has a benchmark with sensitivity and specificity of $2/3$, one can repeat it e.g. 193 times and apply majority voting to get sensitivity and specificity of $99.9999\%$.

Architecture-independent means that the benchmark is useful for Eve's claim for a wide range of architectures Eve could use. Finally, by "practical" in the question I mean that the benchmark should be useful for near-term quantum computers. For example, one could use elliptic curve discrete logarithm problem as a benchmark, but it seems that this would require a quantum circuit depth of the order of $10^{10}$ to beat a classical supercomputer, thus would not be applicable to near-term quantum computers.

Recently IBM popularized quantum volume as a benchmark, which, similarly to Sycamore quantum supremacy claim, relies on sampling of the output distribution of a pseudo-random quantum circuit. However, it seems that these benchmarks all rely on a classical simulator or extrapolation (digital error model), neither of which satisfy the premise of this question:

  • E.g. if Eve claims log quantum volume large enough to show quantum supremacy (e.g. 100), then it is not clear how would we verify that, since the verifications of sampling-based tests above rely on our ability to compute the probabilities of the outputs via simulation of a quantum circuit on a classical hardware.
  • If Eve claims smaller log quantum volume (e.g. 42), for which the circuit can be simulated on classical hardware, nothing prevents Eve to simulate it herself without having access to a quantum computer.
  • Finally, if Eve's argument relies on extrapolation, nothing prevents her from using classical simulation for small circuit depths (which she can simulate and Bob can verify) and picking random outputs for larger ones (which Bob can't verify).

Similarly, "Advanced quantum supremacy using a hybrid algorithmfor linear systems of equations" does not seem to be the answer, since it seems to rely on the classical simulation to verify the results of the quantum computation.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.