Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Protecting the output of a quantum computer with random circuit samplers

Zixin Huang, Pieter Kok, Cosmo Lupo

Published Mar 25, 2020• 2 citations
OpenAlex

Abstract

Random quantum circuit samplers have been used to demonstrate the exponential speed-up of quantum processors beyond what is tractable classically [Arute, K. et al., Nature 574, 505 (2019)]. However, useful applications for these samplers have so far been elusive. Here, we propose random circuit as efficient devices for protecting the output of a quantum computer. We consider a scenario where the server performs universal fault-tolerant quantum computation and the user gains access to the output using a pseudo-random circuit. We show that a private key much smaller than the size of the output may prevent unauthorised access. For an $n$-qubit computation, a standard approach requires an $n$-bit key to scramble the state. We provide an information-theoretic proof showing that obfuscation can be achieved with order $n - H_\mathrm{min}(\mathsf{X})$ secret bits, where $H_\mathrm{min}(\mathsf{X})$ is the min-entropy of the output of the computation. As interesting computations are expected to have large min-entropy, this represents a substantial reduction of the key size.

Related papers

Certified Randomness from Quantum Supremacy

Scott Aaronson, Hung, Shih-Han

We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain $Ω(n)$ min-entropy, where $n$ is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits -- thereby "bootstrapping" from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol's output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most $n\sim 60$ qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.

arXiv:2303.01625•Mar 2, 2023•2 citations

Certified Randomness from Quantum Supremacy

Scott Aaronson, Shih-Han Hung

We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing “quantum supremacy” experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain Ω(n) min-entropy, where n is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits—thereby “bootstrapping” from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol’s output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most n∼ 60 qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.

ACM Symposium on Theory of Computing (STOC)•May 16, 2023•19 citations

Leveraging Quantum Circuit Cutting for Obfuscation and Intellectual Property Protection

George Typaldos, Wei Tang, Jakub M. Szefer

Circuit cutting is a novel technique in the field of quantum computing that offers a promising approach for breaking up large quantum circuits into smaller ones that can be executed on smaller quantum computers. Circuit cutting offers a scalable and hybrid computing approach, by combining classical and quantum computers to run large quantum circuits. At the same time, quantum circuits represent the fundamental building blocks of quantum algorithms, and obfuscation techniques are crucial for protecting the sensitive information and intellectual property encoded in these circuits. This paper constitutes the first security analysis of circuit cutting techniques as a means to protect quantum circuits, and not just for cutting bigger quantum circuits to fit on smaller devices. As cloud providers are in control of quantum computers and give access to users, utilizing cloud-based quantum computers for executing quantum circuits involves considerable security risks. This work demonstrates that quantum circuits can be effectively obfuscated by using quantum circuit cutting techniques. If users are worried about an adversary who attempts to reverse-engineer the original quantum algorithm, circuit cutting can be used as a security measure. To further provide configurable obfuscation level, i.e. number of possible circuits that the cloud provider would have to guess, this work proposes a novel dummy-subcircuits technique. This technique introduces dummy subcircuits with additional qubit cut points to create more confusion for the cloud provider and further help to obfuscate the user's original circuits with limited cost.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•3 citations

Quantum supremacy and random circuits

Ramis Movassagh

As Moore's law reaches its limits, quantum computers are emerging with the promise of dramatically outperforming classical computers. We have witnessed the advent of quantum processors with over $50$ quantum bits (qubits), which are expected to be beyond the reach of classical simulation. Quantum supremacy is the event at which the old Extended Church-Turing Thesis is overturned: A quantum computer performs a task that is practically impossible for any classical (super)computer. The demonstration requires both a solid theoretical guarantee and an experimental realization. The lead candidate is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of random quantum circuits. Google recently announced a $53-$qubit experimental demonstration of RCS. Soon after, classical algorithms appeared that challenge the supremacy of random circuits by estimating their outputs. How hard is it to classically simulate the output of random quantum circuits? We prove that estimating the output probabilities of random quantum circuits is formidably hard ($\#P$-Hard) for any classical computer. This makes RCS the strongest candidate for demonstrating quantum supremacy relative to all other proposals. The robustness to the estimation error that we prove may serve as a new hardness criterion for the performance of classical algorithms. To achieve this, we introduce the Cayley path interpolation between any two gates of a quantum computation and convolve recent advances in quantum complexity and information with probability and random matrices. Furthermore, we apply algebraic geometry to generalize the well-known Berlekamp-Welch algorithm that is widely used in coding theory and cryptography. Our results imply that there is an exponential hardness barrier for the classical simulation of most quantum circuits.

arXiv:1909.06210•Sep 11, 2019•23 citations

Certified randomness using a trapped-ion quantum processor

Minzhao Liu, Ruslan Shaydulin, Pradeep Niroula +29 more

Abstract Although quantum computers can perform a wide range of practically important tasks beyond the abilities of classical computers 1,2 , realizing this potential remains a challenge. An example is to use an untrusted remote device to generate random bits that can be certified to contain a certain amount of entropy 3 . Certified randomness has many applications but is impossible to achieve solely by classical computation. Here we demonstrate the generation of certifiably random bits using the 56-qubit Quantinuum H2-1 trapped-ion quantum computer accessed over the Internet. Our protocol leverages the classical hardness of recent random circuit sampling demonstrations 4,5 : a client generates quantum ‘challenge’ circuits using a small randomness seed, sends them to an untrusted quantum server to execute and verifies the results of the server. We analyse the security of our protocol against a restricted class of realistic near-term adversaries. Using classical verification with measured combined sustained performance of 1.1 × 10 18 floating-point operations per second across multiple supercomputers, we certify 71,313 bits of entropy under this restricted adversary and additional assumptions. Our results demonstrate a step towards the practical applicability of present-day quantum computers.

arXiv:2503.20498•Nature•Mar 26, 2025•34 citations

Efficient Post-Quantum Secured Blind Computation

Davies, Ethan, Alastair Kay

In the medium term, quantum computing must tackle two key challenges: fault tolerance and security. Fault tolerance will be solved with sufficiently high quality experiments on large numbers of qubits, but the scale and complexity of these devices means that a cloud-based access model is likely to dominate. How can we risk evaluating valuable computations on an untrusted server? Here we detail a verifiable circuit-based model that only requires classical communication between parties. The server is blind to the details of the computation, which is computationally secure.

arXiv:2404.07052•Apr 10, 2024•0 citations
Random quantum circuit samplers have been used to demonstrate the exponential speed-up of quantum processors beyond what is tractable classically [Arute, K. et al., Nature 574, 505 (2019)]. However, useful applications for these samplers have so far been elusive. Here, we propose random circuit as efficient devices for protecting the output of a quantum computer. We consider a scenario where the server performs universal fault-tolerant quantum computation and the user gains access to the output using a pseudo-random circuit. We show that a private key much smaller than the size of the output may prevent unauthorised access. For an nnn-qubit computation, a standard approach requires an nnn-bit key to scramble the state. We provide an information-theoretic proof showing that obfuscation can be achieved with order n−Hmin(X)n - H_\mathrm{min}(\mathsf{X})n−Hmin​(X) secret bits, where Hmin(X)H_\mathrm{min}(\mathsf{X})Hmin​(X) is the min-entropy of the output of the computation. As interesting computations are expected to have large min-entropy, this represents a substantial reduction of the key size.
We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain Ω(n)Ω(n)Ω(n) min-entropy, where nnn is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits -- thereby "bootstrapping" from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol's output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most n∼60n\sim 60n∼60 qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.
We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing “quantum supremacy” experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain Ω(n) min-entropy, where n is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits—thereby “bootstrapping” from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol’s output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most n∼ 60 qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.
Circuit cutting is a novel technique in the field of quantum computing that offers a promising approach for breaking up large quantum circuits into smaller ones that can be executed on smaller quantum computers. Circuit cutting offers a scalable and hybrid computing approach, by combining classical and quantum computers to run large quantum circuits. At the same time, quantum circuits represent the fundamental building blocks of quantum algorithms, and obfuscation techniques are crucial for protecting the sensitive information and intellectual property encoded in these circuits. This paper constitutes the first security analysis of circuit cutting techniques as a means to protect quantum circuits, and not just for cutting bigger quantum circuits to fit on smaller devices. As cloud providers are in control of quantum computers and give access to users, utilizing cloud-based quantum computers for executing quantum circuits involves considerable security risks. This work demonstrates that quantum circuits can be effectively obfuscated by using quantum circuit cutting techniques. If users are worried about an adversary who attempts to reverse-engineer the original quantum algorithm, circuit cutting can be used as a security measure. To further provide configurable obfuscation level, i.e. number of possible circuits that the cloud provider would have to guess, this work proposes a novel dummy-subcircuits technique. This technique introduces dummy subcircuits with additional qubit cut points to create more confusion for the cloud provider and further help to obfuscate the user's original circuits with limited cost.
As Moore's law reaches its limits, quantum computers are emerging with the promise of dramatically outperforming classical computers. We have witnessed the advent of quantum processors with over 505050 quantum bits (qubits), which are expected to be beyond the reach of classical simulation. Quantum supremacy is the event at which the old Extended Church-Turing Thesis is overturned: A quantum computer performs a task that is practically impossible for any classical (super)computer. The demonstration requires both a solid theoretical guarantee and an experimental realization. The lead candidate is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of random quantum circuits. Google recently announced a 53−53-53−qubit experimental demonstration of RCS. Soon after, classical algorithms appeared that challenge the supremacy of random circuits by estimating their outputs. How hard is it to classically simulate the output of random quantum circuits? We prove that estimating the output probabilities of random quantum circuits is formidably hard (#P\#P#P-Hard) for any classical computer. This makes RCS the strongest candidate for demonstrating quantum supremacy relative to all other proposals. The robustness to the estimation error that we prove may serve as a new hardness criterion for the performance of classical algorithms. To achieve this, we introduce the Cayley path interpolation between any two gates of a quantum computation and convolve recent advances in quantum complexity and information with probability and random matrices. Furthermore, we apply algebraic geometry to generalize the well-known Berlekamp-Welch algorithm that is widely used in coding theory and cryptography. Our results imply that there is an exponential hardness barrier for the classical simulation of most quantum circuits.
Abstract Although quantum computers can perform a wide range of practically important tasks beyond the abilities of classical computers 1,2 , realizing this potential remains a challenge. An example is to use an untrusted remote device to generate random bits that can be certified to contain a certain amount of entropy 3 . Certified randomness has many applications but is impossible to achieve solely by classical computation. Here we demonstrate the generation of certifiably random bits using the 56-qubit Quantinuum H2-1 trapped-ion quantum computer accessed over the Internet. Our protocol leverages the classical hardness of recent random circuit sampling demonstrations 4,5 : a client generates quantum ‘challenge’ circuits using a small randomness seed, sends them to an untrusted quantum server to execute and verifies the results of the server. We analyse the security of our protocol against a restricted class of realistic near-term adversaries. Using classical verification with measured combined sustained performance of 1.1 × 10 18 floating-point operations per second across multiple supercomputers, we certify 71,313 bits of entropy under this restricted adversary and additional assumptions. Our results demonstrate a step towards the practical applicability of present-day quantum computers.
In the medium term, quantum computing must tackle two key challenges: fault tolerance and security. Fault tolerance will be solved with sufficiently high quality experiments on large numbers of qubits, but the scale and complexity of these devices means that a cloud-based access model is likely to dominate. How can we risk evaluating valuable computations on an untrusted server? Here we detail a verifiable circuit-based model that only requires classical communication between parties. The server is blind to the details of the computation, which is computationally secure.