SSupplementary Material References

# Efficient Construction of Quantum Physical Unclonable Functions with Unitary
t-designs

Niraj Kumar<EMAIL_ADDRESS>School of Informatics, University of Edinburgh,
EH8 9AB, United Kingdom  Rawad Mezher<EMAIL_ADDRESS>School of Informatics,
University of Edinburgh, EH8 9AB, United Kingdom  Elham Kashefi
<EMAIL_ADDRESS>School of Informatics, University of Edinburgh, EH8 9AB,
United Kingdom  CNRS, LIP6, Sorbonne Université, 4 place Jussieu, 75005 Paris,
France

###### Abstract

Quantum physical unclonable functions, or QPUFs, are rapidly emerging as
theoretical hardware solutions to provide secure cryptographic functionalities
such as key-exchange, message authentication, entity identification among
others. Recent works have shown that in order to provide provable security of
these solutions against any quantum polynomial time adversary, QPUFs are
required to be a unitary sampled uniformly randomly from the Haar measure.
This however is known to require an exponential amount of resources. In this
work, we propose an efficient construction of these devices using unitary
$t$-designs, called $\textsf{QPUF}_{t}$. Along the way, we modify the existing
security definitions of QPUFs to include efficient constructions and showcase
that $\textsf{QPUF}_{t}$ still retains the provable security guarantees
against a bounded quantum polynomial adversary with $t$-query access to the
device. This also provides the first use case of unitary $t$-design
construction for arbitrary $t$, as opposed to previous applications of
$t$-designs where usually a few (relatively low) values of $t$ are known to be
useful for performing some task. We study the noise-resilience of
$\textsf{QPUF}_{t}$ against specific types of noise, unitary noise, and show
that some resilience can be achieved particularly when the error rates
affecting individual qubits become smaller as the system size increases. To
make the noise-resilience more realistic and meaningful, we conclude that some
notion of error mitigation or correction should be introduced.

##  1 Introduction

The need for performing the secure exchange of communication, even in presence
of adversaries, has motivated a rich field of cryptography. In its early form,
cryptography was mostly concerned with creating ciphertexts that could not be
inverted by an enemy eavesdropper. The initial form of cryptography was only
based on heuristics and ad-hoc approaches. But with the rise of modern
cryptography courtesy Claude Shannon 1, systematic mathematical approaches
leading to rigorous security definitions and cryptanalysis has come into
prominence. Modern cryptography constructs and analyses protocols against a
third party trying to obtain relevant information of the protocol, and
provides security in the form of confidentiality, data integrity,
authentication, non-repudiation among others 2, 3, 4.

With the advent of internet, information security has become a central talking
point and substantial works have gone into proposing cost-effective solutions
across distributed networks. An important result in this direction by Canetti
and Fishelin states that it is impossible to achieve secure classical
cryptographic protocols in practice without making any assumptions on the
setup 5. This result has motivated a new line of research on designing both
classical and quantum protocols based on hardware assumptions. An emerging
outcome of this is the proposal of quantum physical unclonable function, also
called QPUF 6, 7, 8, 9, 10, 11. These are hardware devices that utilise the
properties of quantum mechanics and the random physical disorders that occur
in the manufacturing process to construct secure devices. The randomness
ensures that the device has the desired security feature of high min-entropy,
thus ensuring no dependency on extra cryptographic properties or assumptions.
A QPUF is accessed by querying it with a _quantum challenge_ , (for example,
the quantum state in the form of an electrical signal, an optical pulse,
temperature signal, etc.) and obtaining a recognisable _response_ that is
robust for a particular QPUF token but highly variable for different but very
similar QPUFs such that each token seems to output a random response. Each
QPUF has a unique identifier associated with it which denotes specific
randomisation used in its creation.

Multiple theoretical and experimental constructions of QPUF have been proposed
to date. These include the _quantum read-out PUF_(QR-PUF) where the underlying
system is a quantum device but the challenges and responses are classical
data. The proposal of QR-PUF included the works of Skoric et. al 7,
Nikolopoulos et. al 9, Gianfelici et. al 10, and Young et. al 8. The limiting
factor in all the above proposals is that they provide the security against
only specific bounded adversary attacks such as intercept-resend 7,
approximate quantum cloning 12, and challenge estimation attacks 13. This was
addressed by the works of Arapinis et. al 6 who formalised the definition of
QPUF as a unitary transformation which satisfies the standard completeness
requirements of robustness, uniqueness, and collision-resistance, and thus
ensures the crucial security property of unknownness (high-min entropy) which
is a primary requirement in building any provably-secure cryptographic
protocol. An interesting result that they showed is that in order to prove the
unknownness property against any quantum polynomial time (QPT) adversary, the
QPUF unitary needs to be sampled uniformly randomly from the Haar measure. The
authors however did not prove the crucial uniqueness property - a requirement
that allow producing multiple QPUFs sufficiently distinguishable from each
other.

Here, we first address this issue by proving the uniqueness property for
unitaries sampled from the Haar measure. This shows that such a construction
would indeed be a good candidate construction, as random sampling from the
Haar measure produces maximum _single-shot_ distinguishable QPUFs with an
exponentially (in the device size) high probability. This Haar random sampling
construction is however not practically motivated as the resources required in
the construction of such a QPUF scales exponentially in the input size 14.

The second part of this work overcomes this exponential requirement in the
resources by constructing the quantum physical unclonable functions using
approximate unitary $t$-designs 15, 16. We refer to this as
$\textsf{QPUF}_{t}$. These unitary designs have the property that they mimic
sampling from the Haar measure on the unitary group up to $t$-th order, but
can nevertheless be generated efficiently using quantum circuits of relatively
simple structure, and circuit depth scaling polynomially with the input size
and the order $t$ of the design. Unitary $t$-designs have found multiple
applications including efficient benchmarking of quantum systems via
randomised benchmarking 17, constructing secure private channels 18, modeling
black holes 19, and in providing candidates for devices to exhibit
computational speedup using quantum resources 20, 21, 22. Our work provides
yet another application of these designs in the field of quantum cryptography.
Contrary to the previous applications where designs with low $t$ values
suffice, we provide, to the best of our knowledge, the first use case of
constructing a unitary $t$-design for arbitrary $t$ in a sense that higher the
$t$ value, the security of protocols with $\textsf{QPUF}_{t}$ can be analysed
with higher resourced adversaries.

Our candidate construction for $\textsf{QPUF}_{t}$ is based on the random
quantum circuit model (RQC) for generating approximate unitary $t$-designs
originally proposed in 23, but uses at its core a relaxation of technical
requirements for RQC recently introduced in 24. Our construction has a more
natural interpretation in the measurement-based model for quantum computing 25
(MBQC); as it can be viewed as performing random single qubit $XY$ plane
measurements chosen from the interval $[0,2\pi]$ on the non-output qubits of a
regularly structured graph state. Equivalently, as in 22, 26, our construction
can be viewed as a $constant$ $depth$ 2D nearest-neighbour circuit, making its
implementation tailor-made on noisy intermediate scale devices 27. To avoid
any confusion and back and forth translations between circuit model and MBQC,
in this work we view our construction only as a RQC, that is, a 1D circuit
composed of nearest neighbour two-qubit gates and scaling depth.

We base the security of our $\textsf{QPUF}_{t}$ construction in the standard
game based model as proposed in 6. This involves a manufacturer of the
$\textsf{QPUF}_{t}$ device, clients who intend to use it for their desired
task (authentication, key exchange etc.), and a bounded quantum polynomial
(BQP) adversary who is allowed limited query access to the device during its
transition from the manufacturer to the clients and in between clients. In our
work, the security is provided against this adversary and we assume that the
manufacturer and the clients are curious but behave honestly. This is a
practically motivated setting where the manufacturer intends to establish a
secure task with the legitimate clients and wants to prevent impostors from
getting valuable secret information of the task. As an example, a smart-phone
company could insert the $\textsf{QPUF}_{t}$ chip with the intention that only
the legitimate user can unlock the smart-phone with their fingerprint
credential, and no impostor can get into the system without a valid
fingerprint.

In this work, we show that our $\textsf{QPUF}_{t}$ device construction
satisfies the standard security requirements of robustness, uniqueness and
collision resistance. In particular, we provide numerical evidence of our
construction exhibiting uniqueness- an essential property to mass produce
multiple devices such that they are sufficiently distinguishable to each
other. Further, we show that a $\textsf{QPUF}_{t}$ is _practically unknown_ to
a BQP adversary with limited query access to the device. In order to do so, we
modify the existing unknownness criteria introduced by 6 to allow for
efficient constructions of such devices. This is a crucial result for the
security of any protocol built on top of $\textsf{QPUF}_{t}$ as this enables
one to restrict the knowledge that the BQP adversary can gain about the device
and thus ensuring that secure protocols can be built on top of it. Another
important security issue that one needs to take into consideration is the
effect of experimental imperfections the device construction. We show that as
long as the imperfection during preparation is restricted to the unitary
noise, our noisy device still exhibits all the desired security properties.

We organise this paper in the following manner. Section 2 provides the
necessary ingredients required for our work including providing formal
definition of a QPUF. We talk about the distance measures and also provide a
brief introduction into $t$-designs. Next we revisit the QPUF proposal of
Arapinis et. al 6 in section 3 and prove an essential property of uniqueness
which was not proven in the previous work. Section 4 introduces the
$\textsf{QPUF}_{t}$ with an explicit construction and proves the required
security properties including robustness, collision resistance and uniqueness.
Further, we provide a new _practical_ definition of unknownness of QPUF to
allow for efficient constructions of these devices. Next, in section 5 we
allow for imperfections in $\textsf{QPUF}_{t}$ preparation and show that it is
still secure against any BQP adversary with limited query access to the
device. Finally, we conclude in section 6 with some important take away from
our work.

##  2 Ingredients

This section provides the important tools required construction of
$\textsf{QPUF}_{t}$. We provide a brief formal definition of a QPUF and a
brief introduction into unitary $t$-designs.

###  2.1 Quantum Physical Unclonabe Functions

A quantum PUF, or QPUF, is a secure hardware cryptographic device which
utilises the property of quantum mechanics 6. Similar to a classical PUF 28, a
QPUF is assessed via challenge and response pairs (CRP). However, in contrast
to a classical PUF where the CRPs are classical states, the QPUF CRPs are
quantum states.

A QPUF involves a manufacturing process with a quantum generation algorithm,
QGen, which takes as an input a security parameter $\lambda$ and generates a
PUF with a unique identifier id,

$\textsf{QPUF}_{\textbf{id}}\leftarrow\textsf{QGen}(\lambda)$ (1)

Next we define the mapping provided by $\textsf{QPUF}_{\textbf{id}}$ which
takes any input quantum state $\rho_{in}\in\mathcal{H}^{d_{in}}$ to the output
state $\rho_{out}\in\mathcal{H}^{d_{out}}$. Here $\mathcal{H}^{d_{in}}$ and
$\mathcal{H}^{d_{out}}$ are the input and output Hilbert spaces respectively
corresponding to the mapping that $\textsf{QPUF}_{\textbf{id}}$ provides. This
process is captured by the QEval algorithm which takes as an input a unique
$\textsf{QPUF}_{\textbf{id}}$ device and the state $\rho_{in}$ and produces
the state $\rho_{out}$,

$\rho_{out}\leftarrow\textsf{QEval}(\textsf{QPUF}_{\textbf{id}},\rho_{in})$
(2)

It is essential for any cryptographic device to satisfy the correctness and
soundness properties. Correctness property ensures that in absence of any
adversary, the device validates the honest behaviour with probability close to
1 in the security parameter. Soundness property ensures that the device
invalidates the success of any malicious behaviour with probability close to 1
in the security parameter. A QPUF is labelled well constructed if it satisfies
these desired properties. The correctness property is characterised by there
requirements: robustness, collision-resistance, and uniqueness.

1\. _Robustness_ : This property is characterised by the indistinguishability
of output responses generated by the QPUF. It ensures that if the QPUF is
queried separately with two input quantum states $\rho_{in}$ and $\sigma_{in}$
that are $\delta_{r}$-indistinguishable to each other in the fidelity measure,
then the output quantum states $\rho_{out}$ and $\sigma_{out}$ must also be
$\delta_{r}$-indistinguishable,

$\text{Pr}[\textsf{F}(\rho_{out},\sigma_{out})\geqslant
1-\delta_{r}|\textsf{F}(\rho_{in},\sigma_{in})\geqslant 1-\delta_{r}]\geqslant
1-\epsilon(\lambda)$ (3)

where $\epsilon(\lambda)$ is a negligible quantity dependent on the desired
security parameter. Here $\delta$\- indistinguishability for any two quantum
states $\rho$ and $\sigma$ is defined as $\textsf{F}(\rho,\sigma)\leqslant
1-\delta$, where $\textsf{F}(\rho,\sigma)$ is the fidelity distance measure
between the quantum states. Alternatively, other distance measures such as
trace norm, euclidean norm (shatten-p norm) can also be used to define
security requirements for QPUF.

2\. _Collision Resistance_ : This property is characterised by the
distinguishability of output responses generated by the QPUF. It ensures that
if the same QPUF is queried separately with two input quantum states
$\rho_{in}$ and $\sigma_{in}$ that are $\delta_{c}$-distinguishable, then the
output states $\rho_{out}$ and $\sigma_{out}$ must also be
$\delta_{c}$-distinguishable with an overwhelmingly high probability,

$\text{Pr}[\textsf{F}(\rho_{out},\sigma_{out})\leqslant
1-\delta_{c}|\textsf{F}(\rho_{in},\sigma_{in})\leqslant 1-\delta_{c}]\geqslant
1-\epsilon(\lambda)$ (4)

3\. _Uniqueness_ : This property captures the QPUF generation process to
ensure that sufficiently distinguishable QPUFs are generated. This is captured
by mapping the each QPUF as a quantum operation characterised by a completely
positive trace preserving (CPTP) map that takes the input quantum states in
$\mathcal{H}^{d_{in}}$ to output states in $\mathcal{H}^{d_{out}}$. We say
that two such maps $\textsf{QPUF}_{\textbf{id}_{i}}$ and
$\textsf{QPUF}_{\textbf{id}_{j}}$ are $\delta_{u}$ distinguishable if,

$\text{Pr}[\|\textsf{QPUF}_{\textbf{id}_{i}}-\textsf{QPUF}_{\textbf{id}_{j}}\|_{\diamond}\geqslant\delta_{u}|i\neq
j]\geqslant 1-\epsilon(\lambda)$ (5)

where $\|.\|_{\diamond}$ is the diamond norm distance measure for the
distinguishablity between any two QPUFs.

The parameters $\delta_{r},\delta_{c}$ and $\delta_{u}$ are determined by the
security parameter $\lambda$. For QPUF, the two constraints
$\delta_{r}\leqslant\delta_{u}$ and $\delta_{r}\leqslant\delta_{r}$ ensure a
clear distinction between different QPUFs.

Once the requirements of a well constructed QPUF is defined, one often looks
for constructions that satisfy these requirements. It was shown by Arapinis
et. al 6 that a unitary device sampled from Haar measure set of unitaries
satisfies the robustness and collision resistance requirements of a QPUF. In
this work, we show that such a construction also satisfies the uniqueness
property, thus establishing that it is a suitable candidate for a QPUF. This
however is not a practical construction as it is known to require exponential
resources in the input size. Hence our work focuses on an alternative resource
efficient construction of QPUF based on the random circuit model for
generating approximate unitary $t$-designs 23. In Section 4, we show that this
construction satisfies all the QPUF requirements.

Next, in order to build cryptographic applications such as authentication,
device identification among others on top of QPUF, one requires that they
satisfy the soundness property. This is characterised by ‘unknownness’. Also
referred to as min-entropy property or randomness property of QPUF, it is
quantified by the amount of knowledge possessed by the adversary about the
QPUF before the start of a QPUF-based protocol. We provide a formal definition
of unknownness in the Sections 3 and 4. This unknownness property is highly
crucial in restricting the pre-protocol knowledge of the adversary and to
prove that the QPUF construction is ‘selectively unforgeable’ which is a
requirement to prove security in applications built on top of QPUF. Formally
the device is selectively unforgeable against a quantum polynomial time (QPT)
adversary if given access to a polynomial number of challenge-response pairs
of QPUF, the probability that the adversary receives a new random challenge
$\rho_{\text{in}}$ from a set of challenges Set, and preforms a local
operation $\mathcal{A}_{\textsf{QPT}}$ to produce the response
$\sigma\leftarrow\mathcal{A}_{\text{QPT}}(\rho;S\in(\rho_{i},\sigma_{i})_{1\leqslant
i\leqslant\text{poly}(n)})$ which is $\mu$-indistinguishable from the response
produced by QPUF, $\rho_{\text{out}}$ on the same challenge, is bounded by a
factor $\epsilon$,

$\begin{split}\textsf{Pr}[\textsf{F}(\sigma,\rho_{\text{out}})\geqslant
1-\mu|\rho\stackrel{{\scriptstyle\$}}{{\leftarrow}}\textsf{Set},S]\leqslant\epsilon(\lambda)\end{split}$
(6)

###  2.2 Distance Measure

1\. _Fidelity_. This is a measure of distance between two quantum density
operators. Although, not being a metric itself, it is related to the metric,
_Bures distance_ $\textsf{D}_{b}=\sqrt{2-2\textsf{F}}$. The fidelity of
density operators $\rho$ and $\sigma$ is defined as,

$\textsf{F}(\rho,\sigma)=\text{Tr}\big{[}\sqrt{\sqrt{\rho}\sigma\sqrt{\rho}}\big{]}$
(7)

2\. _Diamond norm_. Diamond norm is a distance metric for any two completely
positive trace preserving quantum operations $\textsf{U}_{1}$,
$\textsf{U}_{2}$. It is defined as,

$\|\textsf{U}_{1}-\textsf{U}_{2}\|_{\diamond}=\underset{\rho}{\text{max}}(\|(\textsf{U}_{1}\otimes\mathbb{I})[\rho]-(\textsf{U}_{2}\otimes\mathbb{I})[\rho]\|_{1})$
(8)

Operationally it quantifies the maximum probability of distinguishing
operation $\textsf{U}_{1}$ from $\textsf{U}_{2}$ in a single use. More
generally, the diamond norm of an operator $A$ has this form defined as,

$\|A\|_{\diamond}=sup_{l}\|A\otimes\mathbb{I}_{l}\|_{1,1},$

where

$\|B\|_{1,1}=sup_{X\neq 0}\frac{\|B(X)\|_{1}}{\|X\|_{1}},$

and $\|.\|_{1}$ is the usual trace norm.

###  2.3 Haar Measure Group

A Haar measure is a non-zero measure on any locally compact group $G$ such
that $\mu:G\rightarrow[0,\infty]$ such that for all $X\subseteq G$ and $x\in
G$:

$\mu(xX)=\mu(Xx)=\mu(X)$ (9)

where,

$\mu(X)=\int_{x\in G}d\mu(x)$ (10)

In particular, the Haar measure $\mathsf{d}\mu(\textsf{U})$ can be defined for
a unitary group $\textsf{U}(d)$ acting on $\log_{2}d$ qubits. Choosing
unitaries from the Haar measure on $\textsf{U}(d)$ can be thought as a natural
notion of uniform sampling from the unitary group. In practice however,
sampling from the Haar measure is exponentially costly 14. As an example, for
$d=2$, the unitary matrix can be represented as $\textsf{U}=e^{i\phi}$, with
$0\leqslant\phi\leqslant 2\pi$. The Haar measure
$\mathsf{d}\mu(\textsf{U})=\mathsf{d}\phi$ can then be easily verified to
measure the uniformity of the unitary group, since
$\mathsf{d}\mu(\textsf{U}_{0}\textsf{U})=\mathsf{d}\mu(\textsf{U}\textsf{U}_{0})=\mathsf{d}\mu(\textsf{U})$,
which translates to $\mathsf{d}(\phi+\phi_{0})=\mathsf{d}(\phi)$ for any fixed
unitary $\textsf{U}_{0}=e^{i\phi_{0}}$,

$\mu(\textsf{U})=\int_{x\in\textsf{U}}\mathsf{d}\mu(x)=\int_{0}^{2\pi}\mathsf{d}\phi$
(11)

For a general $d$, the Haar measure on the unitary group can be similarly
constructed by invoking the group invariant measure
$\mathsf{d}\mu(\textsf{U}_{0}\textsf{U})=\mathsf{d}\mu(\textsf{U}\textsf{U}_{0})=\mathsf{d}\mu(\textsf{U})$
for any fixed $\textsf{U}_{0}\in\textsf{U}(d)$.

###  2.4 Unitary $t$-designs

A unitary $t$-design on $\textsf{U}(d)$ is a set of $\log_{2}d$-qubit
unitaries $\mathcal{U}=\\{\textsf{U}_{i}\\}_{i=1,..,k}\subset\textsf{U}(d)$
together with a probability distribution over $\mathcal{U}$ which results in
sampling each unitary $\textsf{U}_{i}\in\mathcal{U}$ with probability
$p_{i}\geq 0$ ($\sum_{i=1,\cdots,k}p_{i}=1$) for $i=1,\cdots,k$. We will
denote a unitary $t$-design as a set of couples
$\\{p_{i},\textsf{U}_{i}\\}_{i=1,\cdots,k}$. A unitary $t$-design _mimics_
sampling from the Haar measure up to $t$-th order in the statistical moments
either _exactly_ (called exact unitary $t$-designs) or _approximately_ up to
some precision $\varepsilon$ (called $\varepsilon$-approximate $t$-designs)
29. The construction of exact unitary $t$-designs for any $t$ and any
dimension $d$ of the unitary group has long been a notoriously difficult task
30. Recently however, 31 showed how to construct exact unitary $t$-designs for
any $t$ and $d$; although the quantum circuits needed to implement these
constructions were not discussed in 31. Since we are interested in practical
implementations of QPUFs achievable by means of quantum circuits of well-known
and relatively simple structure, we will focus in this paper on sampling from
$\varepsilon$-approximate $t$-designs, a task which has been shown possible by
using the simple model of random quantum circuits (RQC) 23.

Now we go on to defining an $\varepsilon$-approximate $t$-design. Various
definitions of approximate designs suitable for various applications have been
proposed (see for example 32 for an overview of these definitions), the
definition we will focus on henceforth in this paper is that of an $additive$
$\varepsilon$-approximate $t$-design, since this is sufficient for our
purposes. Thus, whenever we say $\varepsilon$-approximate $t$-designs
throughout this paper we will mean additive $\varepsilon$-approximate
$t$-designs, unless specified otherwise. Let $\mu_{H}$ be the Haar measure on
$\textsf{U}(d)$, $\\{p_{i},\textsf{U}_{i}\\}_{i=1,\cdots,k}$ is said to be an
(additive) $\varepsilon$-approximate unitary $t$-design if the following holds

$\|\delta_{t}-\delta_{t}^{H}\|_{\diamond}\leq\varepsilon.$

Here, $\delta_{t}$ is a quantum channel defined as

$\delta_{t}(Y)=\sum_{i=1,\cdots,k}p_{i}\textsf{U}_{i}^{\otimes
t}Y\textsf{U}_{i}^{\dagger\otimes t},$

where $Y$ is a density matrix on a Hilbert space of dimension $d^{t}$. The
equivalent Haar random quantum channel associated with $Y$ is,

$\delta^{H}_{t}(Y)=\int\textsf{U}^{\otimes t}Y\textsf{U}^{\dagger\otimes
t}\mu_{H}(d\textsf{U}).$

Note that any approximate $t$-design is also an approximate $m\leq t$-design.
Using this we construct the $\textsf{QPUF}_{t}$ in section 4.

##  3 QPUF construction from Haar random Unitary

In this section, we revisit the QPUF construction proposed by 6. The authors
showed that the desired correctness requirements of robustness and collision-
resistance of QPUF of size $d$ can be satisfied by a unitary map of dimension
$d$ sampled from the Haar measure unitary set. Further they also showed that
it satisfies the crucial unknownness property against any QPT adversary.
Figure 1 provides an illustration of such a unitary map which takes an input
state $\rho_{in}\in\mathcal{H}^{d}$ and maps to an output state
$\rho_{out}\in\mathcal{H}^{d}$. Our contribution here is to explicitly show
that this construction satisfies the crucial uniqueness property too which is
crucial to ‘mass-produce’ sufficiently distinguishable QPUFs.

Figure 1: Illustration of QPUF as a unitary operation with input and output
quantum states in $\mathcal{H}^{d}$. The blue and green boxes are single-qubit
gates, while red boxes are two-qubit gates. These are the building blocks for
the qPUF construction.

###  3.1 Robustness $\&$ Collision-Resistance

It is fairly straighforward to check that any unitary map satisfies the
robustness and collision-resistance requirements. This is due to the crucial
property of a unitary map U that $\textsf{U}^{\dagger}\textsf{U}=\mathbb{I}$.
Any unitary acting independently on two input states $\rho_{in}$ and
$\sigma_{in}$, produces the corresponding output state
$\rho_{out}=\textsf{U}\rho_{in}\textsf{U}^{\dagger}$ and
$\sigma_{out}=\textsf{U}\sigma_{in}\textsf{U}^{\dagger}$ respectively. Since
the fidelity is a unitary invariant measure, hence
$\textsf{F}(\rho_{in},\sigma_{in})=\textsf{F}(\rho_{out},\sigma_{out})$. Hence
this implies the both robustness and collision-resistance properties in a
‘strict’ sense i.e. Eq 3 and 4 are satisfied with a probability 1.

###  3.2 Uniqueness

The previous two requirements can be satisfied by any unitary map. However, in
order to produce multiple sufficiently distinguishable QPUFs, we show that
sampling a QPUFs from a Haar random unitary set is sufficient to ensure
maximum distinguishability with exponentially high probability. We note that,
this is not the only method to produce QPUFs which satisfy the uniqueness
property. One could alternatively ensure that they pick distinguishable
unitaries in the manufacturing process enforce the uniqueness requirement.
However, this method would incur two key problems. One being that in order to
ensure that the two unitaries picked are sufficiently distinguishable, the
manufacturer of the QPUF needs to know the full description of the unitaries.
This information would not normally be known to the manufacturer especially if
there are random purtubations (in the form of noise) in the manufacturing
process. Secondly, as we see in the next section, this would compromise the
unknownness property, a key requirement to prove security of applications
built on top of QPUF.

Next, for the uniqueness property we use the following theorem,

###### Theorem 1

If QGen algorithm samples two unitaries $\textsf{QPUF}_{\text{id}_{i}}$ and
$\textsf{QPUF}_{\text{id}_{j}}$ uniformly randomly from the Haar measure set
of unitaries, then the probability that they are $\delta_{u}$-far is
exponentially close to 1.

_Proof_ : Let us denote the two QPUFs sampled uniformly randomly from the Haar
measure set of untiaries to be $\textsf{QPUF}_{\text{id}_{i}}=\textsf{U}_{0}$
and $\textsf{QPUF}_{\text{id}_{j}}=\textsf{U}_{1}$. Then for any positive
operator $X$, we can construct two unitary channels given by
$\Phi_{0}(X)=\textsf{U}_{0}X\textsf{U}_{0}^{\dagger}$ and
$\Phi_{1}(X)=\textsf{U}_{1}X\textsf{U}_{1}^{\dagger}$. For these two channels,
the diamond norm can be expressed as,

$\begin{split}\|\Phi_{0}-\Phi_{1}\|_{\diamond}&=\underset{\rho}{\text{max}}(\|(\Phi_{0}\otimes\mathbb{I})[\rho]-(\Phi_{1}\otimes\mathbb{I})[\rho]\|_{1})\\\
&=2\sqrt{1-\delta(\textsf{U}_{0}^{\dagger}\textsf{U}_{1})^{2}}\end{split}$
(12)

where $\delta(X)$ is the minimum absolute value taken over the numerical range
of the operator $X$ i.e.,

$\delta(X)=\underset{\ket{\phi}}{\text{min}}|\bra{\phi}X\ket{\phi}|$ (13)

where the minimum is over all the input states $\ket{\phi}$. Since the diamond
norm is unitarily invariant, hence with no loss of generality, one can set
$\textsf{U}_{0}=\mathbb{I}$ and $\textsf{U}_{1}=\textsf{U}$ where U is picked
uniformly randomly from the Haar measure. Let us denote the numerical range of
a Haar random unitary U as $W(\textsf{U})$,

$W(\textsf{U})=\\{\bra{\phi}\textsf{U}\ket{\phi}:\braket{\phi}{\phi}=1\\}$
(14)

It can be easily checked that the numerical range is unitarily invariant, i.e.
$W(\textsf{V}^{\dagger}\textsf{U}\textsf{V})=W(\textsf{U})$ for any unitary
matrix V. Since a unitary matrix is also a normal matrix, hence we can write a
unitary $\textsf{U}=\textsf{V}^{\dagger}\Lambda\textsf{V}$, where
$\Lambda:=\text{diag}(\lambda_{i})_{i=1}^{d}$, where $\Lambda$ has eigenvalues
of Uon its diagonal and V is a unitary matrix.

Let us denote a unit quantum state vector
$\ket{\phi}:=[\phi_{i},\cdots,\phi_{d}]^{T}$. From Eq 14 and the unitarily
invariant property of numerical range, we obtain

$W(\textsf{U})=W(\Lambda)=\bra{\phi}\Lambda\ket{\phi}=\sum_{i=1}^{d}\lambda_{i}|\phi_{i}|^{2}$
(15)

where $|\phi_{i}|\geqslant 0$ for all $i\in d$ and
$\sum_{i=1}|\phi_{i}|^{2}=1$. Thus the numerical range of a unitary matrix U
is just a convex hull of its eigenvalues.

So the problem of obtaining a lower bound on the diamond norm reduces to
bounding the absolute value of the numerical range of U:

$\begin{split}&\delta(\textsf{U}):=\underset{t_{1},\cdots,t_{d}}{\text{minimize}}\hskip
5.69054pt|\sum_{i=1}^{d}\lambda_{i}t_{i}|\\\ &\text{subject to}\hskip
5.69054ptt_{i}\geqslant 0\hskip 5.69054pt\forall
i\in[d],\sum_{i=1}t_{i}=1\end{split}$ (16)

First let us consider the eigenvalues of a general unitary matrix U. These
eigenvalues are in general complex numbers with absolute value 1. Let us
denote them by $\\{e^{i\alpha_{1}},\cdots,e^{i\alpha_{d}}\\}$. To prove the
main theorem, we first prove the following lemma.

###### Lemma 1.1

If all the eigenvalues $\\{e^{i\alpha_{1}},\cdots,e^{i\alpha_{d}}\\}$ of a
general unitary matrix U lie in an arc of size $\theta$, then
$\delta(\textsf{U})$ is lower bounded by a function of $\theta$.

_Proof_ : If all the eigenvalues lie in the arc $\theta\leqslant\pi$ then
there exists $j_{0},k_{0}$ such that $|\alpha_{j_{0}}-\alpha_{k_{0}}|=\theta$.
For all other $j,k\in[D]$, $|\alpha_{j}-\alpha_{k}|\leqslant\theta$. If the
arc $\theta>\pi$ then there exists $j_{0},k_{0}$ such that
$|\alpha_{j_{0}}-\alpha_{k_{0}}|=\pi-\underset{j,k\in[D]}{\text{min}}[\pi-|\alpha_{j}-\alpha_{k}|]$.

To find $\delta(\textsf{U})$, we first bound
$|\sum_{j=1}^{d}e^{i\alpha_{j}}t_{j}|$,

$\begin{split}\hskip
5.69054pt|\sum_{j=1}^{d}e^{i\alpha_{j}}t_{j}|&=\Big{[}(\sum_{j=1}^{d}t_{j}\cos\theta_{j})^{2}+(\sum_{j=1}^{d}t_{j}\sin\theta_{j})^{2}\Big{]}^{1/2}\\\
&=\Big{[}(\sum_{j=1}^{d}t_{j}^{2}+2\sum_{j\neq
k}t_{j}t_{k}\cos(\theta_{j}-\theta_{k})\Big{]}^{1/2}\\\
&=\Big{[}1-2\sum_{j\neq
k}t_{j}t_{k}[1-\cos(\theta_{j}-\theta_{k})]\Big{]}^{1/2}\\\
&\geqslant\Big{[}1-2t_{j_{0}}t_{k_{0}}[1-\cos(\theta_{j_{0}}-\theta_{k_{0}})]\Big{]}^{1/2}\\\
\end{split}$ (17)

where, from 3-rd to 4-th line, we have used the convexity argument that given
$t_{j}\geqslant 0$ for all $j\in[D]$ and $\sum_{j=1}^{D}t_{j}=1$, we get the
maximization of $\sum_{j\neq k}t_{j}t_{k}[1-\cos(\theta_{j}-\theta_{k})]$ when
$t_{i}\neq 0$ for $j_{0},k_{0}$ and is 0 otherwise. This implies that even if
the arc is spanned by multiple eigenvalues, the maximisation occurs with a
convex span of only two eigenvalues
$\\{e^{i\alpha_{j_{0}}},e^{i\alpha_{k_{0}}}\\}$.

Now when the convex span is over only two eigenvalues, then
$t_{j_{0}}=1-t_{k_{0}}$. From Eq 17, we can compute the quantity
$\delta(\textsf{U})$ as,

$\begin{split}\delta(\textsf{U})&=\underset{t_{j_{0}}}{\text{min}}\hskip
5.69054pt\sqrt{1-2t_{j_{0}}(1-t_{j_{0}})[1-\cos(\theta_{j_{0}}-\theta_{k_{0}})]}\\\
&=\sqrt{\frac{1}{2}+\frac{1}{2}\cos(\theta_{j_{0}}-\theta_{k_{0}})}\end{split}$
(18)

This completes the proof of the lemma. Few corollaries that emerge as a
consequence of this lemma are,

###### Corollary 1.1

For $\theta\leqslant\pi$, the minimum of absolute value of number range of a
unitary $\textsf{U}\in\textsf{U}_{D}$ is
$\delta(\textsf{U})=\sqrt{\frac{1}{2}+\frac{1}{2}\cos\theta}$

###### Corollary 1.2

If $\theta>\pi$, then for large $d$ and when the eigenvalues are normally
distributed along any specified sub-length of the arc, the minimum of absolute
value of number range of a unitary U is $\delta(\textsf{U})\approx 0$. This is
because there exists $j_{0},k_{0}$ such that
$|\alpha_{j_{0}}-\alpha_{k_{0}}|=\pi-\underset{j,k\in[D]}{\text{min}}[\pi-|\alpha_{j}-\alpha_{k}|]\approx\pi$
in the limit of large $d$.

Now to prove the main theorem, we first use the result from 33 which states
the following: Suppose a unitary $\textsf{U}\in\textsf{U}(d)$ is sampled
randomly from the Haar measure. Then for a fixed arc $\theta$ of a unit
circle, let $Y$ be the random variable corresponding to the number of
eigenvalues of U which lie in the $\theta$ arc. Then as the size $d$ grows,
the quantity $Z:=(Y-\mathbb{E}[Y])/\sqrt{\sigma(Y)}$ is asymptotically
normally distributed, where $\sigma(Y)$ is the variance of $Y$.

Suppose we look at such a random variable $Y$ for the fixed arc
$\theta=\pi-\epsilon$, with $\epsilon\ll 0$. Then 33 show that, the expected
value of $Y$ is,

$\mathbb{E}(Y)=\frac{d(\pi-\epsilon)}{2\pi}\approx\frac{d}{2}$ (19)

and the variance,

$\begin{split}\sigma(Y)&=\frac{1}{\pi^{2}}(\log
d+1+\gamma+\log\left|2\sin(\frac{\pi-\epsilon}{2})\right|)+o(1)\\\
&\approx\frac{1}{\pi^{2}}(\log d+1+\gamma+\log 2)+o(1)\end{split}$ (20)

where $\gamma\approx 0.57721..$ is Euler’s constant.

Thus it means the for $\theta\approx\pi$, on expectation, about half the
number of eigenvalues lie within the arc, with the variance given by Eq 20.
Also in the large $d$ limit, since $Z$ follows a normal distribution, then it
follows using Chernoff-Hoeffding bound that,

$\text{Pr}[|Y-\mathbb{E}[Y]|>\mathbb{E}[Y]]\leqslant
e^{-\mathbb{E}[Y]^{2}/2\sigma(Y)^{2}}\approx e^{-d\pi^{2}/4\log d}$ (21)

This result implies that when any two $\textsf{QPUF}_{\textbf{id}_{i}}$ and
$\textsf{QPUF}_{\textbf{id}_{j}}$ are sampled uniformly randomly from the Haar
measure, then probability that they are not perfectly distinguishable i.e.
$\|\textsf{QPUF}_{\textbf{id}_{i}}-\textsf{QPUF}_{\textbf{id}_{j}}\|_{\diamond}\leqslant
2$ is exponentially low. Next we briefly mention the required unknownness
property of the QPUF.

###  3.3 Unknownness property

In this section, we revisit the ‘unknownness’ definition provided by 6 and
highlight the drawback of this definition in allowing for resource efficient
QPUF constructions. The original unknown definition is captured in the
following definition (slightly modified 6),

######  Definition 1 ($\epsilon,\lambda,\delta,$-Unknown QPUF)

We say that a QPUF constructed as a unitary transformation U from a set
$S\subseteq\textsf{U}(d)$ is $(\epsilon,\lambda,\delta)$-unknown, if for any
quantum polynomial time (QPT) adversary $\mathcal{A}$, before making any query
to U, the probability of outputting a response $\mathcal{A}(\rho)$ with
fidelity at least $1-\delta$ with respect to the _ideal_ response $U\rho
U^{\dagger}$ on every state $\rho=|\psi\rangle\langle\psi|$, with
$|\psi\rangle\in\mathcal{H}^{d}$ is bounded by:

$\mathsf{Pr}[\forall|\psi\rangle\in\mathcal{H}^{d}:\mathsf{F}(\mathcal{A}(\rho),\textsf{U}\rho\textsf{U}^{\dagger})\geqslant
1-\delta]\leqslant\epsilon(\lambda)$ (22)

An immediate consequence of this definition is that if the $U$ is a Haar
random unitary, then $\epsilon(\lambda)=\textsf{negl}(log_{2}(d))$ for any
$\delta$ with $1-\delta=\textsf{non-negl}(log_{2}(d))$ 6. Thus this definition
ensures that apriori, the adversary has negligibly small information of the
QPUF, and thus it is essentially unknown.

The definition 1 bounds the prior knowledge of any QPT adversary $\mathcal{A}$
in terms of their ability to correctly produce the output states given any
random state $\rho$ picked from the Haar measure set of states. However, one
major drawback of this definition is that it limits the capability of ‘any’
QPT adversary. This automatically rules out a QPUF construction which is
composed of polynomial sized circuit since if there was such a QPUF
construction, then there would exist ‘a’ QPT adversary which would generate
the correct response of any state $\rho$ with a probability 1. In that case,
that adversary would be described by the QPUF unitary itself.

In the next section, we propose a construction of QPUF using resource
efficient unitary $t$-designs i.e. the description of the unitary would be
composed of only poly$(\log d)$ gates, where $d$ is the Hilbert space in which
the unitary resides.

##  4 QPUF from unitary $t$-designs

To overcome the issue of inefficient construction of QPUF as a unitary sampled
uniformly randomly from Haar measure, we introduce a resource efficient
construction of these devices using a unitary sampled uniformly randomly from
the $t$-design set of unitaries. For a brief introduction into the designs, we
refer the reader to section 2.4.

###  4.1 $\textsf{QPUF}_{t}$ Generation and Evaluation

Similar to the original proposal of 6, a $\textsf{QPUF}_{t}$ involves a
manufacturing process where the manufacturer samples uniformly from set of
unitaries
$\mathcal{U}:\\{\textsf{U}_{1},\cdots\textsf{U}_{k}\\}\in\textsf{U}(d)$ acting
on $n=\log_{2}d$ qubits which form an approximate unitary $t$-design. This is
formally defined via the manufacturer’s quantum generation algorithm,

$\textsf{QGen}:\textsf{QPUF}_{t,\textsf{id}}=U_{\textsf{id}}\stackrel{{\scriptstyle\$}}{{\leftarrow}}\\{\textsf{U}_{1},\cdots\textsf{U}_{k}\\}$
(23)

The $\textsf{QPUF}_{t}$ generated via this process needs to have good
completeness requirements of robustness, collision-resistance and uniqueness.
What could be potentially problematic in the case of constructions of
$\epsilon$-approximate unitary $t$-designs is the uniqueness property. The
reason behind this is that these constructions usually _sample_ from a set of
unitaries forming an approximate design 23. Depending on the construction,
this sampling (or equivalently the QGen algorithm) could be highly redundant
in the sense that it samples the same unitary with high probability when
implemented twice in succession. Furthermore, these identical unitaries could
have different identifiers. For example, in the RQC model different runs of
RQC’s characterized by different two-qubit gates applied at different
positions could (in this case, the unique identifier is the set of gates and
set of positions where these gates are applied), depending on the two-qubit
gate set used, produce the same overall unitary (possibly up to global phase).
This is detrimental to the uniqueness property which, as seen previously,
demands that two QPUFS with two different identifiers be distinguishable with
high probability. To overcome this issue, we use a specific construction for
$\varepsilon$-approximate $t$-designs which we will detail in the next
paragraph.

Our QGen process involves a particular type of circuit sampling from an
approximate $t$-design inspired by the measurement based quantum computing
(MBQC) approach 25, 34, and from a recent result of 24. 111We note that our
construction can also be viewed in the MBQC framework as a 2D graph state
which results in a constant depth quantum circuit 26, 22. Note that our
circuit is closely related to that of 35, with the main difference being that
the circuit in 35 was shown to sample from an approximate 2-design, whereas
our construction samples from an approximate $t$-design for any $t$, which is
key for our security definition of _practical unknownness_ defined over the
next sections. Although the results of 35 should in principle be extendable to
any $t>2$, it is not immediately clear from 35 how this can be done, hence we
do not consider their construction in this work. We now explain the paralell
random circuit construction, a type of RQC on which our construction is based.

Let $G\subset\textsf{U}(4)$ be a set of unitaries which is _approximately
universal_ on $\textsf{U}(4)$, in the sense that any
$\textsf{U}\in\textsf{U}(4)$ can be approximated to an arbitrary accuracy
$\gamma$ (in some norm) by a product of lenght $l(\gamma)$ of unitaries
$\prod_{i=1,..,l(\gamma)}\textsf{V}_{i}$, where each $\textsf{V}_{i}\in G$.
The parallel random circuit construction was first defined in 23 as follows on
a 1D circuit of $n$ qubits initially in some state $|\psi\rangle$.

  * •

Step 1: On the 1D circuit, apply with a probability 0.5, either the unitary

$\textsf{U}_{12}\otimes\textsf{U}_{34}\cdots\otimes\textsf{U}_{n-1n}\hskip
5.69054pt(\text{for even $n$)}\hskip 5.69054pt/\hskip
5.69054pt\textsf{U}_{12}\otimes\textsf{U}_{34}\cdots\otimes\textsf{U}_{n-2n-1}\hskip
5.69054pt(\text{for odd $n$})$

or the unitary

$\textsf{U}_{23}\otimes\textsf{U}_{45}\cdots\otimes\textsf{U}_{n-2n-1}\hskip
5.69054pt(\text{for even $n$)}\hskip 5.69054pt/\hskip
5.69054pt\textsf{U}_{23}\otimes\textsf{U}_{45}\cdots\otimes\textsf{U}_{n-1n}\hskip
5.69054pt(\text{for odd $n$})$

where $U_{ii+1}$ for $i=1,..,n-1$ is a unitary chosen uniformly at random from
$G$ and which acts on qubits $i$ and $i+1$ of the 1D circuit

  * •

Step 2: Repeat Step 1 $k\geq C(G)t^{9}(2ntlog(2)+log(\dfrac{1}{\varepsilon}))$
times, where $t$ is a positive integer, $C(G)$ is a positive constant which
depends on the choice of gate set $G$, and $0<\varepsilon<1$.

The output of this RQC is the state $\textsf{U}_{\textsf{tot}}|\psi\rangle$,
where $\textsf{U}_{\textsf{tot}}$ is the product of all unitaries applied in
the parallel random circuit construction, and which was shown in 23 to be a
unitary sampled from a $2\varepsilon$-approximate unitary $t$-design. However,
the main restriction in 23 was that the unitaries in $G$ had to be _symmetric_
( if $\textsf{V}\in G$, then $\textsf{V}^{\dagger}\in G$) and composed
entirely of algebraic entries, this strictly limits the choice of allowed gate
sets $G$. However, the main result of 24 (and to an extent also that of 36)
was removing the symmetric and algebraic entries requirements. Indeed, 24 show
that $any$ choice of an approximately universal gate set $G\in\textsf{U}(4)$
results in a $2\varepsilon$-approximate $t$-design in a parallel random
circuit construction where Step 1 is repeated $\geq O(k)$ times, with $k$ as
defined in Step 2. Using the relaxation of 24, we construct our parallel
random circuit where our gate set $G$ will be of the form

$G=\\{CZ\cdot(X(\alpha+m_{1}\pi)Z(\beta+m_{2}\pi)\otimes(X(\gamma+m_{3}\pi)Z(\delta+m_{4}\pi))\\}_{m_{1},..,m_{4},\alpha,\beta,\delta,\gamma},$

where $\alpha,\beta,\gamma,\delta$ range over all angles in the interval
$[0,2\pi]$, and $m_{i}\in\\{0,1\\}$ for $i=1,..4$.

Thus, choosing $\textsf{U}_{ii+1}$ (whose circuit implementation is shown in
Figure 2) uniformly from $G$ corresponds to applying a unitary

$\textsf{U}_{ii+1}=CZ_{ii+1}\cdot(X_{i}(\alpha+m_{1}\pi)Z_{i}(\beta+m_{2}\pi)\otimes
X_{i+1}(\gamma+m_{3}\pi)Z_{i+1}(\delta+m_{4}\pi)),$

acting on qubits $i$ and $i+1$ of the 1D circuit, where
$\alpha,\beta,\delta,\gamma$ are chosen uniformly from $[0,2\pi]$ and
$m_{1},m_{2},m_{3},m_{4}$ are random bits chosen independently with
probability 1/2 from the set $\\{0,1\\}$.

The reason why the binary bits $m_{i}$ appear is because our construction is
based upon an MBQC construction similar to those in 37, 35, 34 which have been
provably shown to converge to approximate $t$-designs. The bits $m_{i}$ have a
natural interpretation in this setting as the random measurement results of
single qubits in some basis (see for example 25). Although we will not go into
details of MBQC constructions here, we keep this structure of the gate set to
illustrate that one can go straightforwardly between both circuit and MBQC
models using translations such as those in 37. This translation may be useful
in implementing our construction on different hardware, such as, for example
trapped ions 38.

Note that the choice of the angles $\alpha,\beta,\gamma,\delta$ uniformly from
$[0,2\pi]$ will give us a good uniqueness. This is demonstrated by our
numerical findings seen later on in section 4.3. The intuition behind why this
should be true is that running two different instances of our construction, it
would be highly unlikely that the same sets of angles (or even close sets of
angles) are obtained; therefore the two output unitaries of these two runs
should be sufficiently distinct (and therefore distinguishable) with high
probability.

Figure 2: An instance of the block unitary $\textsf{U}_{ii+1}$ chosen
uniformly from the set $G$. The unitary $\textsf{U}_{ii+1}$ acts on the qubits
$i$ and $i+1$, where $\alpha,\beta,\delta,\gamma$ are chosen uniformly from
$[0,2\pi]$ and $m_{1},m_{2},m_{3},m_{4}$ are bits chosen independently with
probability 1/2 from the set $\\{0,1\\}$.

It can be easily seen that applying a parallel random circuit with $G$ as
defined above amounts in the circuit picture to constructing the circuit
composed of unitary blocks shown in Figure 2222In the equivalent MBQC picture,
this amounts to constructing a regular graph state followed by a series of
$XY$ measurements where the angles are chosen from $[0,2\pi]$.. An instance of
our parallel random circuit construction in the circuit picture is given in
Figure 3.

Figure 3: An instance of a parallel local random circuit with $k=4$ (left),
and its realisation in the circuit picture (right). Each block from 1 to 4
corresponds to Step 1 in our parallel random circuit construction. The
$U_{ii+1},V_{ii+1},W_{ii+1}$, and $L_{ii+1}$ are unitaries chosen uniformly at
random from our chosen set $G$ and acting on qubits $i$ and $i+1$. As
mentioned in the main text, our choice of $G$ and our parallel random circuit
construction can be implemented naturally in the circuit picture with
parameterised single qubit $X$ (in green) and $Z$ (in yellow) gates and the
unparameterised CZ gate (right part of figure). The gate parameters
$\alpha_{i}^{\prime},\beta_{i}^{\prime},\gamma_{i}^{\prime},\delta_{i}^{\prime}$
are equal to
$\alpha_{i}+m_{1,i}\pi,\beta_{i}+m_{2,i}\pi,\gamma_{i}+m_{3,i}\pi,\delta_{i}+m_{4,i}\pi$
respectively, where $\alpha_{i},\beta_{i},\delta_{i}$, and $\gamma_{i}$ are
$XY$ angles chosen uniformly from $[0,2\pi]$, and
$m_{1,i},m_{2,i},m_{3,i},m_{4,i}$ are bits chosen independently with
probability 1/2 from the set $\\{0,1\\}$.

We still need to prove that our chosen set $G$ is approximately universal on
$\textsf{U}(4)$, as required in the construction of approximate designs we use
24, 23. We will use a result of 39 which shows that the set of all single
qubit gates together with an entangling gate is approximately universal on
$\textsf{U}(4)$. Observe that the set $\\{X(\alpha),Z(\beta)\\}$ with $\beta$
and $\alpha$ ranging from 0 to $2\pi$ is dense in $\textsf{U}(2)$. Indeed, any
single qubit unitary can be represented as a product of gates from this set.
Furthermore, $CZ$ is an entangling gate. Thus, our chosen set $G$ is
approximately universal on $\textsf{U}(4)$ from 39 since it contains a dense
set in $\textsf{U}(2)$ together with an entangling gate.

The evaluation process of this construction is captured by QEval which maps
the any input state $\rho_{in}\in\mathcal{H}^{d}$ to the output state
$\rho_{out}\in\mathcal{H}^{d}$,

$\textsf{QEval}:\rho_{out}=\textsf{QPUF}_{t,\textsf{id}}\rho_{in}\textsf{QPUF}_{t,\textsf{id}}^{\dagger}$
(24)

Next we show that our construction satisfies the security notions
characterised by robustness, collision-resistance, uniqueness and unknownness
requirements.

###  4.2 Robustness $\&$ Collision-Resistance

Following the same arguments as in section 3.1, the unitary property of
$\textsf{QPUF}_{t}$ ensures that the device satisfies the robustness and
collision-resistance properties.

###  4.3 Uniqueness

In this section, we provide numerical evidences that our parallel random
circuit based approximate $t$-design construction of $\textsf{QPUF}_{t}$
satisfies the uniqueness condition with an overwhelmingly high probability.
For our numerical analysis, we construct two instances $\textsf{U}_{0}$ and
$\textsf{U}_{1}$ of our parallel random circuit as shown in Figure 3. This
amounts to randomly choosing the parameters of the $X$ and $Z$ gates and
computing the diamond norm between the resulting unitaries. We are able to
infer that the diamond norm between any two such unitaries is overwhelmingly
close to 2 (which corresponds to maximum distinguishability between the two
unitaries). Further, we infer that the diamond norm closeness to 2 increases
as one increases the circuit size : number of qubits and blocks. In the
following figures, we plot the diamond norm between two unitaries picked using
our construction (on the $y$-axis) with the number of instances (runs) of
creating these unitaries (on the $x$-axis). The diamond norm in the plots
between two such unitary channels is computed using the Equation 12 and Lemma
1.1. In other words, the diamond norm between $\textsf{U}_{0}$ and
$\textsf{U}_{1}$ is expressed as a function of the numerical range
$\delta(\textsf{U}_{0}^{\dagger}\textsf{U}_{1})$. Further, this numerical
range is computed using the convex hull of the eigenvalues of
$\textsf{U}_{0}^{\dagger}\textsf{U}_{1}$. This in turn is computed using Lemma
1.1 which tells us that the numerical range is equal to the minimum difference
in angle (radians) of the two distinct eigenvalues of
$\textsf{U}_{0}^{\dagger}\textsf{U}_{1}$. Note that the eigenvalue ($\alpha$)
of a unitary matrix is of the form $e^{i\alpha}$, where $\alpha$ is the angle
associated with the eigenvalue in the complex plane.

Figures 4,5,6 correspond to the plots of diamond norm vs number of runs for
number of qubits ($\log_{2}d$) corresponding to 4, 6 and 8 respectively. Each
figure is plotted by considering up-to 4 blocks. Within each figure, we see
that the closeness to the maximum value of 2 increases by adding more blocks
in the circuit. This would be expected since adding more blocks amounts to
randomly choosing parameters for more gates and hence the randomness in the
circuit increases. Thus the probability that two such randomly picked circuits
would be the same, decreases with increasing number of blocks.

Figure 4: Figure depicting the diamond norm vs number of runs for two
independent circuits construction using our $\textsf{QPUF}_{t}$ construction
for circuit of size corresponding to 4 qubits. We observe that across the 50
runs, the diamond norm for circuits corresponding to blocks 1, 2, 3, and 4 are
lower bounded by 1.93, 1.98, 1.98, and 1.99 respectively.  Figure 5: Plot of
diamond norm vs number of runs for circuit of size corresponding to 6 qubits.
We observe that across the 50 runs, the diamond norm for circuits
corresponding to blocks 1, 2, 3, and 4 are lower bounded by 1.994, 1.998,
1.999, and 1.999 respectively.  Figure 6: Plot of diamond norm vs number of
runs for circuit of size corresponding to 8 qubits. We observe that across the
50 runs, the diamond norm for circuits corresponding to blocks 1, 2, 3, and 4
are lower bounded by 1.99952, 1.99996, 1.99999, and 1.99999 respectively.

###  4.4 Unknownness property

As highlighted in the previous sections, the unknownness property of QPUF is
essential to show the soundness property against an adversary trying to
leverage information of the device in the query access model. We pointed out
in section 3.3 that the unknownness definition initially proposed for the
Haar-random construction of QPUF ($\textsf{U}\in\textsf{U}(d)$) by 6 implies
that any QPT adversary, who has not apriori queried U, has negligible
probability of producing the correct response
$\textsf{U}\rho\textsf{U}^{\dagger}$, for all input states
$\rho\in\mathcal{H}^{d}$. We also mentioned that such an construction of a
Haar random sampled unitary is impractical in the sense that the size of
quantum circuits needed to sample from the Haar measure is exponential in
$\log_{2}d$.

The above definition of unknownness does not allow constructing a _practical_
QPUF (i.e a QPUF generated by a $poly(\log_{2}d)$-time algorithm). To see
this, suppose that U can be generated by a quantum circuit $\mathcal{C}$
composed of $poly(\log_{2}d)$ gates. Suppose $\mathcal{A}$ implements
$\mathcal{C}$ (it is well within $\mathcal{A}$’s power to do so, since we
assume a polynomial time adversary). $\mathcal{A}$ now has exactly reproduced
$U$, and therefore can produce with probability one a correct response (i.e a
response which is exactly equal to the ideal response
$\textsf{U}\rho\textsf{U}^{\dagger}$), for all states
$\rho\in\mathcal{H}^{d}$. The above definition rejects any such construction
of a QPUF (since the probability of producing a correct response over all the
states should be negligible for any $poly(\log_{2}d)$ quantum circuit
$\mathcal{C}$). Therefore, the only circuits allowed for generation of QPUF in
the above definition are super-polynomial time circuits.

In order to get around this problem, we adopt a _modified_ definition of
unknownness than that of 6, but which nevertheless is a reasonable definition
of what a QPUF should be, and furthermore is satisfied naturally for
$\varepsilon$-approximate unitary $t$-designs. We will call this _practical_
unknownness.

######  Definition 2 ($\epsilon,t,d$\- Practical unknownness)

: We say that a QPUF constructed as a unitary transformation U from a set
$S\subseteq\textsf{U}(d)$ is $(\epsilon,t,d)$\- practically unknown if
provided a bounded number $t\leq poly(\log_{2}d)$ of queries
$\textsf{U}\rho\textsf{U}^{\dagger}$, for any $\rho\in\mathcal{H}^{d}$, the
probability that any $poly(\log_{2}d)$-time adversary can perfectly
distinguish U from a Haar distributed unitary is upper bounded by
$1/2(1+0.5\varepsilon)$.

Here $0<\varepsilon<1$ and $t$ are functions of $\log_{2}d$, and
$lim_{log_{2}(d)\to\infty}\varepsilon=0$.

Here distinguishability of two states $|\psi\rangle$ and $|\phi\rangle$ (for
simplicity we describe the distinguishability in terms of pure states, but it
can be naturally extended to mixed states) implies the ability to distinguish
between $|\psi\rangle$ and $|\phi\rangle$ by performing some unitary
transformation V on each of these states followed by measuring the qubits of
these two states in some basis. This definition of distinguishability is
captured naturally in the definition of the $\|.\|_{1}$, a norm used to
quantify the behaviour of an approximate $t$-design 23. Indeed, when
$\||\psi\rangle\langle\psi|-|\phi\rangle\langle\phi|\|_{1}=2$ it means that
$|\phi\rangle$ and $|\psi\rangle$ are orthogonal, and thus maximally
distinguishable; conversely when
$\|\psi\rangle\langle\psi|-|\phi\rangle\langle\phi|\|_{1}=0$, then
$|\psi\rangle=|\phi\rangle$ and these states are indistinguishable. Suppose we
are given two states $\rho_{1}$ and $\rho_{2}$ uniformly at random, and we
wish to derive a procedure for distinguishing $\rho_{1}$ from $\rho_{2}$. Any
procedure we can think of amounts to performing a unitary V followed by some
positive operator-valued measure (POVM), which could be 2-valued for a
sophisticated enough choice of V. Suppose we want to assign the measurement
outcome 0 to $\rho_{1}$ and 1 to $\rho_{2}$ (in that case the POVM is
2-valued). In that case, it can be shown (see for example 40) that the
probability of distinguishing $\rho_{1}$ from $\rho_{2}$ (i.e getting the
measurement result 0 and having the state $\rho_{1}$, or getting the
measurement result 1 and having the state $\rho_{2}$) is given by

$P_{distinguish}=\dfrac{1}{2}+\dfrac{1}{4}\|\rho_{1}-\rho_{2}\|_{1}.$

Thus, if $\|\rho_{1}-\rho_{2}\|_{1}=2$ there is a procedure which can
perfectly distinguish $\rho_{1}$ from $\rho_{2}$. On the other hand, if
$\|\rho_{1}-\rho_{2}\|_{1}=0$ no process can do better than guess (with
probability 1/2) whether the state is $\rho_{1}$ or $\rho_{2}$, and in that
case the states are completely indistinguishable. In general, the smaller the
norm $\|\rho_{1}-\rho_{2}\|_{1}$, the less distinguishable are the states
$\rho_{1}$ and $\rho_{2}$.

To see why this definition of unknownness is natural for unitary $t$-designs,
consider a given a unitary U unknown to the adversary $\mathcal{A}$, and which
is sampled from an $\varepsilon$-approximate $t$-design
$\\{p_{i},\textsf{U}_{i}\\}_{i=1,\cdots,k}$. Suppose the adversary has access
to $m\leq t$ copies of $\textsf{U}\ket{\phi}$ , where
$\ket{\phi}\in\mathcal{H}^{d}$ is any pure state known to $\mathcal{A}$, and
possibly of his choosing. The mixed state seen by the adversary is then

$\rho=\sum_{i=1,\cdots,k}p_{i}\textsf{U}_{i}^{\otimes
m}(|\phi\rangle\langle\phi|)^{\otimes m}\textsf{U}_{i}^{\dagger,\otimes m}$
(25)

where the sum ranges over all elements of
$\\{p_{i},\textsf{U}_{i}\\}_{i=1,\cdots,k}$. By the definition of a
$\varepsilon$-approximate $t$-design seen previously 23,

$\|\rho-\rho_{H}\|_{1}\leq
sup_{l}\|\delta_{m}\otimes\mathbb{I}_{l}(X)-\delta^{H}_{m}\otimes\mathbb{I}_{l}(X)\|_{1}\leq\|\delta_{m}-\delta^{H}_{m}\|_{\diamond}\leq\varepsilon,$
(26)

The $\|.\|_{1}$ norm, as seen before (see $P_{distinguish}$), relates directly
to the distinguishability between two states, and is bounded in the case of
approximate $t$-designs by an arbitrarily small chosen constant $\varepsilon$.
Furthermore, in standard constructions of $t$-designs 34, 23, one can choose
$t=poly(\log_{2}d)$, and $\varepsilon=O(1/\exp(\log_{2}d))$ with only a
$poly(\log_{2}d)$ increase in the depth of the quantum circuit sampling from
the approximate $t$-design. Note that in this framework, we get a natural
interpretation of the order $t$ of the design, it is simply the maximal number
of queries an adversary can make such that the unitary $U$ remains practically
unknown.

Finally, we note that the desired soundness property of selective
unforgeability of our $\textsf{QPUF}_{t}$ construction against any bounded
quantum adversary (see section 2.1 for definition on selective unforgeability)
follows naturally from the proof presented by 6 for Haar random unitary QPUF
construction. This follows from the fact that the failure of an adversary to
produce the correct response of a selected challenge state (not selected by
the adversary) is solely due to the fact that the challenge state is chosen
from the Haar measure. The unknownness property developed here only excludes
any attacks where the adversary can leverage the _pre-protocol_ information of
the QPUF and thus would be able to trivially copy the device and thus be
successful in producing the responses of any challenge state (even if the
challenge is not prepared by the adversary).

##  5 Noise-resilience of $\textsf{QPUF}_{t}$

Real-world implementation of $\textsf{QPUF}_{t}$ construction would involve
the presence of undesired noise in the circuits. In this section, we consider
the effects of a special type of noise, unitary noise, and show that our
$t$-design based QPUF construction is resilient to this noise model. Unitary
noise maps is a special case of general noise map which transforms an ideal
unitary U to another $\textsf{U}^{\prime}$ representing the experimental
imperfections. $\textsf{U}^{\prime}$ should still be _close enough_ to U, this
closeness is quantified in Equation (27) below.

Assume that ideal manufacturer has an approximate $t$-design set consisting of
$\mathcal{U}=\\{\textsf{U}_{1},\cdots,\textsf{U}_{k}\\}$ elements that are
sampled with the probabilities $\\{p_{1},\cdots,p_{k}\\}$ respectively.
However, in reality, due to experimental implementations, the unitaries
$\\{\textsf{U}_{1},\cdots,\textsf{U}_{k}\\}$ are noisy. Under the unitary
noise model, every unitary $\textsf{U}_{i}$ is subjected to a unitary noise
channel $\Lambda_{i}$. More precisely, for a given quantum state $\rho$,
$\Lambda_{i}\circ\textsf{U}_{i}(\rho)=\textsf{U}^{{}^{\prime}}_{i}\rho\textsf{U}_{i}^{{}^{\prime}\dagger}$,
where $\textsf{U}^{{}^{\prime}}_{i}$ the unitary implemented due to the
unitary noise.

Under this noise model, we immediately see that the requirements of robustness
and collision-resistance are still preserved for $\textsf{QPUF}_{t}$ since
these requirements only require the construction to be a unitary map. The
requirements of uniqueness and practical unknownness leverage the $t$-design
sampling property of the construction. As we show now, our chosen noise model
still preserves the unitary sampling from the approximate $t$-design. We show
this with theorem 2.

###### Theorem 2

If the noiseless $\textsf{QPUF}_{t}$ corresponds to $\epsilon$-approximate
$t$-design, then the $\epsilon_{t}$ additive unitary noise $\textsf{QPUF}_{t}$
corresponds to $\epsilon+\epsilon_{t}$-approximate $t$-design.

_Proof_ : If the $\epsilon_{t}$-unitary noise map is denoted by $\Lambda_{i}$,
then for all $\textsf{U}_{i}\in\mathcal{U}$, we have

$\|ad_{\textsf{U}^{\otimes t}_{i}}-ad^{\Lambda_{i}}_{\textsf{U}^{\otimes
t}_{i}}\|_{\diamond}\leq\varepsilon_{t},$ (27)

where $ad_{\textsf{U}^{\otimes t}_{i}}(.)=\textsf{U}^{\otimes
t}(.)\textsf{U}^{\dagger\otimes t}$, $ad^{\Lambda_{i}}_{\textsf{U}^{\otimes
t}_{i}}(.)$ is defined similarly to $ad_{\textsf{U}^{\otimes t}_{i}}(.)$ but
with each $U_{i}$ now acted upon by the noise channel $\Lambda_{i}$,
$0<\varepsilon_{t}<1$ is the noise parameter, which is usually a function of
$t$, it can be understood naturally as the overall noise strength acting on
the tensor product $U^{\otimes t}_{i}$, where each of the $t$ copies of
$U_{i}$ is acted upon by $\Lambda_{i}$.

Now, since $\\{p_{i},\textsf{U}_{i}\\}_{i=1,\cdots,k}$ is a
$\varepsilon$-approximate unitary $t$-design it satisfies (see Equation (26) )
41

$\|\delta_{t}-\delta^{H}_{t}\|_{\diamond}\leq\varepsilon,$ (28)

where $\delta_{t}(Y)=\sum_{i}p_{i}\textsf{U}_{i}^{\otimes
m}Y\textsf{U}_{i}^{\dagger,\otimes m}=\sum_{i}p_{i}ad_{\textsf{U}^{\otimes
t}_{i}}(Y)$, $\delta^{H}_{m}(Y)=\int ad_{\textsf{U}^{\otimes
t}}(Y)d\mu(\textsf{U})$ are as defined previously in Equation (26), and we
define
$\delta^{\Lambda}_{t}(Y)=\sum_{i}p_{i}ad^{\Lambda_{i}}_{\textsf{U}^{\otimes
t}_{i}}(Y)$ to be the noisy version of $\delta_{t}(Y)$ where each
$\textsf{U}_{i}$ is acted upon by the noise channel $\Lambda_{i}$. By a
triangle inequality,

$\|\delta^{\Lambda}_{t}-\delta^{H}_{t}\|_{\diamond}\leq\|\delta^{\Lambda}_{t}-\delta_{t}\|_{\diamond}+\|\delta_{t}-\delta^{H}_{t}\|_{\diamond}\leq\|\delta^{\Lambda}_{t}-\delta_{t}\|_{\diamond}+\varepsilon.$

Now,

$\|\delta^{\Lambda}_{t}-\delta_{t}\|_{\diamond}\leq\sum_{i}p_{i}\|ad^{\Lambda_{i}}_{\textsf{U}^{\otimes
t}_{i}}-ad_{\textsf{U}^{\otimes
t}_{i}}\|_{\diamond}\leq\varepsilon_{t}\sum_{i}p_{i}\leq\varepsilon_{t}.$

Replacing this in the above equation we obtain

$\|\delta^{\Lambda}_{t}-\delta^{H}_{t}\|_{\diamond}\leq\varepsilon+\varepsilon_{t}.$
(29)

Equation (29) is a meaningful definition of an
$\varepsilon^{{}^{\prime}}$-approximate $t$-design when
$\varepsilon^{{}^{\prime}}=\varepsilon+\varepsilon_{t}\leq 1$, this means that
the noise strength should satisfy $\varepsilon_{t}\leq 1-\varepsilon$. Note
that Equation (29) may not be a very practical definition of noise-resilience.
Indeed it somehow demands that the overall noise strength $\varepsilon_{t}$ be
at most a constant independent of $t$. This would mean, that as the system
size increases, the error rates of single qubits should decrease so that this
condition remains satisfied. We expect that in order to get a better notion of
noise-resilience, some notion of fault-tolerance and quantum error correction
should be invoked.

##  6 Discussion

Quantum physical unclonable functions have become a rapidly emerging
cryptographic technology to provide solutions for tasks including device and
message authentication, secure key exchange among others. Although these have
gained significant interest in recent times, a rigorous resource-efficient
construction with provable security guarantees have been missing. Our work
addresses this issue by proposing a QPUF based on an approximate unitary
$t$-design construction; called $\textsf{QPUF}_{t}$. We utilise the parallel
random circuit based $t$-design construction 23, 24 and show that this
construction provides provable security guarantees against a BQP adversary
with bounded $t$-query access to the device. Further, our construction
involves only nearest neighbour interaction of qubits, which makes our
construction highly practical. When viewed in the measurement based quantum
computation model 25, 37, 22, our circuit is constant depth, which is a
further indication of its potential near-term implementation.

Our work also proposes the first use case of approximate $t$-designs for
arbitrary $t$-values. We note that the previous use cases of $t$-designs have
been restricted only to some (usually low) $t$ values; our work on the
contrary states that higher the $t$ value our QPUF is constructed with, higher
the level of security it provides. By this, we mean that we empower the
adversary to be able to do more queries to the device in the pre-protocol in
order to leverage key information of the device and thus use it during the
protocol run. This can also be viewed alternatively that the QPUF can be
allowed to remain in an unsecured environment for a longer period of time if
its constructed with approximate designs of higher $t$ values (the adversary
performs queries on the device while its in the unsecured environment).

We realise that our work is just the beginning of (what could be) proposing
efficient construction of these hardware-based cryptographic primitives with
provable security guarantees. We envision the future work where these
constructions are proven secure against adversaries who are not just
restricted to the _black-box_ query access model. Specifically, security in
the _white-box_ model would make these devices much more tailored to real
world deployment. Under the white-box model, the adversary would know the
circuit layout which would be in the public domain, but would not know the
parameters of $X$ and $Z$ gates. Hence the security would depend on the
classical randomness with which each of these parameters is chosen.

Another natural extension of our work would be to prove noise-resilience for
general noise maps (including stochastic noise maps). We believe that this
would involve construction and the use of approximate $t$-design completely
positive trace preserving (CPTP) channels instead of the approximate
$t$-design unitaries that we consider in this work. This is due to the fact
that a general noise map in the Kraus formulation is written as a general CPTP
map. Hence it is important to prove that the noisy general CPTP QPUF would
satisfy the required security notions.

##  7 Acknowledgements

We thank Mina Doosti, Mahshid Delavar and Myrto Arapinis for useful
discussions. We acknowledge the support by the Engineering and Physical
Sciences Research Council (grant EP/L01503X/1), Engineering and Physical
Sciences Research Council Hub in Quantum Computing and Simulation EP/T001062/1
grant, and Verification of Quantum Technology (grant EP/N003829/1).

## References

  * 1 Claude E Shannon.  A mathematical theory of communication.  The Bell system technical journal, 27(3):379–423, 1948.
  * 2 Jonathan Katz and Yehuda Lindell.  Introduction to modern cryptography.  CRC press, 2020.
  * 3 Oded Goldreich.  Modern cryptography, probabilistic proofs and pseudorandomness, volume 17.  Springer Science & Business Media, 1998.
  * 4 Wenbo Mao.  Modern cryptography: theory and practice.  Pearson Education India, 2003.
  * 5 Ran Canetti and Marc Fischlin.  Universally composable commitments.  In Annual International Cryptology Conference, pages 19–40. Springer, 2001.
  * 6 Myrto Arapinis, Mahshid Delavar, Mina Doosti, and Elham Kashefi.  Quantum physical unclonable functions: Possibilities and impossibilities.  arXiv preprint arXiv:1910.02126v1, 2019.
  * 7 Boris Škorić.  Quantum readout of physical unclonable functions.  International Journal of Quantum Information, 10(01):1250001, 2012\.
  * 8 Robert James Young, Jonny Roberts, and Utz Roedig.  Quantum physical unclonable function, 2016.
  * 9 Georgios M Nikolopoulos and Eleni Diamanti.  Continuous-variable quantum authentication of physical unclonable keys.  Scientific reports, 7:46047, 2017.
  * 10 Giulio Gianfelici, Hermann Kampermann, and Dagmar Bruß.  Theoretical framework for physical unclonable functions, including quantum readout.  Physical Review A, 101(4):042337, 2020.
  * 11 Mina Doosti, Niraj Kumar, Mahshid Delavar, and Elham Kashefi.  Client-server identification protocols with quantum puf.  arXiv preprint arXiv:2006.04522, 2020.
  * 12 Yao Yao, Ming Gao, Mo Li, and Jian Zhang.  Quantum cloning attacks against puf-based quantum authentication systems.  Quantum Information Processing, 15(8):3311–3325, 2016.
  * 13 Boris Škorić, Allard P Mosk, and Pepijn WH Pinkse.  Security of quantum-readout pufs against quadrature-based challenge-estimation attacks.  International journal of quantum information, 11(04):1350041, 2013\.
  * 14 Emanuel Knill.  Approximation by quantum circuits.  arXiv preprint quant-ph/9508006, 1995.
  * 15 Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine.  Exact and approximate unitary 2-designs and their application to fidelity estimation.  Physical Review A, 80(1):012304, 2009.
  * 16 Fernando GSL Brandao, Aram W Harrow, and Michał Horodecki.  Local random quantum circuits are approximate polynomial-designs.  Communications in Mathematical Physics, 346(2):397–434, 2016.
  * 17 Jeffrey M Epstein, Andrew W Cross, Easwar Magesan, and Jay M Gambetta.  Investigating the limits of randomized benchmarking protocols.  Physical Review A, 89(6):062321, 2014.
  * 18 Patrick Hayden, Debbie Leung, Peter W Shor, and Andreas Winter.  Randomizing quantum states: Constructions and applications.  Communications in Mathematical Physics, 250(2):371–391, 2004.
  * 19 Patrick Hayden and John Preskill.  Black holes as mirrors: quantum information in random subsystems.  Journal of high energy physics, 2007(09):120, 2007.
  * 20 Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert.  Anticoncentration theorems for schemes showing a quantum speedup.  Quantum, 2:65, 2018.
  * 21 Aram Harrow and Saeed Mehraban.  Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates.  arXiv preprint arXiv:1809.06957, 2018.
  * 22 Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert.  Architectures for quantum simulation showing a quantum speedup.  Physical Review X, 8(2):021010, 2018.
  * 23 Fernando GSL Brandao, Aram W Harrow, and Michał Horodecki.  Local random quantum circuits are approximate polynomial-designs.  Communications in Mathematical Physics, 346(2):397–434, 2016.
  * 24 Michał Oszmaniec, Adam Sawicki, and Michał Horodecki.  Epsilon-nets, unitary designs and random quantum circuits.  arXiv preprint arXiv:2007.10885, 2020.
  * 25 Robert Raussendorf and Hans J Briegel.  A one-way quantum computer.  Physical Review Letters, 86(22):5188, 2001.
  * 26 Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham.  Fault-tolerant quantum speedup from constant depth quantum circuits.  arXiv preprint arXiv:2005.11539, 2020.
  * 27 John Preskill.  Quantum computing in the nisq era and beyond.  Quantum, 2:79, 2018.
  * 28 Frederik Armknecht, Daisuke Moriyama, Ahmad-Reza Sadeghi, and Moti Yung.  Towards a unified security model for physically unclonable functions.  In Cryptographers’ Track at the RSA Conference, pages 271–287. Springer, 2016.
  * 29 Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine.  Exact and approximate unitary 2-designs and their application to fidelity estimation.  Physical Review A, 80(1):012304, 2009.
  * 30 Eiichi Bannai, Mikio Nakahara, Da Zhao, and Yan Zhu.  On the explicit constructions of certain unitary t-designs.  Journal of Physics A: Mathematical and Theoretical, 52(49):495301, 2019.
  * 31 Eiichi Bannai, Yoshifumi Nakata, Takayuki Okuda, and Da Zhao.  Explicit construction of exact unitary designs.  arXiv preprint arXiv:2009.11170, 2020.
  * 32 Aram Harrow and Saeed Mehraban.  Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates.  arXiv preprint arXiv:1809.06957, 2018.
  * 33 Kelly Wieand.  Eigenvalue distributions of random unitary matrices.  Probability Theory and Related Fields, 123(2):202–224, 2002.
  * 34 Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham.  Efficient quantum pseudorandomness with simple graph states.  Physical Review A, 97(2):022333, 2018.
  * 35 Jonas Haferkamp, Dominik Hangleiter, Adam Bouland, Bill Fefferman, Jens Eisert, and Juani Bermejo-Vega.  Closing gaps of a quantum advantage with short-time hamiltonian dynamics.  arXiv preprint arXiv:1908.08069, 2019.
  * 36 Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham.  On unitary t-designs from relaxed seeds.  Entropy, 22(1):92, 2020.
  * 37 Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham.  Efficient approximate unitary t-designs from partially invertible universal sets and their application to quantum speedup.  arXiv preprint arXiv:1905.01504, 2019.
  * 38 BP Lanyon, P Jurcevic, M Zwerger, C Hempel, EA Martinez, W Dür, HJ Briegel, Rainer Blatt, and Christian F Roos.  Measurement-based quantum computation with trapped ions.  Physical review letters, 111(21):210501, 2013.
  * 39 Jean-Luc Brylinski and Ranee Brylinski.  Universal quantum gates.  Mathematics of quantum computation, 79, 2002.
  * 40 Robin J Blume-Kohout.  How distinguishable are two quantum processes?.  Technical report, Sandia National Lab.(SNL-NM), Albuquerque, NM (United States), 2015.
  * 41 Richard A Low.  Pseudo-randomness and learning in quantum computation.  arXiv preprint arXiv:1006.5227, 2010.