The Hardness of Learning Quantum Circuits
and Its Cryptographic Applications

In what follows, we let $𝒞$ denote a class of quantum circuits; for example, a concrete choice of $𝒞$ is the ensemble of 1D brickwork circuits with depth $d={\log }^{2}n$.²²2We pick out $d={\log }^{2}n$ here because it happens to be a depth at which the existing state-of-the-art learning algorithms, like those in [35, 49, 43], fail to be efficient. Even if the learning algorithms were to be improved, any depth beyond which the efficiency of those learning algorithms fail is a good design choice for our assumptions and cryptographic constructions.

In words, the Computational No-Learning Assumption says that it a polynomial-time quantum algorithm $A$, given only polynomially-many copies of the output $|C⟩$ of a randomly-chosen circuit $C$ from the circuit ensemble $𝒞$, cannot produce a classical description of another circuit $D$ from the same class ${𝒞}_n$ and whose output state $|D⟩$ approximates $|C⟩$. We note that the algorithm $A$ only has access to copies of the state³³3We stress that $|C⟩$ does not mean the classical description of $C$, but rather the state generated by the circuit $C$ on the all zero input. generated by the random circuit and the circuit description itself is not known to the algorithm. Furthermore, Conjecture 1 actually refers to an entire family of assumptions, one for each choice of circuit class $𝒞$ and parameters $(\epsilon ,\delta )$. Throughout this paper we consider a fixed circuit family for convenience (e.g., 1D brickwork circuits with depth ${\log }^{2}n$ unless otherwise specified). We elaborate on the different parameter settings for $(\epsilon ,\delta )$ below. For clarity we abbreviate “Computational No-Learning” as “No-Learning”. Oftentimes we will abbreviate “$(\epsilon ,\epsilon )$-No-Learning” as “$\epsilon$-No-Learning”.

In this section, we postulate a computational version of the famous No-Cloning principle of quantum mechanics. At a high level, it stipulates that given polynomially copies of the output state of a random quantum circuit, it is intractable to produce an additional copy of the state, or even an approximation of it.

As before, the algorithm $A$ only has access to copies of the state generated by the random circuit and not the circuit description itself. We also abbreviate “Computational No-Cloning” as “No-Cloning” and also abbreviate “$(\epsilon ,\epsilon )$-No-Cloning” as “$\epsilon$-No-Cloning”.

What are the prospects of proving Conjecture 1 or Conjecture 2 outright? First, we note that the conjectures are necessarily computational, meaning that they are intrinsically about the limits of efficient quantum computation. This is because it is possible for an exponential-time quantum algorithm to learn a circuit description with high probability, given only polynomially-many quantum samples (and thus also solve the cloning task with similar sample complexity). One method is to use the classical shadows protocol of [34]; we describe this in more detail in [28]. We note that Morimae and Yamakawa already observed that there is always an exponential-time attack on one-way state generators [55] via shadow tomography; this is essentially the same observation.

Furthermore, we note that proving our hardness conjectures would have dramatic implications for classical complexity theory. The classical shadows-based algorithm described in [28] can be implemented in polynomial time assuming the complexity inclusion ${\mathrm{NP}}^{\mathrm{\#}\mathrm{P}}\subseteq \mathrm{BQP}$.⁵⁵5It was recently shown by Hiroka and Hsieh [32] that efficient state learning is possible if $\mathrm{PP}\subseteq \mathrm{BQP}$, which represents an improved complexity upper bound. Therefore Conjecture 1 implies $\mathrm{P}\ne \mathrm{PSPACE}$. While this doesn’t imply (say) $\mathrm{P}\ne \mathrm{NP}$, for all intents and purposes this would represent a similar breakthrough in mathematics and complexity theory. The longstanding difficulty of proving such complexity separations pose a barrier to proving our hardness assumptions.

We now discuss the evidence for our hardness assumptions. First we discuss the No-Learning assumption.

A one way state generator (OWSG) is an efficient algorithm that takes as input a classical key $k$, and outputs a quantum state $|{\psi }_k⟩$ from that key. Anyone with the key $k$ can efficiently verify that $|{\psi }_k⟩$ is the correct output. Furthermore, given polynomially many copies of the $|{\psi }_k⟩$ for a randomly chosen $k$, it should be computationally hard for an adversary to produce another key $k^{\prime }$ such that the corresponding state $|{\psi }_{k^{\prime }}⟩$ is close to the original output $|{\psi }_k⟩$. (For a formal definition, see [28]). Introduced by Morimae and Yamakawa [56], OWSGs are a quantum analogue of one-way functions, which are functions efficiently computable in the forwards direction but computationally difficult to invert.

The No-Learning Assumption (Conjecture 1) is essentially equivalent to the existence of a OWSG, namely the Random Circuit OWSG described below in Figure 1. For a range of parameters, this is immediate: for negligible $\epsilon$ (i.e., $\epsilon$ goes to $0$ faster than any inverse polynomial), the $\epsilon$-No-Learning Assumption is easily seen to be equivalent to the security of the Random Circuit OWSG. When $\epsilon$ is larger, say even up to $1-1/\mathrm{poly}(n)$, the equivalence still holds; this relies on hardness amplification techniques for OWSGs [55, 17]. We note that this equivalence was also independently observed by Hiroka and Hsieh in a recent preprint [32].

Although a OWSG is not immediately cryptographically useful by itself, it is now known that OWSGs can be used as a primitive building block for a variety of quantum cryptosystems. In their papers defining OWSGs [56, 55], Morimae and Yamakawa showed that OWSGs can be used to build bounded-time-secure digital signature schemes. In a breakthrough work, Khurana and Tomer showed that OWSGs imply the existence of quantum bit commitments [41], which in turn imply other functionalities such as quantum zero knowledge proofs for $\mathrm{NP}$ and secure multiparty computation [19]. Therefore, using the Random Circuit OWSG, we obtain concrete implementations of these cryptosystems on quantum computers, without relying on the use of one-way functions.

An attractive feature of our Random Circuit OWSG is that it seems potentially amenable to implementation on noisy quantum computers, and thus the corresponding cryptosystems may be realizable in the near- and medium-term. We discuss noise tolerant versions of our random circuit-based cryptographic protocols in Section 1.4.

A commitment scheme enables two parties (known as a “committer” and a “receiver”) to perform the cryptographic equivalent of putting a message in a sealed envelope that is opened later. In a quantum commitment scheme, a committer upon getting a bit $b$ generates a bipartite pure state ${|{\psi }_b⟩}_{\mathrm{AB}}$, and sends the register $\mathrm{B}$ to the receiver; this is the “commitment phase” of the protocol and is the analogue of sending the sealed envelope. At this point the receiver should not be able to tell what the bit $b$ is.

Later, in the “reveal phase” of the protocol, the committer announces the bit $b$ and sends the remaining register $\mathrm{A}$ of $|{\psi }_b⟩$ to the receiver, who can uncompute the state to check its validity. The security of the commitment scheme ensures that the committer cannot “change his mind” in between the commit and reveal phases to convince the receiver he had committed to the opposite bit $1-b$.

Recently, quantum commitments have become a centerpiece of the zoo of quantum cryptographic primitives [8, 56, 19, 41]. As mentioned, Khurana and Tomer showed that OWSGs can be used to construct quantum bit commitments in a generic way [41]. Therefore our No-Learning Assumption implies the existence of secure quantum commitments. However the construction of commitments in [41] is quite involved, requiring an intricate sequence of transformations mimicking the classical transformation from one-way functions to pseudorandom generators [31].

We construct a simple quantum bit commitments based on the Computational No-Cloning Assumption (Conjecture 2), and furthermore the analysis is fairly direct and straightforward. We describe the construction below. As discussed in Section 1.1, the No-Cloning Assumption implies the No-Learning Assumption. The ease of obtaining a commitment scheme from the No-Cloning Assumption suggests that the No-Cloning Assumption could be strictly stronger than the No-Learning Assumption (because it appears that obtaining commitments from OWSGs requires an intricate analysis [41]).

We present and analyze the bit commitment scheme in detail in [28].

While implementing the Random Circuit OWSG on a realistic quantum computer, noise can degrade the fidelity of the output state. For certain choices of noise parameters and depth regimes, the fidelity can be inverse polynomial in the number of qubits. If that happens, the success probability of any verification procedure would degrade similarly. Although the OWSG may be secure against any polynomial-time adversary, it may not be very useful if the “honest user” (e.g., someone with the key) tries to run it on a noisy quantum computer. On the other hand, making a OWSG tolerant to noise may give greater leeway to break its security.

However, if we make a sufficiently strong assumption (e.g., the $\epsilon$-No Learning assumption for negligible $\epsilon$), there is a noticeable gap between the success probability of a noisy verifier (who has the circuit description) and any noiseless polynomial-time adversary (who doesn’t have the circuit description): the adversary cannot produce any approximation to the state except with negligible fidelity. We can amplify this gap to obtain a NISQ-friendly OWSG, where both the generation and verification algorithms can be run on a noisy quantum computer, but the OWSG also retains its security against noiseless adversaries. We achieve this amplification via a computational Chernoff bound.

As a direct application of our NISQ-friendly OWSG we obtain a NISQ-friendly quantum digital signature scheme. At a high level, a digital signature scheme (with quantum public keys) is a method for a signer to generate a signature for a message in a way that a third party verifier (using a quantum public key posted by the user beforehand) can verify that the signature belongs to the message (and in particular, the message or the signature have not been changed).

Morimae and Yamakawa [56] showed that such quantum digital signature schemes can be directly constructed from OWSGs by adapting the famous Lamport construction of digital signatures [48]. We show that by plugging in the NISQ-friendly random circuit OWSG, their digital signature scheme becomes NISQ-friendly as well. This gives example of an end-to-end cryptographic task for NISQ-devices whose hardness relies on an innately quantum conjecture.

We present the scheme and the analysis in detail in [28].

Note that the only noise assumption we need is that the fidelity of the signal should at most be inverse polynomially large. However, an observant reader would notice that ${𝒞}_n$ is an ensemble of sufficiently deep circuits. For certain noise models, for e.g. constant rate of depolarizing noise per gate, or more generally, constant rate of unital noise per gate, the output converges to the maximally mixed state [6, 26] exponentially fast in the depth of the circuit, which would cause inverse superpolynomially large signal decay at large depths. However, there are three perspectives on why our proposal is still relevant to near-term experiments.

Firstly, the results proving convergence to the maximally mixed state [26, 7] are asymptotic statements, whereas real experiments have finite system sizes. Thus, there is a discrepancy between what theoretically happens when we scale up the system size and what is experimentally observed for a fixed system size. For example, in quantum advantage demonstrations with random circuits, the experimentalists have observed signatures of long range entanglement and evidence of convergence to the Porter-Thomas distribution when the output state is measured in the standard basis [10, 57]. Note that Porter-Thomas distribution is far in total variation distance from the uniform distribution, where the latter is what we get when we measure a maximally mixed state in the standard basis. If the system were indeed close to being maximally mixed, we would neither see long-range entanglement nor Porter-Thomas type behavior. Thus, sampling from the uniform distribution is not a good approximation to the realistic output distribution, even though the distributions are close asymptotically [6, 26].

There are other classical samplers, such as the recent one proposed in [7], which differ from simply sampling the uniform distribution. However, the sampler in [7] achieves a smaller total variation distance than the uniform distribution only at a depth of approximately $\sim \log n$. Properties of real experiments – such as the presence of long-range entanglement – indicate that they do not operate at logarithmic depth but rather in a much deeper regime. Thus, in the same way as the uniform distribution, it is unclear if the sampler of [7] is directly applicable to real experiments, even though its classical spoofing distribution is again asymptotically close to the noisy target distribution.

Secondly, note that the fidelity of the output state of a noisy circuit, comprised of two qubit gates and a single-qubit, uncorrelated noise channel acting upon each qubit after the application of each gate, is

or the probability that no errors occurred anywhere in the system. Here, where $s$ is the circuit size and $ϵ$ is the noise rate per qubit. If $ϵ$ is at most $\sim \frac{1}{n}$, $F\approx e^{-\mathrm{\Theta }(s\cdot ϵ)}$. Hence, one valid regime for inverse polynomial decay in fidelity is when $ϵ$ is $\sim \frac{1}{n\log n}$ and the system size $s$ is $\sim n{\log }^{2}n$. In certain models, the structure of the output state becomes even simpler. One of the a noise models for which this is manifestly true is the white noise model [10, 14, 24]. According to this model, if the noise per gate is unital, and if the noise rate $ϵ$ is at most $\sim \frac{1}{n}$, then the output state of the circuit can be written as

that is, as a linear combination of ${\rho }_{\mathrm{𝗇𝗈𝗂𝗌𝖾𝗅𝖾𝗌𝗌}}$, which is what the output state would have been if there were no noise, and the maximally mixed state. While the noise rate per gate going down with $n$ is unrealistic for extremely large system sizes, it is nonetheless a reasonable model of real experiments as structural properties of experimental output states match the white noise output state. In fact, judging by the recent progress in random quantum circuit experiments, e.g. [10, 57, 66], it seems quite reasonable to model realistic noise as going down with system size.

Thirdly, note that in all of the previous discussions, we have assumed noise to be unital. But real noise is complicated and it is unclear if any of the above results (e.g., convergence to the maximally mixed state or the white noise model) are realistic for near-term experiments. As an example of surprising behavior with more general noise models, researchers have recently studied the effects of non-unital noise channels in random quantum circuits [27, 53, 61]. Non-unital noise is ubiquitous in real world experiments, as witnessed by, e.g., readout errors, $T_1$ decay for superconducting systems, and photon loss in bosonic systems [67, 68, 72]. In particular, certain structural properties that are true for unital noise at some regimes, like anti-concentration or convergence to the maximally mixed state, fail in the presence of any constant rate non-unital noise channel [27], and hardness or easiness results that assume these properties, like [1, 5, 18, 7], do not seem to work.