Existing experimental demonstrations of quantum computational advantage have had the limitation that verifying the correctness of the quantum device requires exponentially costly classical computations. Here we propose and analyse an interactive protocol for demonstrating quantum computational advantage, which is efficiently classically verifiable. Our protocol relies on a class of cryptographic tools called trapdoor clawfree functions. Although this type of function has been applied to quantum advantage protocols before, our protocol employs a surprising connection to Bell’s inequality to avoid the need for a demanding cryptographic property called the adaptive hardcore bit, while maintaining essentially no increase in the quantum circuit complexity and no extra assumptions. Leveraging the relaxed cryptographic requirements of the protocol, we present two trapdoor clawfree function constructions, based on Rabin’s function and the Diffie–Hellman problem, which have not been used in this context before. We also present two independent innovations that improve the efficiency of our implementation and can be applied to other quantum cryptographic protocols. First, we give a scheme to discard socalled garbage bits, removing the need for reversibility in the quantum circuits. Second, we show a natural way of performing postselection that reduces the fidelity needed to demonstrate quantum advantage. Combining these results, we describe a blueprint for implementing our protocol on Rydberg atombased quantum devices, using hardwarenative operations that have already been demonstrated experimentally.
 Award ID(s):
 1818914
 NSFPAR ID:
 10339339
 Date Published:
 Journal Name:
 ArXivorg
 ISSN:
 23318422
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract 
Computational simulations of nuclear magnetic resonance (NMR) experiments are essential for extracting information about molecular structure and dynamics, but are often intractable on classical computers for large molecules such as proteins and protocols such as zerofield NMR. We demonstrate the first quantum simulation of a NMR spectrum, computing the zerofield spectrum of the methyl group of acetonitrile on a trappedion quantum computer. We reduce the sampling cost of the quantum simulation by an order of magnitude using compressed sensing techniques. Our work opens a new practical application for quantum computation, and we show how the inherent decoherence of NMR systems may enable the simulation of classically hard molecules on nearterm quantum hardware.more » « less

We define the notion of oneshot signatures, which are signatures where any secret key can be used to sign only a single message, and then selfdestructs. While such signatures are of course impossible classically, we construct oneshot signatures using quantum nocloning. In particular, we show that such signatures exist relative to a classical oracle, which we can then heuristically obfuscate using known indistinguishability obfuscation schemes. We show that oneshot signatures have numerous applications for hybrid quantum/classical cryptographic tasks, where all communication is required to be classical, but local quantum operations are allowed. Applications include onetime signature tokens, quantum money with classical communication, decentralized blockchainless cryptocurrency, signature schemes with unclonable secret keys, noninteractive certifiable minentropy, and more. We thus position oneshot signatures as a powerful new building block for novel quantum cryptographic protocols.more » « less

Simulations of nuclear magnetic resonance (NMR) experiments can be an important tool for extracting information about molecular structure and optimizing experimental protocols but are often intractable on classical computers for large molecules such as proteins and for protocols such as zerofield NMR. We demonstrate the first quantum simulation of an NMR spectrum, computing the zerofield spectrum of the methyl group of acetonitrile using four qubits of a trappedion quantum computer. We reduce the sampling cost of the quantum simulation by an order of magnitude using compressed sensing techniques. We show how the intrinsic decoherence of NMR systems may enable the zerofield simulation of classically hard molecules on relatively nearterm quantum hardware and discuss how the experimentally demonstrated quantum algorithm can be used to efficiently simulate scientifically and technologically relevant solidstate NMR experiments on more mature devices. Our work opens a practical application for quantum computation.

As the yeartoyear gains in speeds of classical computers continue to taper off, computational chemists are increasingly examining quantum computing as a possible route to achieve greater computational performance. Quantum computers, built upon the properties of superposition, interference, and entanglement of quantum bits, offer, in principle, the possibility to outperform classical computers for solving many important classes of problems. In the field of chemistry, quantum algorithm development offers promising propositions for solving classically intractable problems in areas such as electronic structure, chemical quantum dynamics, spectroscopy, and cheminformatics. However, physical implementations of quantum computers are still in their infancy and have yet to outperform classical computers for useful computations. Still, quantum software development for chemistry is a highly active area of research. In this perspective, we summarize recent progress in the areas of quantum computing algorithms, hardware, and software, and we describe the challenges that remain for useful implementations of quantum computing for chemical applications.more » « less