I looked through the paper. It seems like they haven't run this on a real quantum computer.
The preparation of the state | by the referee is computationally more expensive as it requires the implementation of pseudorandom permutations. As a near-term toy example, one could implement permutations using the Simplified Advanced Encryption Standard (S-AES) protocol. S-AES uses a block size of 16 bits (as opposed to 128 bits for AES) and a key size of 16 bits as well (128, 192 or 256 for AES). A system size of 16 can display features of quantum advantage: from Theorem 1 with, e.g., =216, =215 and =1/6, any classical algorithm solving complement sampling requires 214 =16384 distinct samples. A quantum circuit implementation of S-AES based on [45] requires only 48 qubits, 168 Toffoli gates, 364 controlled not gates, and 75 not gates.
Why didn't they take the next step and run their algorithm?
It is impossible to travel faster than light, and certainly not desirable, as one's hat keeps blowing off. -- Woody Allen