<p>Brakerski, Christiano, Mahadev, Vazirani, and Vidick propose a <a href="https://arxiv.org/abs/1804.00640" rel="nofollow noreferrer">scheme</a> for verifiable quantum computational supremacy based on a strengthening of trap-door claw-free functions (TCFs).</p>

<p>In the above scheme:</p>

<ul>
<li>Vicky the classical verifier provides a description of a pair of functions <span class="math-container">$f_0$</span> and <span class="math-container">$f_1$</span> to Peggy the quantum prover, while saving the trapdoor to <span class="math-container">$f_0$</span> and <span class="math-container">$f_1$</span>;</li>
<li>Peggy prepares, measures, and reports the results of a register in a quantum state to provide a <span class="math-container">$y$</span> such that <span class="math-container">$y=f_0(x_0)=f_1(x_1)$</span>, keeping a superposition of <span class="math-container">$\vert b\rangle\vert x_b\rangle$</span>;</li>
<li>Vicky asks Peggy to measure the superposition in either the computational basis to provide a bit <span class="math-container">$b$</span> and an <span class="math-container">$x_b$</span> such that <span class="math-container">$f_b(x_b)=y$</span>, or in the Hadamard basis to provide a string <span class="math-container">$d$</span> orthogonal to <span class="math-container">$x_0\oplus x_1$</span>; and</li>
<li>Based on Vicky's possession of the trapdoor, Vicky can validate results (she uses the trapdoor to deduce both <span class="math-container">$x_0$</span> and <span class="math-container">$x_1$</span> from <span class="math-container">$y$</span> and Peggy's response above).  </li>
</ul>

<p>Thus Peggy proves that she was able to execute a function in quantum superposition (or she has broken the security of the TCF).</p>

<p>The authors instantiate their TCFs with learning-with-errors (LWE), which is a leading candidate for post-quantum security.  That is, the functions they require Peggy to prepare and evaluate in superposition are associated with LWE.</p>

<p>My limited understanding is that the author's LWE scheme is out of reach of current and near-term noisy, intermediate-scale quantum computers.  The authors appear somewhat optimistic that about 50 bits of security may correspond to a machine with about 2000 or so qubits, or perhaps even 200-500 noisy qubits if they could optimize their LWE scheme.  </p>

<p>Nonetheless the scheme is interesting and I think close to the spirit of the question.  For example, in this scheme Peggy does not actually find the claw by herself but only provides a proof that she possessed <span class="math-container">$x_0$</span> and <span class="math-container">$x_1$</span> in superposition.</p>

CC BY-SA 4.0
2020-05-24T17:15:17.197Z
2020-05-28T01:03:03.847Z
2020-05-28T01:03:03.847Z
Mark S
<p>Upon more consideration and to expand more of the comments above, I believe that <em><strong>the full scope of the OP's question can be realized, if not now then at least in the near future</strong></em>, for example with a quantum computer having less than a couple hundred qubits and capable of reliably running a relatively shallow depth circuit.</p>
<p>That is, I think we can separate a certificate of quantumness between a quantum part <span class="math-container">$(y,d)$</span> sampled with a quantum computer, and a classical part <span class="math-container">$(x_1,x_2)$</span> found with (cryptocurrency) mining.  Start with the simple observation that for a random oracle <span class="math-container">$f(x)$</span> from <span class="math-container">$n$</span> bits to <span class="math-container">$n$</span> bits a quantum computer can find pairs <span class="math-container">$(y,d)$</span> such that for a large fraction there are preimages <span class="math-container">$(x_1,x_2)$</span> with:</p>
<p><span class="math-container">$$f(x_1)=f(x_2)=y,\tag 1$$</span></p>
<p>and further that:</p>
<p><span class="math-container">$$d\cdot (x_1\oplus x_2)=0.\tag 2$$</span></p>
<p>A classical computer cannot find the pair <span class="math-container">$(d,y)$</span> except by hunting for collisions.</p>
<p>For example a quantum computer (Peggy) can prepare <span class="math-container">$|x\rangle|f(x)\rangle$</span>, and can measure the second register <span class="math-container">$y=f(x)$</span> in the computational basis, while measuring first register <span class="math-container">$d$</span> in the Hadamard basis.  After Peggy broadcasts <span class="math-container">$(d,y)$</span>, miners (Vicky) can hunt for all the preimages to <span class="math-container">$y$</span>.  If there are two preimages <span class="math-container">$(x_1,x_2)$</span> that the miners find and broadcast, then all the clients on the network can easily verify both <span class="math-container">$(1)$</span> and <span class="math-container">$(2)$</span> above.  And, akin to the OP's suggestion, Peggy the quantum computer could offer a smart-contract as a way to motivate Vicky the miners to dedicate resources to finding such <span class="math-container">$(x_1,x_2)$</span> pairs.  She puts her money where her mouth in claiming quantum computational advantage.</p>
<p>The function <span class="math-container">$f(x)$</span> need not satisfy Simon's promise nor even be two-to-one; I had initially envisioned <span class="math-container">$f(x)$</span> to be the last <span class="math-container">$n$</span> bits of <code>SHA256</code>.  But <code>SHA256</code> is cost-prohibitive in the NISQ era, probably requiring a circuit depth of several hundred thousand thousand thereabouts.</p>
<p>I think, however, that any shallow Boolean function <span class="math-container">$f$</span> may have the desirable properties of being easy to implement on a quantum computer but being hard to classically invert.  I would guess that with maybe 150 qubits with all-to-all connectivity able to run a circuit of depth maybe 40-60 Boolean operations such as <span class="math-container">$\mathsf{CCNOT}$</span> or <span class="math-container">$\mathsf{CSWAP}$</span> would work.</p>

CC BY-SA 4.0
2023-03-29T18:32:30.510Z
2023-03-29T18:32:30.510Z
Mark S
<p><strong>Update:</strong> A slightly <a href="https://cstheory.stackexchange.com/questions/46202/are-there-problems-that-can-be-solved-in-time-2n-qc-with-q-qubits">different version of this question has been answered here</a>.</p>

<p>As far as I can see, a major issue with Google's recent quantum supremacy claim is that it is hard to verify the results.
If the quantum computer would be powerful enough to solve problems in NP (like factoring, using Shor's algorithm), it would be easy to verify the results, however, this computational power is not available yet.
As an intermediate step,</p>

<blockquote>
  <p>what could be a problem within reach of today's quantum computers whose output can be verified efficiently with a witness?</p>
</blockquote>

<p>Here <em>efficiently</em> need not stand for the problem itself being in NP, but rather it would be sufficient that the correctness of the solution is in NP.
For example, consider a satisfiability task whose literals are <span class="math-container">$x_i$</span>'s and <span class="math-container">$y_j$</span>'s.
If the quantum computer can produce all the <span class="math-container">$x_i$</span> that are part of a solution, then a witness for its correctness would be finding the <span class="math-container">$y_j$</span>'s that make <span class="math-container">$(x,y)$</span> into a solution.
The corresponding <span class="math-container">$y$</span> can be found with a classical algorithm, or set as a challenge, like in case of Bitcoin, to mint some quantum coin, with the computational power of all the miners looking for the witness.
In fact, miners can be also rewarded for finding another <span class="math-container">$(x',y')$</span> solution of the original problem, which would determine whether <span class="math-container">$x$</span> is useful or not.</p>

<p>So what could be such a problem?
Can Shor's algorithm or some other similar problem be broken into finding some <span class="math-container">$x$</span> with a quantum computer that can be extended into a witness with some (smaller) <span class="math-container">$y$</span>?</p>

CC BY-SA 4.0
2019-12-29T15:13:09.113Z
If a quantum computer output is verifiable in asymptotic polynomial time with classical computers, it is in NP (unless the verification algorithm is randomized, in which case it is in MA). But that's not what you should be asking.  All we care about is the finite case, not the asymptotic one.
Peter Shor 
CC BY-SA 4.0
2019-12-30T18:22:31.403Z
To expand on my previous comment, the asymptotic case is taken care of by factoring, as well as a number of other asymptotic quantum supremacy results. And it's quite possible there are problems in P which quantum computers can solve, but for which witnesses are too difficult to compute classically on today’s digital computers (although I have to admit I don't know any).
Peter Shor 
CC BY-SA 4.0
2019-12-30T19:58:30.137Z
@Peter My question meant exactly to be about the state-of-the-art quantum computers (around 53 qubits). Is there a verifiable problem whose solution they can enhance? For example, if I want to find a hidden 100-digit factor, could a 53-qubit quantum algorithm tell me fast that the 42nd digit is 3 with >20% probability? I would consider this to be a verifiable (through a further exponential amount of computation) quantum advantage.
domotorp
CC BY-SA 4.0
2020-01-02T01:48:27.770Z
As I was trying to explain in my previous comments, "exponential" has no real meaning when you're talking about a 53-qubit machine. Everything is a constant-time computation. The question is whether it's a constant that is practical on our current computers or not.
Peter Shor 
CC BY-SA 4.0
2022-09-26T13:37:55.887Z
@domotorp I think I was inspired by thinking about this to propose a very similar protocol on [Aaronson's blog](https://scottaaronson.blog/?p=6645). For a random two-to-one oracle $f(x)$, a certificate of quantumness is split between a quantum pair $(d,y)$ and a classical pair $(x_1,x_2)$, with $y=f(x_1)=f(x_2)$ and $d\cdot(x_1\oplus x_2)=0$ - with the classical pair being found by mining rigs and a smart contract...(cont.)
Mark S
CC BY-SA 4.0
2022-09-26T13:40:58.067Z
@domotorp With Sam Jacques we also worked out some other details on [QCSE](https://quantumcomputing.stackexchange.com/questions/27963/can-we-use-cryptocurrency-mining-to-verify-claims-of-quantum-advantage) - in particular, Sam pointed out that a 2-to-1 function may be amenable to a birthday attack, but a generic random oracle behaves according to the Poisson distribution and this can aid in verification.  I initially proposed that $f(x)$ be the last $m$ qubits of `SHA256`, but that's much too difficult to implement now. Any other random 2-1 function may suffice, though.
Mark S
<cc.complexity-theory><quantum-computing><ce.computational-finance>
Witness verifiable quantum advantage
domotorp
# Witness verifiable quantum advantage

(Asked by: username_0 on 2019-12-29)

**Update:** A slightly [different version of this question has been answered here](https://cstheory.stackexchange.com/questions/46202/are-there-problems-that-can-be-solved-in-time-2n-qc-with-q-qubits).

As far as I can see, a major issue with Google's recent quantum supremacy claim is that it is hard to verify the results.
If the quantum computer would be powerful enough to solve problems in NP (like factoring, using Shor's algorithm), it would be easy to verify the results, however, this computational power is not available yet.
As an intermediate step,

> what could be a problem within reach of today's quantum computers whose output can be verified efficiently with a witness?

Here *efficiently* need not stand for the problem itself being in NP, but rather it would be sufficient that the correctness of the solution is in NP.
For example, consider a satisfiability task whose literals are $x\_i$'s and $y\_j$'s.
If the quantum computer can produce all the $x\_i$ that are part of a solution, then a witness for its correctness would be finding the $y\_j$'s that make $(x,y)$ into a solution.
The corresponding $y$ can be found with a classical algorithm, or set as a challenge, like in case of Bitcoin, to mint some quantum coin, with the computational power of all the miners looking for the witness.
In fact, miners can be also rewarded for finding another $(x',y')$ solution of the original problem, which would determine whether $x$ is useful or not.

So what could be such a problem?
Can Shor's algorithm or some other similar problem be broken into finding some $x$ with a quantum computer that can be extended into a witness with some (smaller) $y$?

**Tags:** cc.complexity-theory, quantum-computing, ce.computational-finance

> **Comments:**
> **username_1**: If a quantum computer output is verifiable in asymptotic polynomial time with classical computers, it is in NP (unless the verification algorithm is randomized, in which case it is in MA). But that's not what you should be asking.  All we care about is the finite case, not the asymptotic one.  
> **username_1**: To expand on my previous comment, the asymptotic case is taken care of by factoring, as well as a number of other asymptotic quantum supremacy results. And it's quite possible there are problems in P which quantum computers can solve, but for which witnesses are too difficult to compute classically on today’s digital computers (although I have to admit I don't know any).  
> **username_0**: @Peter My question meant exactly to be about the state-of-the-art quantum computers (around 53 qubits). Is there a verifiable problem whose solution they can enhance? For example, if I want to find a hidden 100-digit factor, could a 53-qubit quantum algorithm tell me fast that the 42nd digit is 3 with >20% probability? I would consider this to be a verifiable (through a further exponential amount of computation) quantum advantage.  
> **username_1**: As I was trying to explain in my previous comments, "exponential" has no real meaning when you're talking about a 53-qubit machine. Everything is a constant-time computation. The question is whether it's a constant that is practical on our current computers or not.  
> **username_2**: @username_0 I think I was inspired by thinking about this to propose a very similar protocol on [Aaronson's blog](https://scottaaronson.blog/?p=6645). For a random two-to-one oracle $f(x)$, a certificate of quantumness is split between a quantum pair $(d,y)$ and a classical pair $(x_1,x_2)$, with $y=f(x_1)=f(x_2)$ and $d\cdot(x_1\oplus x_2)=0$ - with the classical pair being found by mining rigs and a smart contract...(cont.)  
> **username_2**: @username_0 With Sam Jacques we also worked out some other details on [QCSE](https://quantumcomputing.stackexchange.com/questions/27963/can-we-use-cryptocurrency-mining-to-verify-claims-of-quantum-advantage) - in particular, Sam pointed out that a 2-to-1 function may be amenable to a birthday attack, but a generic random oracle behaves according to the Poisson distribution and this can aid in verification.  I initially proposed that $f(x)$ be the last $m$ qubits of `SHA256`, but that's much too difficult to implement now. Any other random 2-1 function may suffice, though.  

---

## 2 answers

### Answer by username_2 on 2020-05-24. Score: 3 | Accepted answer

Brakerski, Christiano, Mahadev, Vazirani, and Vidick propose a [scheme](https://arxiv.org/abs/1804.00640) for verifiable quantum computational supremacy based on a strengthening of trap-door claw-free functions (TCFs).

In the above scheme:

* Vicky the classical verifier provides a description of a pair of functions $f\_0$ and $f\_1$ to Peggy the quantum prover, while saving the trapdoor to $f\_0$ and $f\_1$;
* Peggy prepares, measures, and reports the results of a register in a quantum state to provide a $y$ such that $y=f\_0(x\_0)=f\_1(x\_1)$, keeping a superposition of $\vert b\rangle\vert x\_b\rangle$;
* Vicky asks Peggy to measure the superposition in either the computational basis to provide a bit $b$ and an $x\_b$ such that $f\_b(x\_b)=y$, or in the Hadamard basis to provide a string $d$ orthogonal to $x\_0\oplus x\_1$; and
* Based on Vicky's possession of the trapdoor, Vicky can validate results (she uses the trapdoor to deduce both $x\_0$ and $x\_1$ from $y$ and Peggy's response above).

Thus Peggy proves that she was able to execute a function in quantum superposition (or she has broken the security of the TCF).

The authors instantiate their TCFs with learning-with-errors (LWE), which is a leading candidate for post-quantum security. That is, the functions they require Peggy to prepare and evaluate in superposition are associated with LWE.

My limited understanding is that the author's LWE scheme is out of reach of current and near-term noisy, intermediate-scale quantum computers. The authors appear somewhat optimistic that about 50 bits of security may correspond to a machine with about 2000 or so qubits, or perhaps even 200-500 noisy qubits if they could optimize their LWE scheme.

Nonetheless the scheme is interesting and I think close to the spirit of the question. For example, in this scheme Peggy does not actually find the claw by herself but only provides a proof that she possessed $x\_0$ and $x\_1$ in superposition.


---

### Answer by username_2 on 2023-03-29. Score: 1

Upon more consideration and to expand more of the comments above, I believe that ***the full scope of the OP's question can be realized, if not now then at least in the near future***, for example with a quantum computer having less than a couple hundred qubits and capable of reliably running a relatively shallow depth circuit.

That is, I think we can separate a certificate of quantumness between a quantum part $(y,d)$ sampled with a quantum computer, and a classical part $(x\_1,x\_2)$ found with (cryptocurrency) mining. Start with the simple observation that for a random oracle $f(x)$ from $n$ bits to $n$ bits a quantum computer can find pairs $(y,d)$ such that for a large fraction there are preimages $(x\_1,x\_2)$ with:

$$f(x\_1)=f(x\_2)=y,\tag 1$$

and further that:

$$d\cdot (x\_1\oplus x\_2)=0.\tag 2$$

A classical computer cannot find the pair $(d,y)$ except by hunting for collisions.

For example a quantum computer (Peggy) can prepare $|x\rangle|f(x)\rangle$, and can measure the second register $y=f(x)$ in the computational basis, while measuring first register $d$ in the Hadamard basis. After Peggy broadcasts $(d,y)$, miners (Vicky) can hunt for all the preimages to $y$. If there are two preimages $(x\_1,x\_2)$ that the miners find and broadcast, then all the clients on the network can easily verify both $(1)$ and $(2)$ above. And, akin to the OP's suggestion, Peggy the quantum computer could offer a smart-contract as a way to motivate Vicky the miners to dedicate resources to finding such $(x\_1,x\_2)$ pairs. She puts her money where her mouth in claiming quantum computational advantage.

The function $f(x)$ need not satisfy Simon's promise nor even be two-to-one; I had initially envisioned $f(x)$ to be the last $n$ bits of `SHA256`. But `SHA256` is cost-prohibitive in the NISQ era, probably requiring a circuit depth of several hundred thousand thousand thereabouts.

I think, however, that any shallow Boolean function $f$ may have the desirable properties of being easy to implement on a quantum computer but being hard to classically invert. I would guess that with maybe 150 qubits with all-to-all connectivity able to run a circuit of depth maybe 40-60 Boolean operations such as $\mathsf{CCNOT}$ or $\mathsf{CSWAP}$ would work.


---

