5
$\begingroup$

Proposed experiments in achieving quantum supremacy, such as with BosonSampling or using random circuits, have been described as using a (not necessarily Turing complete) quantum computer to perform some sampling problem.

An example would be to sample the distribution of, say, $72$ qubits after application of, say, $1000$ random $2$-qubit gates.

Starting from the all-zeroes ket $\vert 000\cdots\rangle$ on $n$ qubits, a quantum computer would randomly draw from the output distribution after the application of some reasonably-sized unitary $U\vert 000\cdots\rangle$ (of, say, $m=O(n^2)$ gates).

Classically it is very unlikely that one could draw from the same distribution. It may take time $O(\exp(m\times n))$ to draw from this distribution

Because such sampling problems are not likely to be in $\mathcal{NP}$, approaches to validation of quantum supremacy experiments are being researched.

The HOG problem - heavy output generation - has been proposed as a test to validate quantum supremacy. Apparently the HOG test can be performed in time $O(\exp(n))$, which is much better than $O(\exp(m))$, and may be feasible for supercomputers.

But what, exactly, is this test? After a random unitary acts on the all-zeroes ket, the coefficients should be pointing in all different ways asunder - like a Brownian walk. The vast majority of outputs should have a low probability of occurrence, and would never be sampled (even if there are a large number of bases having a low probability $p_\epsilon$ of occurrence, if $p_\epsilon$ is small enough then no .)

How does the HOG test work? Is my understanding close to correct?

EDIT

Some links on the characterization of sampling problems:

Aaronson - "Aspects of Certified Randomness from Quantum Supremacy" Powerpoint

Bouland, Fefferman, Nirkhe, Vazirani - "Quantum Supremacy and the Complexity of Random Circuit Sampling" - arxiv

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
6
$\begingroup$

There are a couple variants of the HOG test.

"Old HOG" computed the proportion of unique samples whose probability is larger than the median probability of the distribution. It then compares that proportion to a threshold, e.g. 2/3. If you have enough larger-than-median outputs, you pass the test.

"New HOG" instead computes the mean of the probabilities of the unique samples. Again you pick some threshold that this mean must exceed in order to pass the test.

There's also "cross entropy fidelity (XEB)", which computes the mean of the logarithms of the probabilities.

The basic idea behind all these quantities is that a random quantum circuit will have a distribution of probabilities known as a Porter Thomas distribution, and this distribution has known medians and means and so forth which are different from the ones you'd get in a uniform distribution. This allows you to determine whether you're seeing larger or smaller probability samples as often as should be the case, which allows you to define a statistical test that is difficult to pass without the ability to sample from the correct distribution.

Improve this answer
$\endgroup$
3
  • $\begingroup$ If a RCS outputs various $n$-qubit vectors $x_1,x_2,\cdots x_k$ must we calculate the probability that each of $x_1,x_2,\cdots, x_k$ will be generated? Does this classically take time $O(\exp(n))$? $\endgroup$
    – Mark Spinelli
    Commented May 23, 2019 at 22:25
  • 1
    $\begingroup$ @MarkS That's correct. These metrics are very expensive to compute for large random circuits. $\endgroup$
    – Craig Gidney
    Commented May 23, 2019 at 23:16
  • $\begingroup$ Right! But cheaper than $O(\exp (m))=O(\exp (n^2))$ ($m$=number of gates). I'm getting it I think. An RCS will generate a number of outputs $x_1,x_2,\cdots,x_k$, and a classical sampler will generate a number of outputs $y_1,y_2,\cdots, y_k$. A supercomputer can calculate the "Old HOG" or the "New HOG" or the "XEB" of $x$ and $y$. If the metric of $x$ is greater than the metric of $y$, then we argue that we've achieved quantum supremacy. $\endgroup$
    – Mark Spinelli
    Commented May 24, 2019 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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