Quantum mechanics asserts that the state of a physical system is characterized by a vector in complex Hilbert space, whose dimension corresponds to the number of degrees of freedom of the system. Specifically, a system with\(2^n\) possible degrees of freedom (such as ann-qubit system, the quantum analogue to ann bit system) is represented as a unit vector over\({\mathbb {C}}^{2^n}\). The ability to sample a random state of a system is a fundamental task when attempting to provide a computational description of the physical world.

Since the description length of a quantum state is infinite (and very long even when taken to a finite precision), relaxed notions for random state sampling are considered in the literature. Most commonly (and in this work) we consider restricting thenumber of copies of the sampled state that are given to the adversary.^Footnote1 The notion of quantumt-designs[AE07] considers computationally unbounded adversaries that are givent copies of the sampled state, and the requirement is that this input is (statistically) indistinguishable fromt copies of a true random state. The resources of generatingt-designs scale at least linearly witht, and therefore if efficient generation is sought,t designs can only be constructed for polynomialt.^Footnote2 Recently, a computational variant known as Pseudorandom Quantum State (PRS) was proposed by Ji, Liu and Song [JLS18]. In a PRS, the adversary is allowed to request an a-priori unbounded polynomial number of samplest, but the guarantee of indistinguishability only holds againstcomputationally bounded adversaries. PRS have applications in quantum-cryptography (e.g. quantum money[JLS18]) and computational physics (e.g. simulation of thermalized quantum states[PSW06]).

It was shown in[JLS18,BS19] that PRS can be constructed from any quantum-secure one-way function. The design paradigm in both works is as follows. First, assume you are given (quantum) oracle access to a (classical) random function, and show how to efficiently construct a PRS which is secure even against computationally unbounded adversaries, a notion that[BS19] calls Asymptotically Random State (ARS). Then, replace the random function with a post-quantum pseudorandom function (PRF) to obtain computational security. Since only a fixed number of calls to the PRF is required in order to generate each PRS copy, this paradigm also leads to new constructions oft-designs, as observed in[BS19].

The previous works[JLS18,BS19] showed how to construct ann-qubit PRS, which is secure against any\(\mathrm{poly}(n)\) time adversary. To be more precise, they constructed ARS whose distinguishing advantage is bounded by\(4 t^2 \cdot 2^{-n}\), and converted it into a PRS using a PRF as described above. We can therefore say that thestatistical security parameter of the scheme is (essentially)n, and there is an additional computational security parameter that comes from the hardness of the PRF. Indeed, a security parameter ofn seems quite sufficient since the complexity of the construction is\(\mathrm{poly}(n)\) so it is possible to choosen as large as needed in order to provide sufficient security. Alas it is not possible to convert ann-qubit state generator into one that produces a random state over a smaller number of qubits, say\(k<n\). This may be quite surprising as one would imagine that we can simply generate ann-qubit state, and just take itsk-qubit prefix. However, recall that then-qubits are in superposition, and taking a prefix is equivalent to measurement of the remaining\((n-k)\) qubits. For each of thet copies, this measurement has a different outcome and therefore each of thet copies will produce a differentk-qubit states, as opposed tot copies of the same state as we wanted.

This peculiar state of affairs means that prior to this work it was not known, for example, how to construct ARS/PRS ofn qubits, but with adversarial advantage bounded by\(2^{-2n}\). This issue is also meaningful when considering the concrete (non-asymptotic) security guarantees of PRS, where we wish to obtain for example 128 bits of security against an adversary that obtains at most\(2^{20}\) copies of a PRS over 70 qubits.

This Work: Scalable ARS/PRS. In this light, it is desirable to introduce ARS/PRS constructions where the security parameter is in fact a parameter which is tunable independently of the length of the generated state. We call this notionscalable ARS/PRS. We notice that the approaches of[JLS18,BS19] are inherently not scalable since they can only generate states in which all computational-basis elements have the same amplitude, and the randomness only effects the phase. Such vectors are inherently distinguishable from uniform unless the dimension is very large (hence their dependence between length and security). In this work, we present new techniques for constructing ARS/PRS and in particular present a scalable construction under the same cryptographic assumptions as previous works.

1.1Our Results

Our main technical result, as in all previous works, is concerned with constructing an ARS generator which is efficient given oracle access to a random function.^Footnote3

Lemma 1.1

(Main Technical Lemma). There exists a scalable ARS generator.

Furthermore, for every lengthn of a quantum state and security parameter\(\lambda \), running the generatort times (for anyt) produces an output distribution that is\(O\left( \frac{t}{e^{\lambda }} \right) \)-indistinguishable fromt copies of a random quantum state ofn qubits.

We note that in previous works that construct ARS generators[JLS18,BS19] the dependence ont in the bound on the trace distance is quadratic, that is, previous ARS generators are known to achieve a bound of\(\frac{t^2}{2^n}\) on the trace distance betweent-copies of the ARS and a random quantum (n-qubit) state, whereas in this work the trace distance bound only scales up linearly witht.

As immediate corollaries and similarly to[JLS18,BS19], we derive the existence of a scalable PRS generator (assuming post-quantum one-way functions) and scalablet-design generators (unconditionally). Unlike scalable PRS generators, scalable statet-design generators were known to exist before this work, however their depth was known to scale up linearly witht (and polynomially inn), and in our construction the depth scales logarithmically witht (and polynomially in\(n, \lambda \)).

Corollary 1.2

If post-quantum one-way functions exist, then scalable PRS generators exist.

Corollary 1.3

For any polynomial\(t(\cdot ) : {\mathbb {N}}\rightarrow {\mathbb {N}}\), scalable state\(t(\lambda )\)-design generators exist where the circuit depth is\(\mathrm{poly}(n, \lambda , \log t)\).

Our ARS construction requires a random oracle withn bits of input (wheren is the length of the generated state) and\(\mathrm{poly}(\lambda )\) bits of output, it therefore follows that if\(n=O(\log \lambda )\), then it is possible to instantiate the construction with a completely random string of length\(2^n \cdot \mathrm{poly}(\lambda ) = \mathrm{poly}(\lambda )\), and obtain statistically secure PRS. We view this consequence as not very surprising in hindsight.

Recently Alagic, Majenz and Russell[AMR19] proposed the notion of random state simulators. Simulators are stateful, and their local state grows with the number of copiest, however, there is no a-priori bound on the number of copies that the simulator can produce, and the guarantee is information-theoretic rather than computational. One can observe that a scalable ARS generator also implies efficient state simulators, by using the random-oracle simulation technique of Zhandry [Zha19]. The state simulators of[AMR19] follow a different approach, which is not known to imply ARS, and achieve simulators with perfect security (and thus straightforwardly scalable), but our ARS provides a different avenue for scalable random quantum state simulators as well.

1.2Paper Organization

We provide a detailed technical overview of our results in Sect. 2. Preliminaries appear in Sect. 3, and in particular we formally state the derivation of the corollaries from the main theorem (which were implicit in previous work) in Sect. 3.3. Our technical results are presented in the following two sections. In Sect. 4 we present quantum information-theoretic tools which are required for our construction but may also find other uses. Then Sect. 5 contains our actual construction.

We now provide a technical outline of how we achieve our main result in Lemma 1.1. Deriving the corollaries is straightforward using known techniques.^Footnote4

As Lemma 1.1 states, we design an algorithm that has oracle access to a random functionf, takes as input a bit lengthn and a security parameter\(\lambda \), runs in time\(\mathrm{poly}(n,\lambda )\), and produces a quantum state overn-qubits\(|{\psi _{f,n,\lambda }}\rangle \) (note that even though our algorithm is randomized, it can either output the state\(|{\psi _{f,n,\lambda }}\rangle \) or\(\bot \) and will never output the “wrong” state). It furthermore holds that the distribution that samples a random functionf and outputs\(|{\psi _{f,n,\lambda }}\rangle ^{\otimes t}\) (i.e.t copies of the state\(|{\psi _{f,n,\lambda }}\rangle \)), is within trace distance at most\(\mathrm{poly}(t)/2^\lambda \) from the distribution that producest copies of a truly randomly sampledn-qubit state.

We recall the standard Dirac notation for vectors in Hilbert space. Ann-qubit state is generically denoted by a unit vector in\({\mathbb {C}}^{2^n}\) of the form\(|{\alpha }\rangle = \sum _{x \in \{0,1\}^n} \alpha _x |{x}\rangle \). Throughout this overview we wish to refer to normalized as well as non-normalized vectors. We will use the convention that a vector\(|{\alpha }\rangle \) is not necessarily normalized unless explicitly noted that it represents a quantum state (or a unit vector), and will denote its normalization

where\(\langle {\alpha }|{\alpha }\rangle = \sum _x \left| {\alpha _x} \right| ^2\).

As explained above, prior works generated quantum states where in the standard basis all coefficients had the same amplitude, i.e. their ARS could be represented by\(|{\alpha }\rangle \) s.t.\(\left| {\alpha _x} \right| =1\) for allx. We abandon this approach, which as we explained cannot lead to a scalable ARS construction. Instead, we will show how to interpret a random functionf as an implicit representation of a random unit vector in\({\mathbb {C}}^{2^n}\). Moreover, we want this interpretation to belocally computable in the sense that the value\(\alpha _x\) only depends onf(x). Our approach, therefore, is more direct and also more involved than the approach taken in previous works, since we will try to sample from a space that most closely resembles the uniform distribution over quantum states.

2.1Our Approach: Implicit Random Gaussian Vector

Assume that we had an efficiently computable classical function\(g(\cdot )\) s.t. if we set\(v_x = g(f(x))\) and consider the vector\(|{v}\rangle = \sum _{x} v_x |{x}\rangle \), then the distribution on\(|{v}\rangle \) (induced by sampling the functionf randomly) isspherically symmetric, i.e. invariant to unitary transformations (“rotations” in\({\mathbb {C}}^{2^n}\)). In this case, the normalized vector\(|{\hat{v}}\rangle \) is a uniform unit vector. In other words, we will show how to use the random functionf as an implicit representation of a vector\(|{v}\rangle \) such that for allx,\(v_x\) can be efficientlylocally computed givenx (and oracle access tof).

Our solution, therefore, needs to address two challenges. The first is to properly define a locally efficiently computable functiong with the desirable properties. The second is to efficiently generate the quantum state\(|{\hat{v}}\rangle \) given oracle access to the values\(v_x\). Let us describe how we handle each one of these challenges at a high level, and then expand on the parts that contain the bulk of technical novelty.

First Technique: Multivariate Gaussian Sampling. For the first challenge, we use the multivariate Gaussian distribution, whose spherical symmetry has proven useful for many applications in the literature. Our functiong will simply be a Gaussian sampler (or more accurately, a two-dimensional Gaussian sampler, for the real and imaginary parts of\(v_x\)). That is, we use the entries of the random functionf as random tape for a Gaussian sampling procedureg. Since the Gaussian distribution is spherically symmetric, such ag has the properties that we need.

This approach indeed seems quite suitable but achieving (perfect) spherical symmetry is at odds with achieving computational efficiency, simply because the Gaussian distribution is continuous and has infinite support. Indeed, we will need to show a truncated discretized Gaussian distribution which on one hand can be sampled efficiently, and on the other hand provides approximate spherical symmetry. Note that the notion of approximation we are interested in here is with respect to the trace distance between the quantum state\(|{\hat{v}}\rangle ^{\otimes t}\) and at-repetition of a random unit vector. This requires us to develop tools in order to relate this notion to standard notions such as Euclidean distance. These tools are not particularly complicated but we view them as fundamental and of potential to be used elsewhere.^Footnote5 We elaborate more on this in Sect. 2.2 below, and the full details appear in Sect. 4.

Second Technique: Rejection Sampling. The second challenge is addressed using a quantum analog of therejection sampling technique. Recall that in standard probability theory, if it is possible to sample from a distributionp where\(\Pr [x]=p_x\), then we can consider the experiment of first sampling fromp, and then either outputting the sample receivedx with probability\(q_x\), or aborting and restarting the process with probability\(1-q_x\). This process constitutes a sampler for the distribution\(\frac{p_x q_x}{\sum _{x} p_x q_x}\). The probability of not aborting is\(\sum _{x} p_x q_x\), and therefore the expected running time of the new sampler is\(\frac{1}{\sum _{x} p_x q_x}\). In the quantum setting, a similar technique can be used for superpositions (Indeed, extensions of these technique were used e.g. in[ORR13]).

In this work we use quantum rejection sampling to generate quantum states from scratch. To create our state\(|{v}\rangle \) we will start with the uniform superposition\(|{u}\rangle = \sum _x |{x}\rangle \), and via a rejection process we can obtain (not necessarily with good probability), any desired superposition\(|{v}\rangle \). The probability of success in the quantum case is\(\frac{1}{d^2} \cdot \frac{\langle {v}|{v}\rangle }{\langle {u}|{u}\rangle }\), whered is ana-priori bound on\(\max _x \left| {v_x} \right| \) that needs to be given as a parameter to the rejection sampling procedure. (The algorithm and success probability are analogous to the classical version described above, when replacing\(q_x\) with\(\frac{v_x}{d}\) and considering\(\ell _2\) norm instead of\(\ell _1\).)

On the face of it, the rejection sampling procedure can work to create any state\(|{v}\rangle \) when a boundd is known. However, the probability of success can still be very small (e.g. negligible), so if we wish to use repetition to obtain\(|{v}\rangle \), the expected running time will become very large (e.g. super-polynomial). Fortunately, our vectors\(|{v}\rangle \) are (approximately) Gaussian, which means that they have strong concentration properties that guarantee that with high probability two properties are satisfied. The first is that all entries\(v_x\) have roughly the same magnitude, up to a factor of\(\mathrm{poly}(n,\lambda )\).^Footnote6 This allows us to choose the valued in such a way that the rejection sampling algorithm will operate correctly. The second property is that\(\langle {v}|{v}\rangle \approx 2^n\) (formally,\(\langle {v}|{v}\rangle \) is a constant factor away from\(2^n\)), this makes the probability of success noticeable (i.e.\(1/\mathrm{poly}(n,\lambda )\)). We informally call a vector that maintains the combination of these two properties “balanced”. By running in time\(\mathrm{poly}(n, \lambda )\) and repeating the process as needed we can amplify the success probability to\(1-2^{-\lambda }\). We generalize these properties and provide a state generator for any oracle\(v_x\) which satisfied the balance property, see Sect. 4.

Lastly, we note that while the first property above (bound ond) can be made to hold for anyn, the second one (lower bound on\(\langle {v}|{v}\rangle \)) might not hold with high enough probability. Special care needs to be taken in the case wheren is very small, since in that case concentration properties are insufficient to imply that\(\langle {v}|{v}\rangle \) does not fall far below its expected value with small yet significant probability (we wish to succeed with all but\(2^{-\lambda }\) probability, so anything higher than that is already significant). In such a case, the success probability of the rejection sampler might become negligibly small, which will lead to failure in generating a state.^Footnote7 Luckily, since the dimension of the vector\(|{v}\rangle \) is\(2^n\), good concentration kicks in already at\(n \gtrsim \log (\lambda )\), so we only need to worry about this issue when\(n < \log (\lambda )\). For such smalln, the sampling algorithm can store the vector\(|{v}\rangle \) in its entirety, and check whether the norm\(\langle {v}|{v}\rangle \) is sufficiently close to its expectation (which happens with constant probability). If the norm is not in the required range, we sample a new Gaussian.^Footnote8 Repeating this roughly\(\lambda \) times guarantees that we generate a “balanced” vector from a spherically symmetric distribution with all but\(2^{-\lambda }\) probability.

2.2Approximate Gaussians Under Tensored Trace Distance

We wish to do approximate sampling from the continuous Gaussian distribution using an efficiently locally sampleable distribution. If we wish to be fully precise, we need to consider Gaussian distributions over the complex regime. However, for the purpose of sampling, one can think of each complex coordinate just as two real-valued coordinates. For the purpose of this overview we will simplify things even further and assume that we wish to sample from a real-valued Gaussian, i.e. a vector in\({\mathbb {R}}^{2^n}\) instead of\({\mathbb {C}}^{2^n}\). Everything we discuss here be extended to the complex regime in a natural manner. From this point and on, our goal is to find an efficient samplerg s.t. when sampling\(v_x\) i.i.d from the distribution generated byg, and sampling\(w_x\) from a continuous Gaussian, it holds that the trace distance (quantum optimal distinguishing probability) between the quantum states\(|{\hat{v}}\rangle ^{\otimes t}\) and\(|{\hat{w}}\rangle ^{\otimes t}\), is at most\(\mathrm{poly}(t) \cdot 2^{-\lambda }\) for allt. For any vectors\(|{v}\rangle , |{w}\rangle \), we refer to the trace distance between\(|{\hat{v}}\rangle ^{\otimes t}\) and\(|{\hat{w}}\rangle ^{\otimes t}\) as the “t-tensored trace distance” between\(|{v}\rangle \) and\(|{w}\rangle \).

An efficiently sampleable distribution is necessarily discrete and supported over a finite segment, whereas the Gaussian distribution is continuous and supported over\((-\infty , \infty )\). Indeed, even in the classical setting Gaussian samplers need to handle this discrepancy. Usually, when one says that it is efficient to sample from the Gaussian distribution, they mean that it is possible to sample to within any polynomial precision and from a Gaussian truncated far enough away from the standard deviation that the probability mass that is chopped off is negligible.^Footnote9 We adopt a similar approach here. Formally, sampling to within a fixed precision is equivalent to sampling from arounded Gaussian distribution, i.e. the distribution obtained by sampling from a continuous Gaussian and then rounding the result to the nearest multiple of\(\epsilon \), where\(\epsilon \) indicates the required precision. Truncation means that we sample from the distribution obtained by sampling a Gaussian, and if the absolute value of the sampled valuex is at most some boundB, then returnx, otherwise return 0. SettingB to be sufficiently larger than the standard deviation, say by roughly a factor ofk, would imply that the resulting distribution only distorts the Gaussian by\(e^{-k^2}\) in total variation distance. We set our samplerg therefore to be a sampler from theB-truncated\(\varepsilon \)-rounded Gaussian distribution. It is possible to sample from a distribution that’s within\(\varepsilon \) statistical distance from this distribution in time\(\mathrm{poly}(\log (1/\epsilon ), \log (B))\) by standard Gaussian sampling techniques, and therefore we can set\(1/\epsilon \) to be a sufficiently large exponential function in\(\lambda , n\) and maintain the efficient sampling property.

The challenge, as already mentioned above, is to translate this intuitive notion of “approximate Gaussian” to one that is provable under tensored trace distance. In fact, we present a general analysis of the effects of truncation and rounding on tensored trace distance. We do this using a two-phase proof.

Part I: Tensored Trace Distance Respects Statistical Distance. We show that truncating a continuous Gaussian introduces negligible trace distance forany number of copiest. This follows quite straightforwardly from the classical total variation distance bound between the distributions. In fact, we show a more general claim (Lemma 4.3): Let\(|{v}\rangle \) and\(|{w}\rangle \) be distributions overn-qubit states, such that their classical distributions as\(2^n\)-dimensional vectors are within classical statistical distance (total variation distance)\(\delta \). Then theirt-tensored trace distance is at most\(\delta \) for allt. The intuition here (which can also be translated to a formal proof), is that even given an infinite number of repetitions, a quantum state does not contain more information than its\(2^n\)-dimensional coefficient vector. Therefore, a (computationally unbounded) adversary that attempts to distinguish\(|{\hat{v}}\rangle ^{\otimes t}\) and\(|{\hat{w}}\rangle ^{\otimes t}\) as quantum states cannot do better than a classical (computationally unbounded) adversary which receives\(|{v}\rangle , |{w}\rangle \) as explicit vectors.

Part II: Tensored Trace Distance Respects Rounding. We say that a distribution\(|{v}\rangle \) is a rounding of a distribution\(|{w}\rangle \) if\(|{v}\rangle \) can be described as first sampling an element from\(|{w}\rangle \) and then applying some mapping\(\varphi \) s.t. for allw,\(\left\| {\varphi (w)-w} \right\| \) is bounded (say be some value\(\delta \)).^Footnote10 We wish to show that if\(|{v}\rangle \) is a rounding of\(|{w}\rangle \) then these vectors are close under tensored trace distance.

Let us start by considering the case\(t=1\), i.e. the distinguisher needs to distinguish between the quantum states\(|{\hat{v}}\rangle \) and\(|{\hat{w}}\rangle \). It is well established that if\(|{\hat{v}}\rangle \) and\(|{\hat{w}}\rangle \) are close in Euclidean distance, then they are also close in trace distance. However, this does not complete the proof since we only have a bound on the Euclidean distance between the unnormalized vectors\(|{v}\rangle \) and\(|{w}\rangle \). Indeed, the notion we care about is the Euclidean distance when projected onto the unit sphere, or in other words theangular distance induced by\(\varphi \). In our case, our distribution\(|{w}\rangle \) (the Gaussian) is such that the norm is quite regular with high probability, and this is preserved also for the rounded version (some straightforward yet fairly elaborate calculation is required in order to establish the exact parameters).^Footnote11

Once we formalize the right notion of approximation (i.e. angular distance), it is possible to state a general lemma (Lemma 4.4) that shows that if\(\varphi \) is s.t. the angular distance between its input and output (over the support of\(|{v}\rangle \)) is bounded, then thet-tensored trace distance degrades moderately witht. Therefore, if we start with a short enough angular distance, our trace distance will indeed be bounded by\(\mathrm{poly}(t)/2^{\lambda }\).

3.1Standard Notions and Notations

During this paper we use standard notations from the literature. For\(n \in {\mathbb {N}}\),

• We denote\([n] := \{1, \cdots , n \}\).

• We denote by\([n]_2\) the\(\left\lceil \log _2(n) \right\rceil \)-bit binary representation ofn.

• We denote by\(\omega _{n}\) the complex root of unity of ordern:\(\omega _{n} := e^{\frac{2\pi i}{n}}\).

• We denote by\(\mathcal{S}(n)\) the set ofn-qubit pure quantum states, by\(\mathcal{D}(n)\) the set ofn-qubit mixed quantum states and by\(\mathcal{U}(n)\) the set ofn-qubit quantum unitary circuits.

• We sometimes denote\(2^n\) withN, when we do that, we explicitly note it.

Vectors and Quantum States. We use standard Dirac notation throughout this paper, vectors are not assumed to be normalized unless explicitly mentioned. Specifically, for a column vector\(u \in {\mathbb {C}}^{m}\), we denote\(|{u}\rangle := u\),\(\langle {u}| := u^{\dagger }\), where\(u^{\dagger }\) is the conjugate transposed ofu. We usually let\(\hat{u}\) denote the normalized version of the vectoru, namely:\(\hat{u} := \frac{1}{\left\| {u} \right\| } \cdot u\) (whereu is a nonzero complex vector). Vectors that represent quantum states have unit norm and therefore are normalized by default.

We make a distinction between avector in a Hilbert space, and thequantum state corresponding to this vector. The two objects are related as a complete characterization of a (pure) quantum state overn-qubits is characterized by a vector in a\(2^n\)-dimensional Hilbert space (up to normalization and global phase). However, the vector is not necessarily (and almost always is not) recoverable given then-qubit state, and quantum states that correspond to different vectors can be indistinguishable (even perfectly).^Footnote12 In terms of vector notation, the symbol\(|{u}\rangle \) can refer either to the vector in the Hilbert space of to the quantum state that corresponds to this vector, we will explicitly mention which of the two we refer to when using this notation.

Distributions Over Quantum States as Density Matrices. Density matrices are a mathematical tool to describe mixed quantum states, that is, distributions over quantum states. Formally, let\(\mu \) a (possibly continuous) probability distribution overn-qubit quantum states,\(\mu : \mathcal{S}(2^n) \rightarrow [0, 1]\),\(\int _{|{\psi }\rangle \in \mathcal{S}(2^n)} 1 \text {d}\mu (|{\psi }\rangle ) = 1\), then the density matrix induced by\(\mu \) is denoted\(\rho _\mu \) and defined as:

Statistical Distance. We use basic properties of the statistical distance metric (also known as total variation distance). Statistical distance can be described in terms of operations, that is, for two (possibly continuous) distributions\(D_1\),\(D_2\) with corresponding supports\(S_1\),\(S_2\), the statistical distance between\(D_1, D_2\) is the maximal advantage,

taken over all functions\(\mathsf {A}: S_1 \cup S_2 \rightarrow \{ 0, 1 \}\). We note that we can allow\(\mathsf {A}\) to be randomized and obtain an equivalent definition. The statistical distance between two random variables is the statistical distance between their associated distributions.

Additionally, throughout the proof of Theorem5.1 we will use the following fact about the statistical distance between a distribution and a conditional version of it.

Fact 3.1

LetX be a random variable andE some probabilistic event. Denote\(Y = X | \bar{E}\), i.e. the conditional variable ofX conditioned onEnot happening. Then

Trace Distance. The trace distance, defined below, is a generalization of statistical distance to the quantum setting and represents the maximal distinguishing probability between distributions over quantum states.

Definition 3.2

(Trace Distance). Let\(\rho _0, \rho _1 \in \mathcal{D}(2^n)\) be two density matrices ofn-qubit mixed states. For a projective measurement\(\mathsf {A}\) with output in\(\{ 0,1 \}\) define

The trace distance between\(\rho _0\),\(\rho _1\) is

We note that the trace distance is often equivalently defined as\(\tfrac{1}{2} \left\| {\rho _0 -\rho _1} \right\| _1\), where\(\left\| {\cdot } \right\| _1\) refers to the\(\ell _1\) norm of the vector of eigenvalues of the operand matrix.

A standard fact about trace distance is the following.

Fact 3.3

Let\(D_0\),\(D_1\) be two distributions overn-qubit states and let\(\rho _0, \rho _1 \in \mathcal{D}(2^n)\) be the corresponding density matrices. For a projective measurement\(\mathsf {A}\) with output in\(\{ -1,1 \}\) define

Then,

The trace distance between pure states is given by the following expression.

Fact 3.4

Forn-qubit pure quantum states\(|{\psi }\rangle , |{\phi }\rangle \), the trace distance between them is:

Trace distance is an operator on density matrices. In this work we will sometimes use it directly on distributions, that is we denote\(\mathrm {TD}(D_1, D_2)\), where\(D_1, D_2\) are distributions overn-qubit quantum states. This notation refers to the trace distance between the two density matrices induced by\(D_1\) and\(D_2\) (as per Eq. (1)). That is,

Quantum Unitary for a Classical Function. Let\(f : \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^m\) be a function. The unitary off is denoted by\(U_f\), it is a unitary over\(n + m\) qubits defined as

Quantum Rejection Sampling. Quantum Rejection Sampling (QRS) is a known efficient procedure for taking one quantum state\(|{\alpha }\rangle \) and outputting with some probability a different quantum state\(|{\beta }\rangle \), given black box access to a circuit that describes their closeness. Formally, the algorithm\(\mathsf {QRS}\) gets as input ann-qubit quantum state\(|{\alpha }\rangle \) and quantum oracle access to a unitaryU on\(n + k\) qubits (wherek is related to the binary description length for complex numbers that is being used) and have the following correctness and time complexity guarantees.

Theorem 3.5

(Quantum Rejection Sampling). Let\(|{\alpha }\rangle , |{\beta }\rangle \) be twon-qubit quantum states and letU be an\((n + k)\)-qubit unitary. Assume there exists a positive real numberd such that the following hold

• \(d \ge \max _{x \in \{ 0, 1 \}n} \left| {\frac{\beta _x}{\alpha _x}} \right| \).

• \(\forall x \in \{ 0, 1 \}^n\), the complex number\(\frac{\left( \beta _x / \alpha _x \right) }{d}\) can be described with full precision ink bits.

• U is the unitary of the classical function\(f : \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^k\) such that\(f(x) := \frac{ \left( \beta _x / \alpha _x \right) }{d}\).

Then\(\mathsf {QRS}^{U}(|{\alpha }\rangle )\) outputs\((\mathtt {success}, |{\beta }\rangle )\) with probability at least\(\frac{1}{d^2}\) and otherwise outputs\((\mathtt {fail}, |{0^n}\rangle )\).

The algorithm makes a single query toU, and assuming this query takes a single time step, the time complexity of\(\mathsf {QRS}^{U}(|{\alpha }\rangle )\) is\(\mathrm{poly}(n, k)\).

3.2Pseudorandom Functions andm-Wise Independent Functions

We define pseudorandom functions with quantum security (QPRFs).

Definition 3.6

(Quantum-Secure Pseudorandom Function (QPRF)). Let\(\mathcal {K}= \{ \mathcal {K}_n \}_{n \in {\mathbb {N}}}\) be an efficiently samplable key distribution, and let\(\mathsf {PRF}= \{ \mathsf {PRF}_n \}_{n \in {\mathbb {N}}}\),\(\mathsf {PRF}_n : \mathcal {K}_n \times \{0,1\}^n \rightarrow \{0,1\}^{\mathrm{poly}(n)}\) be an efficiently computable function, where\(\mathrm{poly}(\cdot )\) is some polynomial. We say that\(\mathsf {PRF}\) is a quantum-secure pseudorandom function if for every efficient non-uniform quantum algorithm\(A = \{ A_n \}_{n \in {\mathbb {N}}}\) (with quantum advice) that can make quantum queries there exists a negligible function\(\mathrm{negl}(\cdot )\) s.t. for every\(n \in {\mathbb {N}}\),

In[Zha12], QPRFs were proved to exist under the assumption that post-quantum one-way functions exist.

We definem-wise independent functions as keyed functions s.t. when the key is sampled from the key distribution, then anym different inputs to the function generatem-wise independent random variables.

Definition 3.7

(m-Wise Independent Function). Let\(n, m, p \in {\mathbb {N}}\), let\(\mathcal {K}\) be a key distribution, and letf,\(f : \mathcal {K}\times \{0,1\}^n \rightarrow \{0,1\}^{p}\) a function.\((f, \mathcal {K})\) is anm-wise independent function if for every distinctm input values\(x_1, \cdots , x_{m} \in \{0,1\}^{n}\),

Based onm-wise independent functions we define efficiently samplablem-wise independent function families.

Definition 3.8

(Efficientm(n)-Wise Independent Function). Letm(n), \(p(n) : {\mathbb {N}}\rightarrow {\mathbb {N}}\) be functions, let\(\mathcal {K}= \{ \mathcal {K}_n \}_{n \in {\mathbb {N}}}\) be an efficiently samplable key distribution, and let\(f = \{ f_n \}_{n \in {\mathbb {N}}}\),\(f_n : \mathcal {K}_n \times \{0,1\}^n \rightarrow \{0,1\}^{p(n)}\) be an efficiently computable function. Then, if for every\(n \in {\mathbb {N}}\),\((f_n, \mathcal {K}_n)\) is anm(n)-independent function, then\((f, \mathcal {K})\) is an efficientm(n)-wise independent function.

3.3Quantum Randomness and Pseudorandomness

The Haar Measure. The Haar measure on quantum states is the quantum analogue of the classical uniform distribution over classical bit strings. That is, it is the uniform (continuous) probability distribution on quantum states. Recall that ann-qubit quantum state can be viewed as a unit vector in\({\mathbb {C}}^{2^n}\), thus the Haar measure onn qubits is the uniform distribution over all unit vectors in\({\mathbb {C}}^{2^n}\). In this work we denote then-qubit Haar distribution with\(\mu _n\). From this point forward we refer to the uniform distribution over quantum states simply as “random”, and don’t mention specifically that it is with respect to the Haar distribution.

Scalable Asymptotically Random State Generators. We propose a scalable variant to the notion of Asymptotically Random State (ARS) generators which was implicitly defined in[JLS18] and explicitly in[BS19]. Previous works consider an ARS generator to be an efficient quantum algorithm\(\mathsf {Gen}\) that gets quantum oracle access to\(U_f : |{x, y}\rangle \rightarrow |{x, y \oplus f(x)}\rangle \) for a random classical functionf, along with a parameter\(n \in {\mathbb {N}}\) that denotes the number of desired output qubits. The guarantee of the ARS generator is that for any polynomialt(n) inn,t(n) outputs from\(\mathsf {Gen}^{U_f}\) (executed with the same functionf) have negligible trace distance (in n) fromt(n)-copies of a randomn-qubit state This means thatn plays two roles, it denotes the number of qubits in the output state but also the security parameter that determines the quality of randomness (i.e. how indistinguishable it is from random).

AScalable ARS generator is one that gets two parameters\(n, \lambda \) instead of one.n, as before, denotes the number of wanted output qubits, and\(\lambda \) is a security parameter, thus a scalable ARS generator eliminates the dependence between state size and security.

Definition 3.9

(Asymptotically Random State (ARS) Generator). A quantum polynomial-time algorithm\(\mathsf {Gen}\) with input\((1^n, 1^\lambda )\) for\(n, \lambda \in {\mathbb {N}}\) and quantum oracle access to\(U_f : |{x, y}\rangle \rightarrow |{x, y \oplus f(x)}\rangle \) for\(f : \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^{\mathrm{poly}(n, \lambda )}\), is an ARS generator if there exists a negligible function\(\mathrm{negl}(\cdot )\) s.t. for every polynomial\(t : {\mathbb {N}}\rightarrow {\mathbb {N}}\), for all natural numbers\(n, \lambda \),

where the distributions\(D_1, D_2\) are defined as follows.

• \(D_1{:} \) Sample\(f \leftarrow \left( \{ 0, 1 \}^{\mathrm{poly}(n, \lambda )} \right) ^{ \{ 0, 1 \}^n }\), perform\(t(\lambda )\) independent executions of\(\mathsf {Gen}^{U_f}(1^n, 1^\lambda )\) and output the\(t(\lambda )\) output quantum states.

• \(D_2{:} \) Sample\(|{\psi }\rangle \leftarrow \mu _n\) a randomn-qubit quantum state, and output\(t(\lambda )\) copies of it:\(|{\psi }\rangle ^{\otimes t(\lambda )}\). Recall that\(\mu _n\) is the Haar measure onn qubits.

We next define (scalable) quantum statet-design generators and (scalable) pseudorandom quantum state (PRS) generators. After defining these, we briefly describe a general and simple reduction structure that shows how to constructt-designs and PRS generators from any ARS generator.

Approximate Quantum State t-Designs. A quantum statet-design[AE07] is a distribution over quantum states that mimics the uniform distribution over quantum states when the number of output copies is restricted tot. A (scalable, approximate) quantum statet-design generator consists of two quantum algorithmsK, G. The key sampler algorithmK samples a classical keyk given two parameters\(1^n, 1^\lambda \) wheren denotes the number of qubits and\(\lambda \) denotes the security parameter. The state generation algorithmG gets a keyk and outputs ann-qubit state\(|{\psi }\rangle \). Informally, the randomness guarantee of at-design generator is that if we sample a keyk once from\(K(1^n, 1^\lambda )\) and then executeG(k)t times and output thet outputs, then this output distribution is going to be indistinguishable fromt copies of ann-qubit quantum state, for unbounded quantum distinguishers. The formal definition follows.

Definition 3.10

(\(\varepsilon (\lambda )\)-Approximate State\(t(\lambda )\)-Design Generator). Let\(\varepsilon (\lambda ): {\mathbb {N}}\rightarrow [0, 1]\),\(t(\lambda ): {\mathbb {N}}\rightarrow {\mathbb {N}}\) be functions. We say that a pair of quantum algorithms (K, G) is an\(\varepsilon (\lambda )\)-approximate state\(t(\lambda )\)-design generator if the following holds:

• Key Generation. For all\(n, \lambda \in {\mathbb {N}}\),\(K(1^n, 1^\lambda )\) always outputs a classical key k.

• State Generation. Givenk in the support of\(K(1^n, 1^\lambda )\) the algorithm\(G(1^n, 1^\lambda , k)\) will always output ann-qubit quantum state.

• Approximate Quantum Randomness. For all\(n, \lambda \in {\mathbb {N}}\),

  $$ \mathrm {TD}\big ( D_1 , D_2 \big ) \le \varepsilon (\lambda )\,, $$

  where the distributions\(D_1, D_2\) are defined as follows.

• \(D_1{:}\) Sample\(k \leftarrow K(1^n, 1^\lambda )\), perform\(t(\lambda )\) independent executions of\(G(1^n, 1^\lambda , k)\) and output the\(t(\lambda )\) output quantum states.

• \(D_2{:}\) Sample\(|{\psi }\rangle \leftarrow \mu _n\) a randomn-qubit quantum state, and output\(t(\lambda )\) copies of it:\(|{\psi }\rangle ^{\otimes t(\lambda )}\).

It is not part of the standard definition, but it is usually the case that the algorithmsK, G execute in time\(\mathrm{poly}(n, \lambda )\), which is going to be the case in this work as well.

Pseudorandom Quantum States. We define scalable Pseudorandom State (PRS) generators. Compared tot-designs, Quantum Pseudorandom State Generators have a slight difference, and formally incomparable randomness guarantee. Mainly, with a PRS we are guaranteed that the output state is going to be indistinguishable for any polynomial number of copies\(t(\lambda )\)without knowing in advance\(t(\lambda )\), however this indistinguishability is onlycomputational. That is, it is only guaranteed that computationally bounded distinguishers will be unable to tell the difference between\(t(\lambda )\) executions of the generator and\(t(\lambda )\) copies of a random quantum state. The scalability property maintains the ability to increase security without increasing the state sizen. We remind that the notion of scalability in PRS generators was not considered in previous works[JLS18,BS19] and thus the following definition differs a bit from the previous definition of a PRS, we view this as the more proper definition.

Definition 3.11

(Scalable Pseudorandom Quantum State (PRS) Generator). We say that a pair of polynomial-time quantum algorithms (K, G) is a Pseudorandom State (PRS) Generator if the following holds:

• Key Generation. For all\(n, \lambda \in {\mathbb {N}}\),\(K(1^n, 1^\lambda )\) always outputs a classical keyk.

• State Generation. Givenk in the support of\(K(1^n, 1^\lambda )\) the algorithm\(G(1^n, 1^\lambda , k)\) will always output ann-qubit quantum state.

• Quantum Pseudorandomness. For any polynomial\(t(\cdot )\) and a non-uniform polynomial-time quantum algorithm\(A = \{ A_\lambda \}_{\lambda \in {\mathbb {N}}}\) (with quantum advice) there exists a negligible function\(\mathrm{negl}(\cdot )\) such that for all\(n, \lambda \in {\mathbb {N}}\),

  $$ \left| {\Pr [A_\lambda \big ( D_1 \big ) = 1] - \Pr [A_\lambda \big ( D_2 \big ) = 1]} \right| \le \mathrm{negl}(\lambda )\, , $$

  where the distributions\(D_1, D_2\) are defined as follows.

• \(D_1{:}\) Sample\(k \leftarrow K(1^n, 1^\lambda )\), perform\(t(\lambda )\) independent executions of\(G(1^n, 1^\lambda , k)\) and output the\(t(\lambda )\) output quantum states.

• \(D_2{:}\) Sample\(|{\psi }\rangle \leftarrow \mu _n\) a randomn-qubit quantum state, and output\(t(\lambda )\) copies of it:\(|{\psi }\rangle ^{\otimes t(\lambda )}\).

Scalable PRS and Quantum Statet-Design Generators from Scalable ARS Generators. We recall a generic transformation from previous works that explain how to construct PRS generators and quantum statet-designs from any ARS generator. We start with the paradigm from[JLS18,BS19] that explains a simple way to turn any ARS generator into a PRS generator.

Lemma 3.12

If there exists a scalable ARS generator and post-quantum one-way functions exist, then there exists a scalable PRS generator.

Proof (Proof Sketch)

The proof follows the same lines as the proof of[BS19, Claim 4, Section 3.1], with the additional scalability property. The key generator\(K(1^n, 1^\lambda )\) of the PRS is the key generator of some quantum-secure pseudorandom function\(\mathsf {PRF}\) with security parameter\(n + \lambda \). For a sampled PRF keyk, the state generator algorithmG simply executes the ARS generator with the pseudorandom function instead of the truly random function,\(G(1^n, 1^\lambda , k) := \mathsf {Gen}^{U_{\mathsf {PRF}_k}}(1^n, 1^\lambda )\). For a polynomial\(t(\cdot )\),\(t(\lambda )\) copies of the generated distribution are computationally indistinguishable (by quantum adversaries) from\(t(\lambda )\) copies of the standard output distribution of the ARS generator, by the security guarantee of the PRF. Additionally,\(t(\lambda )\) copies of the output distribution of the ARS is already known to be indistinguishable (by unbounded distinguishers) from\(t(\lambda )\) copies of a random quantum state, and our proof is concluded.

Also, we follow the observation from[BS19] that explains how an ARS generator implies the existence oft-designs (with depth that has logarithmic dependence ont).

Lemma 3.13

Assume there exists a scalable ARS generator with the following properties:

• The generator is implemented by a circuit of depth\(T(n, \lambda )\).

• For all\(n, \lambda , t\) its output is\(\varepsilon (n, \lambda , t)\)-indistinguishable from at-tensor of a randomn-qubit state.

Then there exists an\(\varepsilon (n, \lambda , t)\)-approximate scalablet-design generator, which is implementable by circuits of depth

Proof (Proof Sketch)

The proof is similar to the explanation in[BS19, Section 3.2], with slight differences and an additional consideration of the scalability property. The key generator\(K(1^n, 1^\lambda )\) of thet-design samples an efficientm-wise independent function\(\tilde{f}\), where\(m := 2t\cdot T(n, \lambda )\). The state generator algorithmG executes the ARS generator with the function\(\tilde{f}\) instead with the truly random function,\(G(1^n, 1^\lambda , \tilde{f}) := \mathsf {Gen}^{U_{\tilde{f}}}(1^n, 1^\lambda )\). By[Zha12, Fact 2], The behavior of any quantum algorithm making at mostm quantum queries to a 2m-wise independent function is identical to its behavior when the queries are made to a random function. Therefore if we maket executions of\(G(1^n, 1^\lambda , \tilde{f})\), each of which makes at most\(T(n, \lambda )\) queries to\(U_{\tilde{f}}\), then the output distribution of the algorithm\(G(1^n, 1^\lambda , \tilde{f})\) is the same as that produced by the ARS generator (when it uses a truly random function). Since the classical depth of anm-wise independent function onn bits is\(\log (n) \cdot \log (m)\), the proof follows (see elaboration on the classical depth ofm-wise independent functions in[BS19, Section 3.2]).

3.4The Continuous Gaussian and Rounded Gaussian Distributions

In this work we will work with distributions related to the Gaussian distribution over\({\mathbb {R}}\) denoted\(\mathcal {N}(0, 1)\), also known as the normal distribution having a mean of 0 and variance of 1. More specifically we will consider the complex Gaussian distribution over\({\mathbb {C}}\), denoted\(\mathcal {N}^{{\mathbb {C}}}(0, 1)\), where both real and imaginary parts of a complex number are sampled independently from\(\mathcal {N}(0, 1)\).

Rounded Gaussian Distribution. The true Gaussian distribution is continuous and we cannotexactly sample from it. Instead, we will use a discrete distribution that we can efficiently sample from. There are quite a few versions of distributions that are discretezations of the Gaussian distribution. In this work we use the rounded Gaussian distribution, which we denote by\(\mathcal {N}^{{\mathbb {C}}}_{\text {R}\left( {\varepsilon , B} \right) }(0, 1)\). This distribution is parameterized by\(\varepsilon = 2^{-m} > 0\) (for some\(m \in {\mathbb {N}}\)) and by\(B \in {\mathbb {N}}\), whereB is some integer multiple of\(\varepsilon \).

To define the distribution\(\mathcal {N}^{{\mathbb {C}}}_{\text {R}\left( {\varepsilon , B} \right) }(0, 1)\) we first define the rounding function\(R_{(\varepsilon , B)}(\cdot )\). For a number\(x \in {\mathbb {R}}\), if\(|x| > B\) then\(R_{(\varepsilon , B)}(x) := 0\), and otherwise\(R_{(\varepsilon , B)}(x)\) roundsx up (in absolute value) to the nearest multiple of\(\varepsilon \). Formally, if\(|x| \le B\) then\(R_{(\varepsilon , B)}(x)\) is the number\(y \in {\mathbb {R}}\) that has minimal absolute value and s.t. both\(|x| \le |y|\),\(\exists k \in {\mathbb {Z}}: y = k\cdot \varepsilon \). For a complex number\(z \in {\mathbb {C}}\),\(R_{(\varepsilon , B)}(z)\) is just applying\(R_{(\varepsilon , B)}(\cdot )\) to both real and imaginary parts ofz.

We define\(\mathcal {N}^{{\mathbb {C}}}_{\text {R}\left( {\varepsilon , B} \right) }(0, 1)\) to be the output distribution of the following process: Sample\(z \leftarrow \mathcal {N}^{{\mathbb {C}}}(0, 1)\) and output\(R_{(\varepsilon , B)}(z)\). The output of\(\mathcal {N}^{{\mathbb {C}}}_{\text {R}\left( {\varepsilon , B} \right) }(0, 1)\) is specified by a number between 0 andB with precision\(\varepsilon = 2^{-m}\), thus the output length in bits is bounded by\(m + \left\lceil \log _2(B) \right\rceil \).

We use the following standard fact about (classical) Gaussian sampling.

Fact 3.14

(Efficient Rounded Gaussian Sampling). There is a sampling algorithm\(G^{{\mathbb {C}}}_{\text {R}\left( {} \right) }\) that takes\(1^m, B\) (and random tape) as input, runs in polynomial time, i.e.\(\mathrm{poly}(m, \log B)\), and samples from a distribution that has statistical distance at most\(2^{-m}\) from the rounded Gaussian distribution\(\mathcal {N}^{{\mathbb {C}}}_{\text {R}\left( {2^{-m}, B} \right) }(0, 1)\).

4.1State Generation of Balanced Vectors

In this subsection we describe a simple procedure that given quantum oracle access to the entries of some general, not necessarily normalized vector\(v \in {\mathbb {C}}^{2^n}\), generates then-qubit quantum state\(|{v}\rangle \) that corresponds to (the normalization of)v. More formally, the procedure gets two pieces of information aboutv:

• Quantum oracle access to\(U_v\), the unitary of the classical function\(v : \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^k\) (wherek is the description size in bits of each entry ofv) that describes the vectorv and maps\(v(x) := v_x\).

• An upper bound\(M \in {\mathbb {N}}\) on any entry ofv, that is,\(\max _{x \in [N]}|v_x| \le M\).

The procedure runs in time\(\mathrm{poly}(n, k, \log M)\) and outputs the quantum state\(|{v}\rangle \) as follows.

\(\mathsf {BVS}^{U_v} \left( M \right) {:}\)

1. 1.

   Define the quantum unitary\(U_{\tilde{v}}\) which is the unitary of the classical function\(\tilde{v} : \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^{k + \log (M)}\) that maps\(\tilde{v}(x) := v_x\cdot \frac{1}{M}\). It’s trivial to simulate\(U_{\tilde{v}}\) given\(U_v\): Given a query\(|{x, y}\rangle \), we concatenate an ancilla of zeros and apply\(U_v\) to get\(|{x, y, v_x}\rangle \), then apply a simple unitary that multiplies by\(\frac{1}{M}\) (on the last register as input and on the second register as output) to obtain\(|{x, y \oplus v_x \cdot \frac{1}{M}, v_x}\rangle \), and then use\(U_v\) again to uncompute the last register.

2. 2.

   Execute quantum rejection sampling,\(\left( b \, , \, |{\hat{v}}\rangle \right) \leftarrow \mathsf {QRS}^{U_{\tilde{v}}}\left( |{+}\rangle ^{\otimes n} \right) \) (see specification of\(\mathsf {QRS}\) in Theorem 3.5). If\(b = \mathtt {fail}\) then output\(\mathtt {fail}\), otherwise output\(|{\hat{v}}\rangle \).

Claim 4.1

(\(\mathsf {BVS}\)Success Probability). If\(\max _{i \in [N]}|v_i| \le M\) then the execution\(\mathsf {BVS}^{U_v}(M)\) always outputs either\(\mathtt {fail}\) or the quantum state\(v \cdot \frac{1}{\left\| {v} \right\| } = |{\hat{v}}\rangle \), furthermore the execution succeeds and outputs the quantum state\(|{\hat{v}}\rangle \) with probability at least\(\frac{\left\| {v} \right\| ^2}{M^2\cdot N}\).

Proof

We need to make sure that we execute the quantum rejection sampling algorithm\(\mathsf {QRS}\) with correct parameters (specified in Theorem 3.5), and also understand what exactly are the parameters for\(\mathsf {QRS}\). As the starting state\(|{\alpha }\rangle \) we input\(|{+}\rangle ^{\otimes n}\), our target state\(|{\beta }\rangle \) is\(|{\hat{v}}\rangle =\tfrac{|{v}\rangle }{\left\| {v} \right\| }\). As the state transformation unitaryU we use\(U_{\tilde{v}}\), that is, the unitary of the classical function\(f(x) := v_x \cdot \frac{1}{M}\).

It follows that there exists an upper bound\(d \ge \max _{x \in \{ 0, 1 \}n} \left| {\frac{\beta _x}{\alpha _x}} \right| \) s.t.\(\forall x \in \{ 0, 1 \}^n : f(x) := f(x) := v_x \cdot \frac{1}{M} = \frac{\beta _x / \alpha _x}{d}\), by taking\(d := \frac{M \cdot \sqrt{N}}{\left\| {v} \right\| }\).

• d is indeed an upper bound:

  $$ \forall x \in \{ 0, 1 \}^n : \left| {\frac{\beta _x}{\alpha _x}} \right| = \left| {\frac{v_x / \left\| {v} \right\| }{1 / \sqrt{N}}} \right| = \left| {v_x \cdot \frac{\sqrt{N}}{\left\| {v} \right\| }} \right| \le \frac{M \cdot \sqrt{N}}{\left\| {v} \right\| }\,. $$

• \(f(\cdot )\) indeed computes\(\frac{\beta _x}{\alpha _x}/d\):

  $$\begin{aligned} \forall x \in \{ 0, 1 \}^n : f(x)&:= v_x \cdot \frac{1}{M} \\&= v_x \cdot \frac{1}{M} \cdot \frac{\sqrt{N}}{\sqrt{N}} \cdot \frac{\left\| {v} \right\| }{\left\| {v} \right\| } \\&= \left( \frac{v_x}{\left\| {v} \right\| } \cdot \sqrt{N} \right) \cdot \left( \frac{1}{M} \cdot \frac{\left\| {v} \right\| }{\sqrt{N}} \right) \\&= \frac{\left( \frac{v_x / \left\| {v} \right\| }{1 / \sqrt{N}} \right) }{\left( \frac{M \cdot \sqrt{N}}{\left\| {v} \right\| } \right) } \\&= \frac{\beta _x / \alpha _x}{d}\,. \end{aligned}$$

The conditions for\(\mathsf {QRS}\) hold, and thus from the correctness guarantee of quantum rejection sampling we can be sure that the algorithm\(\mathsf {BVS}\) will always output either\(\mathtt {fail}\) or\(|{\beta }\rangle := |{\hat{v}}\rangle \). As for the probability of success in outputting\(|{\hat{v}}\rangle \), again from the success guarantees of\(\mathsf {QRS}\) this probability is at least\(\frac{1}{d^2} = \frac{\left\| {v} \right\| ^2}{M^2\cdot N}\).

The above procedure tries to generate\(|{\hat{v}}\rangle \) once and it will be convenient to have an amplified version of this algorithm as a black box, this is an option because we can always re-generate the state\(|{+}\rangle ^{\otimes n}\) efficiently and retry. The amplified version of the algorithm is with the same name and have one more parameter\(k \in {\mathbb {N}}\) (amplification parameter), that is,\(\mathsf {BVS}^{U_v}(M, k)\).

The amplified version of\(\mathsf {BVS}\) executesk (parallel) repetitions of\(\mathsf {BVS}^{U_{v}}(M)\), if all fail it outputs\(\mathtt {fail}\), and if either succeeds it outputs the generated state\(|{\hat{v}}\rangle \). The probability of\(\mathsf {BVS}^{U_v}(M, k)\) to succeed in generating the state\(|{\hat{v}}\rangle \) follows.

Claim 4.2

(Amplified\(\mathsf {BVS}\)Success Probability). If\(\max _{i \in [N]}|v_i| \le M\) then the algorithm\(\mathsf {BVS}^{U_v}(M, k)\) always outputs either\(\mathtt {fail}\) or the quantum state\(v \cdot \frac{1}{\left\| {v} \right\| } = |{\hat{v}}\rangle \), furthermore the algorithm succeeds and outputs the quantum state\(|{\hat{v}}\rangle \) with probability at least\(1 - e^{-\frac{k \cdot \left\| {v} \right\| ^2}{M^2\cdot N}}\).

Proof

4.2Analytic Tools for Distributions

In this subsection we describe some analytic tools for bounding trace norm between two distributions, for multiple output copies. We start with an elementary property of trace distance and classical statistical distance that we will use in our construction.

Lemma 4.3

(Classical Statistical Distance Implies Trace Distance). Let\(n \in {\mathbb {N}}\) and let\(D_1\),\(D_2\) be two distributions over unit vectors in\({\mathbb {C}}^{2^n}\). Let\(\tilde{D_1}\),\(\tilde{D_2}\) be the quantum-state distributions of\(D_1\),\(D_2\), that is, for\(b \in \{ 0, 1 \}\), a sample from\(\tilde{D_b}\) is generated by sampling a vectorv from\(D_b\), and outputting ann-qubit register in the state described byv.

Then, if\(\mathrm {SD}(D_1, D_2) \le \varepsilon \), then for every number of copies\(t \in {\mathbb {N}}\),

Proof

Intuitively, the proof follows from the fact that a computationally unbounded mapping can always capture the computation of an (even unbounded) quantum process, along with the fact that when the classical description of a state is available then there is no advantage in having more than a single copy. Formally, we assume towards contradiction there is a projective measurement\(\mathsf {A}\) (with output in\(\{ 0, 1 \}\)) that distinguishes between at-tensor of\(\tilde{D_1}\) and at-tensor of\(\tilde{D_2}\) with advantage bigger than\(\varepsilon \), and describe a (randomized) distinguisher\(\mathsf {A}' : {\mathbb {C}}^{2^n} \rightarrow \{ 0, 1 \}\) that distinguishes between\(D_1, D_2\) with advantage bigger than\(\varepsilon \). LetA denote the Hermitian matrix that corresponds to the projective measurement\(\mathsf {A}\).

The distinguisher\(\mathsf {A}'\) is defined as follows. Given an input\(v \in {\mathbb {C}}^{2^n}\), consider the vector\(|{v'}\rangle = |{v}\rangle ^{\otimes t}\), and compute the value\(p = \langle {v'}| A |{v'}\rangle \). We note that this value is exactly the probability that\(\mathsf {A}\) outputs 1 when input the quantum state\(|{v}\rangle ^{\otimes t}\). The distinguisher\(\mathsf {A}'\) then outputs 1 with probabilityp and 0 with probability\(1-p\). By definition, the advantage of\(\mathsf {A}'\) in distinguishing\(D_1\) and\(D_2\) is identical to the advantage of\(\mathsf {A}\) in distinguishing thet-tensored\(\tilde{D_1}\) and\(\tilde{D_2}\).

Robustness to Small Shifts. Lemma 4.3 asserts that distributions on quantum states are indistinguishable if they are induced by indistinguishable distributions over vectors in the respective Hilbert space. This is a very strict condition and in fact in many cases distributions on quantum states can be indistinguishable even if the respective distributions over vectors are highly distinguishable.

This will be useful in the context of this work since we wish to show indistinguishability between the Haar random distribution, which corresponds to a continuous distribution over the sphere, and an efficiently samplable distribution (with oracle access to a random function), which necessarily produces a discrete distribution over vectors. Hence, the two distributions over vectors are necessarily distinguishable (with advantage 1), and yet we will be able to bound the distinguishing gap between the quantum states.

Technically, we rely on the well known property that quantum states that correspond to vectors with inner product close to 1 are indistinguishable. This is formalized in Lemma4.4 below, which considers a distribution over vectors, and a small perturbation of this distribution, that does not shift the vector by too much. We show that such perturbation, which in particular captures the case of rounding a continuous distribution into some discrete domain, would be indistinguishable in terms of the resulting quantum state.

Lemma 4.4

(Angular Indistinguishability). Let\(n \in {\mathbb {N}}\),\(\varepsilon \in [0, 1]\), letD be a distribution over (not necessarily normalized) vectors in\(V \subseteq {\mathbb {C}}^{2^n}\), let\(\varphi : V \rightarrow {\mathbb {C}}^{2^n}\) be a function and let\(\hat{\varphi } : V \rightarrow {\mathbb {C}}^{2^n}\) be the normalized version of\(\varphi \),\(\hat{\varphi }(v) := \frac{\varphi (v)}{\left\| {\varphi (v)} \right\| }\). Assume that for every\(v \in V\), the normalization ofv and its\(\hat{\varphi }\)-image are close on the unit sphere, that is,

then for all\(t \in {\mathbb {N}}\),

In the original version of this work, the above lemma was proven using a proof different from the one below. We thank the CRYPTO reviewer for suggesting the simplified proof presented below.

Proof

The lemma follows since

where the first inequality follows from the convexity of trace distance, the second follows from the relation between trace distance and fidelity\(\mathrm {TD}(\rho , \sigma ) \le \sqrt{1- F(\rho , \sigma )}\) and the fact that for pure states\(|{u}\rangle , |{v}\rangle \) the Fidelity is\(\left| {\langle {u}|{v}\rangle } \right| ^2\), and the last inequality follows from Bernoulli’s inequality which implies\(\left( 1 - \varepsilon \right) ^{2\cdot t} \ge 1 - 2t\varepsilon \).

In this section we describe a procedure that given quantum oracle access to a random classical function, efficiently samples random quantum states that are arbitrarily random (i.e. we can scale up the randomness of our sampled state and make it increasingly harder to distinguish from a random quantum state, for an increasing number of output copies, without increasing the number of qubits in the state) and can generate multiple copies of a state when executed multiple times with oracle access to the same function. More formally, we describe a sampling procedure with the following inputs:

• \(1^n\): Number of wanted qubits in the output state.

• \(1^\lambda \): Security parameter that measures “how random” the output state is going to be (i.e. how hard will it be to distinguisht copies of the sampled state fromt copies of a random quantum state, as a function of\(\lambda , t\)).

• Quantum oracle access to\(U_f\): For a function\(f: \{ 0, 1 \}^{n} \rightarrow \{ 0, 1 \}^{\mathrm{poly}(n, \lambda )}\) (for some polynomial\(\mathrm{poly}(\cdot )\), specified later), the sampling procedure gets oracle access to the unitary mapping\(U_f\) off.

The formal statement that explains how to construct a scalable ARS generator follows.

Theorem 5.1

(Scalable ARS Generator Construction). There exists a scalable ARS generator\(\mathsf {Gen}\) that for every\(n \in {\mathbb {N}}\) number of qubits,\(5 \le \lambda \in {\mathbb {N}}\) security parameter and\(t \in {\mathbb {N}}\) number of copies, satisfies the following trace distance bound,

where the distributions\(D_1, D_2\) are defined as follows:

• \(D_1{:}\) Sample\(\tilde{f} \leftarrow \left( \{ 0, 1 \}^{\mathrm{poly}(n, \lambda )} \right) ^{\{ 0, 1 \}^{n}}\), executet times the generation algorithm\(\mathsf {Gen}^{U_{\tilde{f}}}(1^{n}, 1^{\lambda })\) and output thet output states.

• \(D_2{:}\) Sample\(|{\psi }\rangle \) a randomn-qubit state and output\(|{\psi }\rangle ^{\otimes t}\).

Proof

We start with describing the procedure of\(\mathsf {Gen}^{U_{\tilde{f}}}(1^n, 1^\lambda )\). First, we denote\(\varepsilon := 2^{-n-\lambda }\),\(B := \left\lceil 2\sqrt{n + \lambda } \right\rceil \) and set the polynomial\(\mathrm{poly}(n, \lambda )\) that denotes the output size of\(\tilde{f}\) to be\(\lambda \cdot r(\varepsilon , B)\), where\(r(\varepsilon , B)\) is the randomness complexity of the rounded Gaussian sampler\(G^{{\mathbb {C}}}_{\text {R}\left( {\varepsilon , B} \right) }\). Given the oracle access to\(\tilde{f} \in \left( \{ 0, 1 \}^{\lambda \cdot r(\varepsilon , B)} \right) ^{\{ 0, 1 \}^{n}}\), the algorithm starts with deciding on a different function\(f \in \left( \{ 0, 1 \}^{r(\varepsilon , B)} \right) ^{\{ 0, 1 \}^{n}}\) that it is going to use.

In what follows, denote\(N := 2^n\), for a function\(h \in \left( \{ 0, 1 \}^{r(\varepsilon , B)} \right) ^{\{ 0, 1 \}^{n}}\) denote by\(v^h\) the vector that is created by rounded Gaussian sampling withh, that is,\(\forall x \in \{ 0, 1 \}^n, v^h_x := G^{{\mathbb {C}}}_{\text {R}\left( {\varepsilon , B} \right) }(h(x))\). We think of\(\tilde{f}\), that has an output length of\(\lambda \cdot r(\varepsilon , B)\), as\(\lambda \) different functions, each having an output length of\(r(\varepsilon , B)\). Specifically, for\(i \in [\lambda ]\) define the function\(f_i \in \left( \{ 0, 1 \}^{r(\varepsilon , B)} \right) ^{\{ 0, 1 \}^{n}}\) as the function that for input\(x \in \{ 0, 1 \}^n\) outputs thei-th packet of\(r(\varepsilon , B)\) bits from\(\tilde{f}(x)\).

The procedure of\(\mathsf {Gen}\) follows.

1. 1.

   Decide on a function\(f \in \left( \{ 0, 1 \}^{r(\varepsilon , B)} \right) ^{\{ 0, 1 \}^{n}}\):

   • If\(N > \lambda \), we actually use only the first\(r(\varepsilon , B)\) bits of the output of\(\tilde{f}\). That is,f is simply\(f_1\).

   • If\(N \le \lambda \), iterate for\(i \in [\lambda ]\):

   • Compute the vector\(v^{f_{i}}\) by applying\(G^{{\mathbb {C}}}_{\text {R}\left( {\varepsilon , B} \right) }\) to each of theN outputs of\(f_i\). If\(\left\| {v^{f_i}} \right\| \ge \frac{\sqrt{N}}{2}\), denote\(f := f_i\) and halt the loop.^Footnote13

   If you executed all iterations and did not get a function\(f_i\) s.t.\(\left\| {v^{f_i}} \right\| \ge \frac{\sqrt{N}}{2}\), halt and output\(|{0^{n}}\rangle \) (as a sign of failure).

2. 2.

   Givenf execute\(\mathsf {BVS}^{U_{v^f}}(\sqrt{2}\cdot B, 8\cdot \lambda \cdot B^2)\) and output then-qubit quantum state generated by\(\mathsf {BVS}\).

The full analysis and the rest of the proof, showing why at-tensor of the output of the generator (i.e. the distribution\(D_1\)) and at-tensor of a random quantum state (i.e. the distribution\(D_2\)) are indistinguishable, is in the full version of this work^Footnote14.