# Unclonability and Quantum Cryptanalysis: From Foundations to Applications

Mina Doosti

###### Abstract

The impossibility of creating perfect identical copies of unknown quantum
systems is a fundamental concept in quantum theory and one of the main non-
classical properties of quantum information. This limitation imposed by
quantum mechanics, famously known as the no-cloning theorem, has played a
central role in quantum cryptography as a key component in the security of
quantum protocols. In this thesis, we look at Unclonability in a broader
context in physics and computer science and more specifically through the lens
of cryptography, learnability and hardware assumptions. We introduce new
notions of unclonability in the quantum world, namely quantum physical
unclonability, and study the relationship with cryptographic properties and
assumptions such as unforgeability, randomness and pseudorandomness. The
purpose of this study is to bring new insights into the field of quantum
cryptanalysis and into the notion of unclonability itself. We also discuss
applications of this new type of unclonability as a cryptographic resource for
designing provably secure quantum protocols.

First, we study the unclonability of quantum processes and unitaries in
relation to their learnability and unpredictability. The instinctive idea of
unpredictability from a cryptographic perspective is formally captured by the
notion of unforgeability. Intuitively, unforgeability means that an adversary
should not be able to produce the output of an unknown function or process
from a limited number of input-output samples of it. Even though this notion
is almost easily formalized in classical cryptography, translating it to the
quantum world against a quantum adversary has been proven challenging. One of
our contributions is to define a new unified framework to analyse the
unforgeability property for both classical and quantum schemes in the quantum
setting. This new framework is designed in such a way that can be readily
related to the novel notions of unclonability that we will define in the
following chapters. Another question that we try to address here is ”What is
the fundamental property that leads to unclonability?” In attempting to answer
this question, we dig into the relationship between unforgeability and
learnability, which motivates us to repurpose some learning tools as a new
cryptanalysis toolkit. We introduce a new class of quantum attacks based on
the concept of ‘emulation’ and learning algorithms, breaking new ground for
more sophisticated and complicated algorithms for quantum cryptanalysis.

Second, we formally represent, for the first time, the notion of physical
unclonability in the quantum world by introducing Quantum Physical Unclonable
Functions (qPUF) as the quantum analogue of Physical Unclonable Functions
(PUF). PUF is a hardware assumption introduced previously in the literature of
hardware security, as physical devices with unique behaviour, due to
manufacturing imperfections and natural uncontrollable disturbances that make
them essentially hard to reproduce. We deliver the mathematical model for
qPUFs, and we formally study their main desired cryptographic property, namely
unforgeability, using our previously defined unforgeability framework. In
light of these new techniques, we show several possibility and impossibility
results regarding the unforgeability of qPUFs. We will also discuss how the
quantum version of physical unclonability relates to randomness and
unknownness in the quantum world, exploring further the extended notion of
unclonability.

Third, we dive deeper into the connection between physical unclonability and
related hardware assumptions with quantum pseudorandomness. Like unclonability
in quantum information, pseudorandomness is also a fundamental concept in
cryptography and complexity. We uncover a deep connection between Pseudorandom
Unitaries (PRU) and quantum physical unclonable functions by proving that both
qPUFs and the PRU can be constructed from each other. We also provide a novel
route towards realising quantum pseudorandomness, distinct from computational
assumptions.

Next, we propose new applications of unclonability in quantum communication,
using the notion of physical unclonability as a new resource to achieve
provably secure quantum protocols against quantum adversaries. We propose
several protocols for mutual entity identification in a client-server or
quantum network setting. Authentication and identification are building-block
tasks for quantum networks, and our protocols can provide new resource-
efficient applications for quantum communications. The proposed protocols use
different quantum and hybrid (quantum-classical) PUF constructions and quantum
resources, which we compare and attempt in reducing, as much as possible
throughout the various works we present. Specifically, our hybrid construction
can provide quantum security using limited quantum communication resources
that cause our protocols to be implementable and practical in the near term.

Finally, we present a new practical cryptanalysis technique concerning the
problem of approximate cloning of quantum states. We propose variational
quantum cloning ($\operatorname{\textsf{VarQlone}}$), a quantum machine
learning-based cryptanalysis algorithm which allows an adversary to obtain
optimal (approximate) cloning strategies with short depth quantum circuits,
trained using the hybrid classical-quantum technique. This approach enables
the end-to-end discovery of hardware efficient quantum circuits to clone
specific families of quantum states, which has applications in the foundations
and cryptography. In particular, we use a cloning-based attack on two quantum
coin-flipping protocols and show that our algorithm can improve near term
attacks on these protocols, using approximate quantum cloning as a resource.
Throughout this work, we demonstrate how the power of quantum learning tools
as attacks on one hand, and the power of quantum unclonability as a security
resource, on the other hand, fight against each other to break and ensure
security in the near term quantum era.

### Lay summary

One of the most routine tasks we do almost every day on our computers is
copying a file. A computer file contains information in the form of a string
of zeros and ones. But, what if instead of a normal file, data was encoded
inside a tiny physical system? In fact, a system from the subatomic world
where different rules of physic would apply to it. The set of rules in that
scale is known as the theory of quantum mechanics, and quantum mechanics says
that if you have a ‘quantum file’, it is forbidden to copy it! This
fundamental rule of physics called the ‘no-cloning theorem’, or unclonability,
while seemingly very limiting, is a very convenient property of nature. It
allows us to conceal information and share it securely. Controlling quantum
systems for the secure transmission of information and similar cryptographic
tasks is called quantum cryptography.

On the other hand, we can also control these subatomic systems to perform
computation, leading to physical devices known as quantum computers that
perform computational tasks in a fundamentally different way from any
‘classical’ computer. Despite applications in many areas, such as solving some
mathematical problems, optimizing some operations, and simulating complex
molecules, quantum computers do not bring good news for our cryptosystems. For
the same reason that they are efficient in solving some mathematical problems,
they can break many of today’s cryptosystems as they are based on the
assumption that solving those problems would take too long time to be
feasible.

Even given the long and challenging technological road ahead of building
quantum computers, there has been incredible progress in recent years that has
brought the idea of quantum computing to reality. Today’s quantum computers,
although ‘small’ in scale and ‘low’ in quality, can perform interesting tasks
even now. Plus, we believe that sooner or later, we will get to the regime
where quantum computers will surpass the limit of computation for any
classical computers. Thus we need to be prepared for the threats that they
will bring on.

The study of cryptography, in the near future, where we can both exploit
quantum systems in our favour and will be at risk due to their computational
power, is the art and science called quantum cryptanalysis. To master this
art, one needs to understand the strengths and limitations of quantum systems.
As such, the unclonability will be at the heart of it.

In this thesis, we study quantum unclonability beyond its usual scope. We
explore other forms of natural unclonability that not only, are fundamentally
connected to no-cloning, but can also be exploited for cryptography. An
example of unclonable objects is optical devices that are particularly unique
since their formation or manufacturing processes involve factors that we
cannot control. As a result, they become physical devices that are not
reproducible. This uniqueness makes them also a physical key. These physically
unclonable objects can be modelled in the regime of quantum mechanics. A major
part of this thesis includes the comprehensive study of them in the quantum
regime, their several interesting properties, and finally, their applications
in cryptography.

We also explore the relationship between unclonability and learning, that is
how efficiently one can learn a quantum or classical system. In this research
area, we use different tools from other fields of physics and computer
science, such as machine learning. Specifically, we show that we can make a
quantum machine to learn how to efficiently create an ’almost’ satisfactory
copy of a quantum system. This machine-learning algorithm can be used to
attack the security of protocols. These attack analyses give a better
perspective on the security of cryptosystems with current and future quantum
technology and help us design our systems more securely.

### Publications and manuscripts

The author has contributed to the following papers and publications in the
course of her doctoral program.

Fully or partially included in this thesis:

  1. 1.

Quantum physical unclonable functions: Possibilities and impossibilities.
Quantum 5 (2021)[8]
Myrto Arapinis, Mahshid Delavar, Mina Doosti, and Elham Kashefi
DOI:10.22331/q-2021-06-15-475

  2. 2.

On the connection between quantum pseudorandomness and quantum hardware
assumptions. Quantum Science and Technology 7.3 (2022)[160]
Mina Doosti, Niraj Kumar, Elham Kashefi, and Kaushik Chakraborty
DOI:10.1088/2058-9565/ac66fb

  3. 3.

Client-server identification protocols with quantum PUF. ACM Transactions on
Quantum Computing 2.3 (2021)[158]
Mina Doosti, Niraj Kumar, Mahshid Delavar, and Elham Kashefi
DOI:10.1145/3484197

  4. 4.

Progress toward practical quantum cryptanalysis by variational quantum
cloning. Physical Review A 105.4 (2022)[108]
Brian Coyle, Mina Doosti, Elham Kashefi, and Niraj Kumar
DOI:10.1103/PhysRevA.105.042604

  5. 5.

A Unified Framework For Quantum Unforgeability. arXiv preprint (2021)[140]
Mina Doosti, Mahshid Delavar, Elham Kashefi, and Myrto Arapinis
Arxiv:2103.13994

  6. 6.

Quantum Lock: A Provable Quantum Communication Advantage. arXiv preprint
(2021)[110]
Kaushik Chakraborty, Mina Doosti, Yao Ma, Myrto Arapinis, and Elham Kashefi
Arxiv:2110.09469

Excluded from this thesis:

  7. 7.

Differential Privacy Amplification in Quantum and Quantum-inspired Algorithms.
arXiv preprint (2022) / workshop paper (SRML)[9]
Armando Angrisani, Mina Doosti, Elham Kashefi
Arxiv:2203.03604

###### Acknowledgements.

I do not believe that PhD is a one-man (or, in this case, one-woman) journey,
or at least it has not been so for me. If I have reached the centre of this
spiral, it has been the result of many fortunate ’environmental factors’ and
’lucky interactions’ with amazing people I met along the way (just like a
lucky quantum state that has finally collapsed to the right state). So I do
not intend to keep this acknowledgement short, by no means. First and
foremost, I have to thank my supervisors, Elham Kashefi and Myrto Arapinis,
the two brilliant, enthusiastic, inspiring and, certainly lovely women I have
had the honour to spend my PhD under their supervision. I can never be
thankful enough for their non-stop support, their patience, their insightful
pieces of advice, and for being much more than just advisors to me. Starting
my PhD and coming from a physics background, I have been an outsider to
computer science and cryptography. This thesis is the product of their
tireless effort in transforming me into the hybrid creature that I am now.
Elham, who never came short on thrilling ideas, whose energy always awed me,
and who taught me how to be an independent researcher. Myrto, who patiently
educated me to appreciate ’formal’ mathematical frameworks and taught me how
to think like a cryptographer, and, was there for me in all the ups and downs.
I also greatly thank Anne Broadbent, and Petros Wallden, my PhD examiners for
their valuable comments on this thesis. Although I cannot only thank Petros
for being my examiner, a special thank goes to him, as he is one of the most
intelligent men I have met during my PhD, who never withheld me his time,
someone whom I could always go to with my questions about almost any topic,
and whom I learned a lot from, and with whom I have had countless hours of
fruitful discussions, and pleasant conversations. My PhD would have not been
the same without him. I should also thank other faculties of the quantum group
at the University of Edinburgh: Raul Garcia-Patron Sanchez and Chris Heunen,
as I greatly benefited from their wisdom and insight during my time as a PhD
student. I appreciate having the opportunity to study and research in such a
generous environment. While almost half of my PhD collided with the covid
pandemic and was spent at home, in the other half, I gathered many good
memories from my time at the Informatic Forum and all the people there. I also
would like to thank Marc Kaplan, my mentor at VeriQloud, for his support and
mentorship. Then, of course, I should thank the comrades, the members of our
amazing quantum group over these years, a group that not even a global
pandemic could diminish its merit: First, Alex Cojocaru, who is like my
brother, who knows how much I am thankful for his kindness, his friendship and
his help all the way to the end, and I thank him also for giving me feedback
on this thesis. Mahshid Delavar and Meisam Tarabkhah, for being such all-in
friends, and in a way, my family here. Niraj Kumar, who not only was a mentor
to me but a fantastic colleague and friend. Brian Coyle, as he truly deserves
his title of ”the most efficient man in the group”, as he is a brilliant
researcher and caring friend whom I have learned a lot from. Kaushik
Chakraborty, my smart, patient and wonderful colleague, office-mate and
friend, whom I greatly enjoyed working with. Atul Mantri, who despite his
short time in the group, was one of the most memorable persons, as he is
clever in his work and humour equally. Ellen Derbyshire, for the unique
kindness and company she always offered me. Yao Ma, my awesome colleague and
friend with all the exciting memories we made together. Rawad Mehzer, an
equally clever and deep man whom I always enjoyed having a conversation with.
Daniel Mills, a character that I will always respect and never forget. James
Mills, with whom I spent memorable times. Ieva Cepaite, a cheerful and free
soul. And I also thank Ross Grassie, Sima Bahrani, Theodoros Kapourniotis,
Debasis Sadhukhan, other amazing postdocs that I had the pleasure to know in
the group and discuss with, as well as Pablo Andrés-Martinez and Nuiok Dicaire
from the extended Edinburgh quantum group. And that is not all, since our
group is a highly non-local one, with half of the entangled pair in Paris. I
should extend my thanks to Dominik Leichtle, Léo Colisson, Ulysse Chabaud,
Shraddha Singh, Armando Angrisani, Jonas Landman, Pierre-Emmanuel Emariau,
Luka Music, Raja Yehia, Damian Markham, Harold Ollivier, Fred Groshans, Eleni
Diamanti with all of whom I have great memories and interactions. I am perhaps
one of the luckiest human beings in having friends whose friendship expands
over space-time. I start with my friends in Iran: to Armita, my best friend,
the ever-present being in my life despite the distance, and my companion
through all the pains and joys, and she knows what else. To Alma and Aria,
because thinking about them (and our memories of 225) has always been the most
heart-warming thought. To Laaya, Nima, Babak, Alireza and Ghazal, as they all
have their own special place for me. I also thank Azadeh, our ever-supportive
and great friend. Then I thank the lovely people I have met here: Mohammad and
Lucy, for all the pleasing times we have spent in these years, and to Ségo,
for being such a beautiful person who she is and for all the music we played
together and all the things we shared. And finally, among friends, I thank my
dearest friend, who knows who he is, and although he might find it dull if he
ever reads this page, I can’t go on without thanking him as he has been such a
great friend to me during the toughest parts of this. I give my sincere thanks
to my mom and dad, my biggest supporters, who never ceased to encourage me
during this time, even from the other side of the world, and I thank them for
everything they have done for me in my life and for enduring the best and
worst of me. And as I will keep the best for the last, I thank Ramin, my love,
my partner in life and crime, and my closest, most reliable company. Without
him and his endless support, his love, and his beautiful mind, I probably
would not be where I am now, let alone finishing this thesis and this period.
Although no gratitude would do justice to what he has been for me all these
years, I am glad that I have this chance to properly thank him.

To Ramin, my love,
And to every being who seeks knowledge and beauty.

###### Contents

  1. 1 Introduction
    1. 1.1 Thesis overview
  2. 2 Preliminaries
    1. 2.1 Quantum information and quantum computing
      1. 2.1.1 Quantum states and Hilbert space
      2. 2.1.2 Mixed states and density matrices
      3. 2.1.3 Quantum operations and measurements
      4. 2.1.4 Distance measures
      5. 2.1.5 Entropic uncertainty relations
      6. 2.1.6 Quantum computing
    2. 2.2 Distinguishability and verification of quantum states
      1. 2.2.1 Verifying quantum states
    3. 2.3 Quantum cloning
      1. 2.3.1 Cloning beyond the no-cloning theorem
    4. 2.4 Haar measure and random matrix theory
    5. 2.5 Quantum cryptography
      1. 2.5.1 Formal frameworks for cryptanalysis
      2. 2.5.2 Adversarial models in the quantum world
      3. 2.5.3 Quantum accessible oracles for classical functions
      4. 2.5.4 Classical pseudorandomness
      5. 2.5.5 Quantum pseudorandomness
      6. 2.5.6 Unforgeability
      7. 2.5.7 Coin-flipping
    6. 2.6 Quantum and classical learning
      1. 2.6.1 Quantum state and process tomography
      2. 2.6.2 Quantum Emulation
      3. 2.6.3 Learning theory
      4. 2.6.4 Quantum machine learning and variational algorithms
  3. 3 Unclonability, Unforgeability and Learnability
    1. 3.1 Introduction
      1. 3.1.1 Structure of the chapter
    2. 3.2 Unclonability and Unknownness
      1. 3.2.1 From unclonability of quantum states to unclonability of transformations
    3. 3.3 Unclonability and different notions of learning
      1. 3.3.1 Learning, forging and emulation
      2. 3.3.2 Unforgeability and unclonability
      3. 3.3.3 Unforgeability and learnability with quantum oracles
    4. 3.4 Universal quantum emulator revisited
      1. 3.4.1 Output fidelity analysis
      2. 3.4.2 Quantum Emulation Attacks
    5. 3.5 A unified framework for quantum unforgeability
      1. 3.5.1 Framework and Formal definitions
      2. 3.5.2 Hierarchy and relationship to other definitions
      3. 3.5.3 Unforgeability against weak vs adaptive adversaries
    6. 3.6 Applications of qGU: possibility and impossibility results
      1. 3.6.1 Generalised existentially unforgeable schemes
      2. 3.6.2 Generalised selectively unforgeable schemes
      3. 3.6.3 Generalised universally unforgeable schemes
    7. 3.7 Discussion and conclusions
  4. 4 Quantum Physical Unclonable Functions
    1. 4.1 Introduction
      1. 4.1.1 Structure of the chapter
      2. 4.1.2 Related works
    2. 4.2 Background on classical Physical Unclonable Functions
    3. 4.3 Quantum Physical Unclonable Functions
    4. 4.4 Cryptanalysis of Quantum Physical Unclonable Functions
      1. 4.4.1 Impossibility of exponential unforgeability for UqPUFs
      2. 4.4.2 Impossibility of existential unforgeability for UqPUFs
      3. 4.4.3 Universal unforgeability of UqPUFs
      4. 4.4.4 A note on the unforgeability of quantum PUFs with public database
    5. 4.5 Discussion and conclusions
      1. 4.5.1 Subsequent works
  5. 5 Connection Between Quantum Pseudorandomness and Quantum Hardware Assumptions
    1. 5.1 Introduction
      1. 5.1.1 Structure of the chapter
    2. 5.2 Efficient unforgeability with PRSs
    3. 5.3 From pseudorandom unitaries to UU and UqPUFs
    4. 5.4 Pseudorandom unitaries and states from hardware assumptions
    5. 5.5 Discussion and conclusions
  6. 6 Applications of Quantum Physical Unclonable Functions
    1. 6.1 Introduction
      1. 6.1.1 Structure of the chapter
      2. 6.1.2 Related works
    2. 6.2 Quantum-secure identification protocols using quantum PUF
      1. 6.2.1 General description of device-based identification protocol
      2. 6.2.2 Quantum identification protocol with high-resource verifier
      3. 6.2.3 Quantum identification protocol with low-resource verifier
      4. 6.2.4 Generalisation of low-resource protocol to arbitrary distribution of traps
      5. 6.2.5 Resource comparison of protocols
    3. 6.3 Towards more efficient qPUF-based identification protocols
    4. 6.4 Hybrid PUF: A practical solution
      1. 6.4.1 CPUF model
      2. 6.4.2 Construction for Hybrid PUF
      3. 6.4.3 Hybrid Locked PUF
      4. 6.4.4 Quantum identification protocol using Hybrid Locked PUF
      5. 6.4.5 Security analysis
      6. 6.4.6 Challenge re-usability
    5. 6.5 Discussion and conclusions
  7. 7 Variational Quantum Cloning: A New Cryptanalysis Toolkit
    1. 7.1 Introduction
      1. 7.1.1 Structure of the chapter
    2. 7.2 Quantum cryptanalysis based on different classes of cloning
      1. 7.2.1 Cryptanalysis based on phase-covariant cloning
      2. 7.2.2 Cryptanalysis based on state-dependent cloning
    3. 7.3 Variational Quantum Cloner: specifications of the algorithm
      1. 7.3.1 Cost functions
      2. 7.3.2 Cost function gradients
      3. 7.3.3 Cost function guarantees
      4. 7.3.4 Summary of other specifications
    4. 7.4 Practical cryptanalysis based on the numerical results of VarQlone
      1. 7.4.1 Variational phase-covariant cloning
      2. 7.4.2 Variational state-dependent cloning
    5. 7.5 Discussion and conclusions
  8. 8 Conclusion
  9. A Additional proofs and derivations
    1. A.1 Proof of Theorem 13 in Chapter 3
    2. A.2 Proof of Theorem 15 in Chapter 3
    3. A.3 Proof of Theorem 16 in Chapter 3
    4. A.4 Alternative model for an adaptive quantum adversary
    5. A.5 Proof of Theorem 23 in Chapter 3
    6. A.6 Calculation of the cost function’s gradient for $\operatorname{\textsf{VarQlone}}$

###### List of Figures

  1. 2.1 The Bloch sphere (figure from: [408])
  2. 2.2 The SWAP test circuit
  3. 2.3 The circuit of GSWAP
  4. 2.4 Cartoon illustration of a cloning-based eavesdropping attack by Eve, trying to clone the state, $\rho_{A}$, Alice sends to Bob
  5. 2.5 Ideal cloning circuit for universal and phase covariant cloning. The Preparation circuit prepares Eve’s system to receive the cloned states, while the Cloning circuit transfers information. Notice that the output registers which contain the two clones of $\ket{\psi}_{A}$ to Bob and Eve in this circuit are registers $2$ and $3$ respectively.
  6. 2.6 Haar measure and non-uniform sampling over the Bloch sphere
  7. 2.7 Quanutm emulation vs. quantum simulation
  8. 2.8 The circuit of the quantum emulation algorithm.
  9. 3.1 Illustration of ‘unknownness’ property of quantum states and measurement
  10. 3.2 Relationship between different definitions of _Generalised Quantum Unforgeability_ , BU and BZ
  11. 3.3 The winning probability of $\mathcal{A}$ to forge classical messages $\\{m_{2},m_{3}\\}$ with the emulation attack.
  12. 3.4 A sample circuit for randomised quantum oracle for quantum primitives
  13. 4.1 Illustration of the concept of a physical unclonable function
  14. 4.2 Illustration of qPUF as a unitary operation with input and output quantum states
  15. 5.1 Connection between different notions of quantum pseudorandomness, unknownness, and efficient universal unforgeability
  16. 5.2 Proof sketch of Theorem 30 with the intermediate games.
  17. 6.1 qPUF-based identification protocol with high-resource verification
  18. 6.2 qPUF-based identification protocol with low-resource verifier and classical verification
  19. 6.3 Probability comparison for different classical adversarial strategies against lrv-id
  20. 6.4 Quantum collective attack strategy on lrv-id
  21. 6.5 Quantum coherent attack strategy on lrv-id
  22. 6.6 Behaviour of Eve’s success probability $\text{Pr}[\text{Ver accept}_{\text{Eve}}]$ as a function of $p$ (corresponding to number of valid qPUF responses), for different values of $N$.
  23. 6.7 Comparison of the resources required by the prover and verifier in the three qPUF-based identification protocols (hrv-id-swap, hrv-id-gswap, and lrv-id)
  24. 6.8 Comparison of verification based on SWAP and GSWAP for identification protocols
  25. 6.9 Hybrid Locked PUF (HLPUF) $\mathcal{E}^{L}_{f}$ with Construction 4
  26. 7.1 States used for quantum coin-flipping. The first bit represents the _basis_ , while the other represents one of the two orthogonal states.
  27. 7.2 Cartoon overview of $\operatorname{\textsf{VarQlone}}$ in a cryptographic attack
  28. 7.3 Variational Quantum Cloning implemented on phase-covariant states using three qubits of the Rigetti Aspen-8 chip (QPU), plus simulated results (QVM)
  29. 7.4 Overview of cloning-based attack on the protocol of Mayers et. al. [307], plus corresponding numerical results for $\operatorname{\textsf{VarQlone}}$
  30. 7.5 Circuit learned by $\operatorname{\textsf{VarQlone}}$ in to clone states, $\ket{\phi_{0}},\ket{\phi_{1}}$, with an overlap $s=\cos\left(\pi/9\right)$ in the protocol, $\mathcal{P}_{1}$
  31. 7.6 Cloning attacks and numerical results for the protocol, $\mathcal{P}_{2}$
  32. 7.7 Clone fidelities for optimal circuits learned by $\operatorname{\textsf{VarQlone}}$ for (a) $1\rightarrow 3$ and (b) $2\rightarrow 4$ cloning of the states used in the coin-flipping protocols
  33. 7.8 Circuits learned by $\operatorname{\textsf{VarQlone}}$ to clone states from the protocol, $\mathcal{P}_{2}$

##  Chapter 1 Introduction

“See that the imagination of nature is far, far greater than the imagination
of man.”

– Richard Feynman

One of the most impactful scientific revolutions of the 20th century was the
development of quantum mechanics. Revolutionary discoveries about the
behaviour of light and matter in the late 19th and early 20th centuries, not
explainable by existing knowledge of physics by that time, or what we call
today _classical physics_ , led to a need for a completely new theory.
Arguably, the most important among these was the illumination of the nature of
light by Planck in 1900 and the photoelectric effect between 1883 and 1900.
These physical phenomena that classical physics has still to date failed to
explain have created one of those mutually horrifying and exciting situations
in science: the sparks of _maybe we got it all wrong!_

Fanning the flames of this idea led to the birth of the main concepts of
quantum theory and eventually to a well-established formalisation of quantum
mechanics as we know it today. Quantum theory has changed our mindset and
understanding of nature to a great degree. Even though it has gracefully and
even surprisingly explained those phenomena which classical physics fell short
in describing, it did so at the cost of being counter-intuitive and odd to our
_classical_ minds. It comes with predictions about nature, not as it appears
in our everyday life, but as Richard Feynman famously put it “nature, … she is
absurd” [354]. Quantum mechanics left our human mind with questions and
mysteries about _probabilistic nature of observation_ , _non-locality_ ,
_unclonability_ (which is the core topic of this thesis), and many more to
ponder about over the years.

Attempting to unravel some of the mysteries of quantum mechanics led to the
appearance of quantum information theory [316], which takes an information
theory approach to study quantum systems. This new field, together with the
rise of quantum computation, has engaged physicists, mathematicians, and
computer scientists with new fundamental questions about the concept of
computation and the differences between classical and quantum versions of it
[5]. Quantum information, in its simplest form, starts with the idea of
considering discrete quantum systems as carriers of information and treating
them as quantum versions of the binary systems we use for the storage and
manipulation of information. However, the field expands extensively beyond
this humble foundation and incorporates the full framework of information
theory and many other powerful mathematical tools such as probability theory,
group theory, representation theory and so on. Using all this powerful
machinery, quantum information sheds a light on complicated problems of
dealing with quantum properties of nature. Thanks to quantum information, we
have now developed a much better understanding of these problems to the point
that most of them are no longer mysteries, even if still strange. The idea of
quantum computing, on the other hand, emerged from the idea of using physical
quantum mechanical systems to simulate themselves. A task that seemed to be
too hard to simulate using classical digital computers. This idea was
introduced by Feynman111Although not all the credit should be given to Mr
Feynman! The idea of quantum computing in other forms, was also mentioned by
Yuri Manin [282] and Paul Benioff [56] in 1980. in 1981, at a conference where
he talks about the difficulties of such simulations and asks “Can you do it
with a _new kind_ of computer? A quantum computer?”[346].

To realise Feynman’s groundbreaking idea would require us to understand this
_new kind_ of computation and to eventually acquire the ability to control
quantum systems for performing our desired computational or simulation task.
Obtaining this ability, as Feynman has predicted “doesn’t look easy”, and
almost 40 years of relentless research (from his talk) has proved to be truly
the case. Notwithstanding the unresolved challenges of controlling quantum
systems, there has been remarkable progress in this area, especially in recent
years. One of the main challenges is to achieve quantum computers able to
perform useful computational tasks, outside the reach of classical computers,
which requires a considerably large scale and a high level of control over
such systems. In 2019 the Google AI Quantum group announced their quantum
computer, with 53 working qubits, has surpassed this limit and has achieved
what is famously known as _quantum supremacy_ or _quantum advantage_ in the
realm of computation [1]. Despite the scepticism and critics about this result
[233, 223, 359], it is an undeniable indication of an important fact: quantum
computers are no longer just an idea, and we have entered a new era. More
specifically, this new era is named NISQ, standing for _Noisy Intermediate-
Scale Quantum_ devices [345]. The NISQ devices provide on the orders of 10s to
100 noisy qubits, but they can exploit the quantum behaviours of light or
matter to execute _some limited_ quantum programs. Although limited, they can
provide a _laboratory_ for theoretical research in the field of quantum
computation and quantum information that was not possible until very recently.

The future large-scale quantum computers, on the other hand, are believed to
have significant quantum advantages over classical computers for some specific
problems, which are not limited to the simulation of physical systems. The
range of problems we hope to be able to solve more efficiently with quantum
computers extends to decision problems, search problems and learning problems.
The ability to solve these problems, not just faster, but perhaps _in a
different way_ , using quantum properties, has already and will continue to
impact many areas of physics, computer science, chemistry [278, 133, 289],
biology [172, 131, 328], and even linguistics [224, 124, 310, 291]. One of the
fields that has been hugely affected by quantum computing and quantum
information is _cryptography_. Quantum mechanics has a rather fascinating and
somewhat contradictory relationship with cryptography. When quantum steps into
the realm of cryptography, not only does it threaten security, but it may as
well enhance it! But most definitely, it has changed the way one can look at
cryptography, as it has done with computation. Let us first start with the
negative side of the story.

It is well-known that Shor’s quantum algorithm [372] menaces many widely-used
cryptographic schemes that are based on the mathematical hardness assumptions
of factoring and the discrete logarithm problems (such as RSA). A sufficiently
large, fault-tolerant and universal quantum computer will be able to run this
algorithm and solve these problems efficiently [410]. Furthermore, Shor’s
algorithm is not the only quantum algorithm that can be used as an attack on
classical cryptography schemes. Other famous algorithms, such as Grover or
Simon, have also been used for this purpose [69, 248, 231, 269, 198, 19].
Generally speaking, a quantum computer can be seen as a powerful computational
resource in the hands of an attacker. Yet, this extra computational power is
not the only aspect that can raise an issue. An adversary who has been given
the possibility to exploit non-classical properties of quantum data may as
well, have other advantages. For example, a quantum adversary can also use
entanglement to extract crucial information from a system or use the power of
quantum superposition while interacting with cryptosystems. Hence a very
central question to ask is _What are the possible advantages of an attacker
equipped with quantum capabilities?_ Answering this question, in full
generality, is brutally challenging and requires a profound understanding of
the underlying assumptions (both computational and physical) of cryptographic
schemes, as well as the new potential ways for these quantum capabilities to
be exploited to break them. Nevertheless, partially addressing this question
is one of the central ideas of this thesis.

On the bright side, quantum mechanics and its odd properties provide us with a
new way of achieving cryptographic functionalities, or that is to say, a
fundamentally distinct type of cryptography: one that is based on the laws of
quantum mechanics and the limitations that it imposes on the adversary. The
field of research that studies this direction is known as _quantum
cryptography_. The most well-known problem studied in this field is _Quantum
Key Distribution (QKD)_ , a protocol that enables two remote parties to
establish a secure key by relying on the characteristics of quantum mechanics
[35] in the presence of the most possibly powerful quantum adversary. Perhaps
one of the most intriguing aspects of QKD is that, under a carefully specified
set of assumptions and requirements about the underlying physical systems, it
provably achieves the strongest known level of security without any
computational assumptions. QKD, however, is not the only example of what
quantum cryptography can bring to the table. For example, the wide range of
capabilities that quantum features equip us with has motivated the
construction of networks where the nodes are armed with the ability to
transmit, store and manipulate small quantities of quantum information222Often
referred to as _quantum communication_.[403]. These quantum networks (also
called a quantum internet) can enable applications fundamentally impossible
for purely classical networks and systems, such as quantum money, quantum
multi-party computations, and delegated quantum computing. For a better
overview of these functionalities and developed protocols, we refer the reader
to the _quantum protocol zoo_ [399], an open repository for quantum protocols.

In quantum cryptanalysis333In cryptography, the term ‘cryptanalysis’ is
commonly used for referring to the study of attacks on cryptosystems and often
at a practical or implementation level. However, in this thesis, we use this
term in a slightly different sense to address both cases of breaking
cryptosystems and designing secure ones, or more generally for _analysing_ the
cryptographic properties of a system, which is the other main topic of this
thesis, we walk a thin line between these two sides, trying to win the
everlasting battle between making and breaking cryptosystems in a world
(probably not too far away in the future) where both sides can make the most
of quantum mechanical systems and computers. As such, quantum cryptanalysis
encompasses many subfields of quantum sciences from quantum computing and
quantum information to the foundations of quantum mechanics, to better
manipulate them for designing secure systems. Furthermore, it has even merged
with relatively younger fields, such as quantum machine learning and quantum
learning theory, since they provide a new ground for cryptanalysis. Also,
given that quantum technology is usually more expensive and resource-intensive
than the usual classical computers and existing systems, another balance to
maintain in quantum cryptanalysis is between the security guarantees and the
required quantum resources. Maintaining this balance, although challenging, is
what makes the design of such quantum systems and protocols thought-provoking
and theoretically satisfying.

As mentioned above, a key factor for building efficient and secure quantum
cryptosystems in the presence of a quantum attacker is to deeply understand
the fundamental and non-classical aspects of quantum systems in general. In
this spirit, we can ask: _What are the key elements of quantum security?_ or
in other words, _What is it that leads to the security (of primitives or
protocols) in the regime of quantum mechanics?_ Depending on the required
functionality or protocol, different quantum features have been used, such as
entanglement and non-locality, the probabilistic nature of measurements, the
indistinguishability of quantum states and conjugate coding, and most of all,
_unclonability_.

The unclonability of the quantum state is one of the most exploited and most
common non-classical features in any cryptographic functionality that uses
quantum systems. This fundamental limitation of quantum mechanics that forbids
creating perfect copies of unknown quantum systems is one of the most central
properties of quantum mechanics. Maybe that is why it is inherent in almost
all quantum protocols and functionalities, even if not consciously employed.
It is perhaps safe to say that unclonability is a _resource_ for achieving
quantum security. However, many questions still remain regarding
unclonability, such as _Is the no-cloning of quantum states the only existing
form of unclonability?_ If not, _what are the other notions of unclonability?_
and _how can we relate them to cryptographic properties?_ Or maybe we can ask
more fundamental questions such as _Is there any deeper level to the concept
of unclonability?_ These are some of the questions that we try to tackle in
this thesis as we continue to uncover the relationship between the broader
notion of unclonability and quantum cryptanalysis. Finally, we aim to use the
tools and concepts that we develop and gather along the way for practical
applications.

###  1.1 Thesis overview

We give a brief summary of our contributions and the structure of the thesis.
We exclude Chapter 2, which includes the preliminaries and background
materials for the various tools we used in this thesis.

  * •

Chapter 3: We start from the foundations while focusing on three primary
notions: unclonability, unforgeability and learnability. We first lay an
argument about the relationship between unclonability and unknownness, a
concept that we formally define for unitary transformations, and then we bring
unclonability into a greater regime which encompasses both cryptography and
learning theory. This chapter serves as a roadmap for the rest of the thesis,
where we focus on different aspects of each of the concepts we will discuss.
Moreover, we introduce two main contributions which we will widely employ in
the rest of the thesis. The first one is a new class of quantum attacks based
on the concept of _emulation_ , and the next one is a new unified framework
for quantum unforgeability. Within this framework, we enclose the notion of
unforgeability for both quantum and classical primitives, and we also provide
a hierarchy of definitions. Finally, as a case study of our framework, several
impossibility results are given, and some quantum-secure constructions have
been introduced. The content of this chapter is the combination of two papers,
Quantum physical unclonable functions: possibilities and impossibilities.
Quantum 5 (2021)[8] and A Unified Framework For Quantum Unforgeability.” arXiv
preprint arXiv:2103.13994 (2021)[140], and some unpublished results which were
excluded from the mentioned papers.

  * •

Chapter 4: This chapter focuses on defining the notion of _quantum Physical
Unclonable Functions (qPUF)_ and studying its cryptographic properties using
the unforgeability framework that has been introduced in the previous chapter.
PUFs are a concept borrowed from the hardware security literature. However, as
we will see in this chapter, defining a quantum counterpart is not a
straightforward translation to the quantum regime but a rather more
fundamental generalisation of the notion of physical unclonability. Here, we
answer one of the questions we have asked before, _i.e._ we confirm the
existence of other forms of unclonability, not unrelated to the unclonability
of quantum states in quantum mechanics, while this relationship is more lucid
in the context of quantum PUF compared to classical ones. We focus on the
unitary subclass of quantum PUFs, and we prove general no-go results about the
unforgeability property of any such primitives. Finally, we formally prove
that a large class of them can satisfy a level of quantum unforgeability
powerful enough to make them strong and useful hardware tokens for
cryptography. This chapter is based on the paper Quantum physical unclonable
functions: Possibilities and impossibilities. Quantum 5 (2021)[8] as a part of
a collaboration with _Mahshid Delavar_ , _Myrto Arapinis_ and _Elham Kashefi_.

  * •

Chapter 5: This chapter is concerned with quantum pseudorandomness and its
relationship with physical unclonability and, more generally, quantum hardware
assumptions. Pseudorandomness is also one of the most rudimentary building
blocks of modern cryptography as it provides the randomness required for
cryptographic schemes in an efficient manner. In the quantum world, quantum
pseudorandomness has been recently introduced by [232] via the notions of
pseudorandom quantum states and pseudorandom unitaries. The pseudorandom
quantum objects provide an efficient and computational form of perfect uniform
randomness over the Hilbert spaces known as Haar-randomness. In this chapter,
we first study the connection between pseudorandom quantum states and
unforgeability. We prove that using quantum pseudorandomness will allow the
same level of security guarantee for unforgeability while improving
efficiency. Then we delve into the relationship between quantum physical
unclonability and pseudorandom unitaries, and we show that they are closely
connected to the point that they can be derived from each other in terms of
functionality. We also show that, interestingly, considering some assumptions
over the family of qPUFs, even without assuming the full extent of quantum
physical unclonability, will lead to quantum pseudorandom objects. This
chapter is the result of a collaboration between _Kaushik Chakraborty_ ,
_Niraj Kumar_ and _Elham Kashefi_ , published in On the connection between
quantum pseudorandomness and quantum hardware assumptions. Quantum Science and
Technology 7.3 (2022)[160].

  * •

Chapter 6: This chapter which includes three main results from three projects
is dedicated to applications of quantum physical unclonability and quantum-
enhanced physical unclonable functions. In the first part of the chapter, we
introduce two new identification protocols based on qPUFs as we have defined
and studied in earlier chapters. Our protocols include client-server
scenarios: that is, in the first one, a quantum server intends to identify a
low-resource client who only owns a qPUF device, and in the second protocol,
the client identifies a quantum server with a qPUF device, while we manage to
delegate the quantum verification to the server as well such that the client
only needs to run a classical verification test. Amid the security proof of
these two protocols lies one of our leading arguments earlier concerning
unclonability, since we will see how quantum physical unclonability serves as
a resource for these protocols to achieve exponential security in only a
polynomial number of rounds of quantum communication. We also thoroughly
discuss the role of differed quantum testing algorithms as our verification
subroutines and compare them, which can be of interest even outside the scope
of the presented protocols and more generally for other quantum communication
protocols. Furthermore, to provide sufficient theoretical ground and benchmark
for the experimental realisation of these protocols in the future, we give a
resource analysis in terms of quantum memory, quantum communication and
quantum computation resources. In the second part of the chapter, we will show
that the results we have demonstrated in Chapter 5 bring on efficiency and
practicality to our qPUF-based protocols. Finally, in the last part of this
chapter, we introduce a new quantum-enhanced PUF construction that combines
classical physical unclonability with quantum communication and combines the
best of both worlds. This construction, although weaker than a full quantum
PUF, allows for an efficient identification protocol that is implementable
with today’s technology, for instance, the existing QKD infrastructure, while
it achieves a high level of security against quantum adversaries. This
application also shows a particular _provable_ advantage of quantum
communication vs classical ones, as we will discuss through different
properties that the protocol achieves. To prove the security of our
construction and protocol, we use many tools and previous results from quantum
information theory, including entropic uncertainty relations. The first part
of the chapter is based on the work done in collaboration with _Niraj Kumar_ ,
_Mahshid Delavar_ and _Elham Kashefi_ , which resulted in this publication
Client-server identification protocols with quantum puf.” ACM Transactions on
Quantum Computing 2.3 (2021)[158]. The second part is from a small section of
the paper mentioned before [160], while it was more appropriate to be included
in this chapter. Lastly, the third part of this chapter is from a
collaboration with _Kaushik Chakraborty_ , _Yao Ma_ , _Myrto Arapinis_ , and
_Elham Kashefi_ , resulted in the paper Quantum Lock: A Provable Quantum
Communication Advantage. arXiv preprint arXiv:2110.09469 (2021)[110]. We note
that this last paper is included partially for more coherence and brevity of
the chapter.

  * •

Chapter 7: Finally, we turn to another aspect of the relation between quantum
unclonability and quantum cryptanalysis, this time from a machine learning
perspective. This chapter introduces a new cryptanalysis toolkit and method
based on approximate quantum cloning and variational algorithms. We introduce
our machine learning algorithm, $\operatorname{\textsf{VarQlone}}$, that can
efficiently learn to (approximately) clone quantum states of a specified
family optimally and in a hardware-friendly manner. This algorithm can have
several applications in the context of quantum foundation and quantum
computing, specifically since it can be run on NISQ devices, as we have done
so. However, in this thesis, we are particularly interested in its application
for cryptanalysis. For this purpose, we take two classes of quantum protocols,
QKD and quantum coin-flipping, for case studies, and we relate their security
to cloning-based attacks based on $\operatorname{\textsf{VarQlone}}$. We argue
that cryptanalysis in this new fashion, even for protocols that have been
information-theoretically proven secure like QKD, is beneficial since it
allows for benchmarking the state of the art of the current technology with
the state of the art of sophisticated attacks that are also implementable on
current hardware. Besides the relevance in the application, this chapter
allows us to come back to the foundations. In the course of this chapter, we
connect the security of certain classes of quantum protocols to specific
classes of approximate cloning. This type of cloning-based cryptanalysis
brings us one step closer to understanding the role of unclonability as a
source of security in quantum cryptography. We even offer several theoretical
guarantees and results on the specifications of this algorithm that could be
of interest to the quantum machine learning community. The content of this
chapter is from a collaboration with _Brian Coyle_ , _Niraj Kumar_ and _Elham
Kashefi_ and was published in Progress toward practical quantum cryptanalysis
by variational quantum cloning.” Physical Review A 105.4 (2022)[108]. Again,
since the context of the research done in this paper is wider than the focus
and interest of this thesis, we have only included the most relevant parts and
main contributions of the current author.

##  Chapter 2 Preliminaries

Man, he took his time in the sun
Had a dream to understand
A single grain of sand
He gave birth to poetry
But one day’ll cease to be
Greet the last light of the library

– Nightwish, The Greatest Show on Earth

We start with a general remark regarding this chapter. This chapter attempts
to cover all the necessary backgrounds, topics, concepts and tools used in
this thesis. Some sections mainly provide general knowledge on the subject,
and others, briefly introduce, sometimes in more detail, the definitions or
tools used later on in the thesis. Throughout this preliminary chapter,
whenever a specific notion or tool is introduced, we navigate the reader to
the part of the thesis it is employed. However, for a reader with familiarity
with the general topics covered here, we suggest skipping this chapter and
returning to each subsection when referred to subsequently in the following
chapters.

###  2.1 Quantum information and quantum computing

Let us begin the chapter by giving some background on quantum information and
quantum computing. We assume some familiarity with quantum mechanics and
although it will not be necessary for understanding the content of this
thesis, it is encouraged for enjoying it. We also assume familiarity with
linear algebra.

####  2.1.1 Quantum states and Hilbert space

The concept of _quantum states_ and where they live, which is called _state
space_ comes from the first postulate of quantum mechanics. According to this
postulate, any isolated physical system can be described (or be associated
with) a _vector_ , in a complex vector space with an inner product, known as
_Hilbert space_. This vector, that completely describes the physical system,
or sometimes the physical quantum mechanical property of a physical system, is
called the _state_ of the system and is a normalised unit vector in the
Hilbert space [316]111There is an alternative version of the first postulate
of quantum mechanics that has an additional statement that the other way is
also assumed, meaning that giving a Hilbert space, where a physical system is
described in it, any vector of the Hilbert space is also a potential state of
a physical system. Sometimes this is inherent in the evolution postulate,
however, it is interesting to think about it as the first postulate as well..
We denote a Hilbert space of dimension $d$ by $\mathcal{H}$ or sometimes
$\mathcal{H}^{d}$. Any $d$-dimensional Hilbert space is equipped with a set of
$d$ orthonormal vectors called a basis. The most important quantum systems in
quantum information are 2-level quantum systems or quantum states living in a
2-dimensional Hilbert space. We call this special state a _qubit_. The
following set of vectors is a complete basis for a qubit, referred to as the
computational bases:

$\ket{0}=\begin{bmatrix}1\\\
0\end{bmatrix}\quad\quad\ket{1}=\begin{bmatrix}0\\\ 1\end{bmatrix}$ (2.1)

Here $\ket{.}$ (called ‘ket’) or $\bra{.}$ (called ‘bra’) are known as _Dirac
notation_ and are the most common notation in quantum. Moreover, for any
Hilbert space $\mathcal{H}$ we can define a dual space denoted by
$\mathcal{H}^{*}$, where for any $\ket{\psi}\in\mathcal{H}$, there exists a
dual $\bra{\psi}\in\mathcal{H}^{*}$, that is its complex conjugate, such that
$\bra{\psi}\psi\rangle=1$. Also the inner product between two vectors
$\ket{\psi},\ket{\phi}\in\mathcal{H}$ is shown in the Dirac notation as
$\bra{\phi}\psi\rangle$.

Any qubit state can be written as a linear combination of the basis for
instance: $\ket{\psi}=\alpha\ket{0}+\beta\ket{1}$ where
$|\alpha|^{2}+|\beta|^{2}=1$ for any $\alpha,\beta\in\mathbb{C}$, since the
state should be normalised. This linear combination of other quantum states
(for instance any basis state) is called a _superposition_ of those quantum
states. According to quantum mechanics, any normalised superposition of the
states is also a valid member of the Hilbert space, due to linearity and hence
is another valid quantum state. The coefficients $\alpha$ and $\beta$ are also
called _amplitudes_ and are complex numbers. One of the most useful
superpositions, in the equal-weight superposition of the computational basis
like the following:

$\ket{+}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1}),\quad\quad\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$
(2.2)

one can see that the state $\ket{+}/\ket{-}$ are also orthonormal and hence
form another basis for qubit Hilbert space. This basis is called _plus-minus
basis_ or _X-basis_ (we will see why in 2.1.6). The generalisation of such
uniform superposition basis states in higher dimension is also known as
_Fourier basis_.

####  2.1.2 Mixed states and density matrices

Now, let us give a more general and complementary formalism for describing
qubits and quantum states. When we describe a quantum system by a vector in
the Hilbert space, we _deterministically_ describe its state (however, as we
will see, the process of revealing the state is itself probabilistic), in this
case, we call it a _pure_ quantum state. Nevertheless, not all the systems in
nature are like that. Some systems, are in fact, a probability distribution
over different pure quantum states. We call these states _mixed states_ , and
we can represent them as follows:

$\rho:=\sum_{s}p_{s}\ket{\psi_{s}}\bra{\psi_{s}}$ (2.3)

where $\ket{\psi_{s}}\bra{\psi_{s}}$ is the outer product of the two vectors.
The above representation means that we prepare a pure state $\ket{\psi_{s}}$
with probability $p_{s}$. Also, one can see that $\rho$ is no longer a vector,
but a matrix. This kind of matrices, called _density matrices_ [173] are a
more general way of describing all quantum systems, including the pure one,
since if we have only one probability $p=1$, then $\rho=\ket{\psi}\bra{\psi}$,
which is a pure state and the density matrix equivalent of $\ket{\psi}$.

In operator language, a density operator for a system is a positive semi-
definite, Hermitian operator of trace one ($\mathsf{Tr}(\rho)=1$) acting on
the Hilbert space of the system. We denote the set of all the density matrices
associated with the Hilbert space $\mathcal{H}$, as
$\mathcal{S}(\mathcal{H})$. Geometrically, this is a convex set. Also a pure
state always satisfy $\mathsf{Tr}(\rho^{2})=1$, while as for a mixed state
$\mathsf{Tr}(\rho^{2})<1$. This is a good criterion for checking the purity of
a density matrix.

##### Bloch sphere

For the 2-dimensional space of qubits, there is a simple and pleasant
geometrical representation for all the possible pure and mixed states. It is
described as a unit sphere, called _Bloch sphere_ , as shown in Fig. 2.1.

Figure 2.1: The Bloch sphere (figure from: [408])

The surface of the Bloch sphere represents the pure state of a qubit and all
the points inside of the sphere represent the set of the mixed states. A pure
qubit state can be described in terms of the angles associated with its Bloch
vector, as can be seen in the figure. For $0\leqslant\theta\leqslant\pi$ and
$0\leqslant\phi<2\pi$, the state of a qubit $\ket{\psi}$ is described as:

$\ket{\psi}=\cos{\frac{\theta}{2}}\ket{0}+e^{i\phi}\sin{\frac{\theta}{2}}\ket{1}$
(2.4)

A general qubit density matrix, can be written as [78]:

$\rho=\frac{1}{2}(\mathbb{I}+x_{1}X+x_{2}Y+x_{3}Z)$ (2.5)

where $\mathbb{I}$ is the identity matrix and X, Y and Z are the following
matrices known as _Pauli matrices_ :

$X=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix},\quad Y=\begin{pmatrix}0&-i\\\
i&0\end{pmatrix},\quad Z=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}$ (2.6)

Thus, states of single qubits are characterized by a vector
$(x1,x2,x3)\in\mathbb{R}^{3}$ taken from the unit ball, which is the Bloch
sphere.

##### Composition of quantum systems and entanglement

The very original formulation of quantum mechanics talks about a single
quantum system described by a vector in Hilbert space. However, if we want to
describe the joint state of two quantum systems $\mathcal{H}_{1}$ and
$\mathcal{H}_{2}$, we need to deal with their composition. The most common
framework for the composition of quantum states is tensor product composition.
In other words, the composite system $\ket{\psi_{1,2}}$ is described as a unit
vector in the tensor product of the Hilbert spaces
$\mathcal{H}_{1}\otimes\mathcal{H}_{2}$.222This is usually considered as an
(extended) axioms of the quantum mechanics, however, it is also possible not
to assume it, and to derive it instead from general composition rules and
physical evidence [7].

If a quantum state can be written as the tensor product of all its subsystems,
we say that the state is _separable_ , for example:
$\ket{\psi_{AB}}=\ket{\psi_{A}}\otimes\ket{\psi_{B}}$. Nevertheless, not all
the states in $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ can be written as such.
The states that cannot be described in this tensor product form are called
_entangled_ states, and physically, they contain some non-classical
correlation known as _entanglement_. The following defines the general
definition of separable and entangled states for bipartite mixed states:

######  Definition 1 (Separable and entangled mixed states [78]).

A mixed state $\rho_{AB}$ is separable if and only if it can be represented as
a convex combination of the product of projectors on local states in the form
of the following equation. Otherwise, the mixed state is said to be entangled.
$\rho_{AB}=\sum^{K}_{i=1}p_{i}\ket{e_{i}}\bra{e_{i}}\otimes\ket{f_{i}}\bra{f_{i}}$
(2.7) where $\ket{e_{i}}$ and $\ket{f_{i}}$ are a basis for subsystem $A$ and
$B$ respectively.

We also note that the states in Eq. (2.7) describe the most general state of a
class of states called LOCC, meaning the most general states that two parties,
Alice and Bob can prepare using only _local operation_ and _classical
communication_.

Another advantage of the density matrix formalism is that it allows us to
describe the quantum states of the subsystems of a joint quantum system, even
if the state is not separable [316]. For this we can take the partial trace of
the other subsystem, to obtain the subsystems of interest, for instance:

$\rho_{A}=\mathsf{Tr}_{B}(\rho_{AB}),\quad\text{and},\quad\rho_{B}=\mathsf{Tr}_{A}(\rho_{AB})$
(2.8)

where $\mathsf{Tr}_{B}$ meaning taking the trace over subsystem $B$, using the
basis of this subspace. $\rho_{A}$ and $\rho_{B}$ are called a _reduced
density matrix_ of the system.

Now, let us introduce the most important entangled bipartite states in quantum
information, also known as _Bell states_ , which are as follows:

$\begin{split}&\ket{\Phi^{\pm}}:=\frac{1}{\sqrt{2}}(\ket{00}\pm\ket{11})\\\
&\ket{\Psi^{\pm}}:=\frac{1}{\sqrt{2}}(\ket{01}\pm\ket{10})\end{split}$ (2.9)

where $\ket{00}=\ket{0}_{A}\otimes\ket{0}_{B}$ (and similarly for the rest of
the basis). These states contain the maximum amount of entanglement between
all the pure bipartite states. Furthermore, they have an interesting property
that their reduced density matrices are the state $\frac{\mathbb{I}}{2}$,
which is a state known as _maximally mixed_ state.333In general maximally
mixed state for Hilbert space of dimension $d$ is given as
$\frac{\mathbb{I}_{d}}{d}$. For instance, we have:

$\rho_{A}=\rho_{B}=\mathsf{Tr}_{A}(\ket{\Phi^{+}}\bra{\Phi^{+}}_{AB})=\frac{\mathbb{I}}{2}$
(2.10)

Looking at the reduced density matrix of joint quantum systems can in general
give information about the amount of entanglement contained in these systems.

####  2.1.3 Quantum operations and measurements

So far we gave a brief introduction to quantum systems and some of their
properties. Now it is time to talk about how quantum systems evolve and
transform into other quantum systems.

The first form of quantum operation that we know, according to postulates of
quantum mechanics, are unitary operators. A unitary matrix $U$, can transform
a pure and mixed quantum state as follows:

$\ket{\psi^{\prime}}=U\ket{\psi}\quad\text{and},\quad\rho^{\prime}=U\rho
U^{\dagger}$ (2.11)

Recalling the Bloch sphere, the unitary operation of any pure qubit state is
equivalent to a rotation of the vector on the surface of the Bloch sphere (up
to a phase factor). However, unitary matrices are not the most general form of
quantum operations. General quantum transformations are _Completely Positive
Trace Preserving (CPTP or CPT)_ maps which include also unitary matrices.
These operations are also called a _quantum channel_ and can map a general
density matrix $\rho\in\mathcal{H}$ to another density matrix
$\rho^{\prime}\in\mathcal{H}^{\prime}$ (where $\mathcal{H}^{\prime}$ is often
the same as $\mathcal{H}$, but not necessarily), as follows:

$\mathcal{E}:\mathcal{S}(\mathcal{H})\rightarrow\mathcal{S}(\mathcal{H}^{\prime}),\quad\quad\rho^{\prime}=\mathcal{E}(\rho)$
(2.12)

Quantum channels can take the following general from:

$\mathcal{E}(\rho)=\sum_{k}E_{k}\rho E^{\dagger}_{k}$ (2.13)

where $E_{k}$ are operators that should satisfy the following criterion for
the overall operation $\mathcal{E}$ to be trace-preserving:

$\sum_{k}E^{\dagger}_{k}E_{k}=\mathbb{I}$ (2.14)

This representation of quantum channels is called _operator-sum_ formalism
[316] and the decomposition of a quantum channel into such operators is also
sometimes called _Kraus decomposition_. There also exists an alternative way
of representing quantum channels from the point of view of system-environment
interaction. This point of view is very interesting since it shows that all
the operations can eventually be described via a unitary operation on a larger
or expanded Hilbert space which also includes the environment. Let the quantum
state $\rho$ be entangled with a system $\ket{E}$ that describes the
environment. If a unitary operation is applied to the joint state of the
system-environment, the operation that is applied to the system alone can be
described as follows:

$\rho^{\prime}=\mathcal{E}(\rho)=\mathsf{Tr}_{E}[U(\rho\otimes\ket{E}\bra{E})U^{\dagger}]$
(2.15)

This operation is no longer a unitary but a CPTP map. We should also note that
this later interpretation gives us a good intuition and toolkit to study the
effect of noise on the quantum system in the same way as we describe any other
transformations of them. A quantum _noise_ is also described as a CPTP map and
be studied with the same mathematical toolkits theoretically. Commonly we
define specific classes of quantum channels that model the most common errors
and noisy behaviour that happens to the actual devices. The most famous ones
are _bit-flip noise channel_ , _phase-flip noise channel_ , _Pauli noise
channel_ , _depolarising noise channel_ , _dephasing noise channel_ , and
_amplitude-damping noise channel_ [78, 316].

##### Measurements

We now introduce one of the most central types of operations in quantum
mechanics _i.e._ measurements. Measurement operators offer a mathematical
formalism for studying the process of observation and extracting the real
values for the physical properties of a quantum system. These values are in
some sense _the classical information_ of the system given by expectation
values of a Hermitian observable. Quantum measurements are described as a set
of linear operators $\\{M_{m}\\}$ acting on the state where the index $m$
refers to each measurement outcome. If $\ket{\psi}$ is the pure quantum state
before the measurement, then the probability of obtaining result $m$, and the
state of the system after the measurement is given as follows [316]:

$\begin{split}&p(m)=Pr[\text{obtaining result
}m]=\bra{\psi}M_{m}^{\dagger}M_{m}\ket{\psi}\\\
&\ket{\psi_{m}}=\frac{M_{m}\ket{\psi}}{\sqrt{\bra{\psi}M_{m}^{\dagger}M_{m}\ket{\psi}}}\end{split}$
(2.16)

Thus quantum measurements are probabilistic in nature, and since the
probability should be preserved over the full set of measurement, they also
satisfy the following completeness equation:

$\sum_{m}\bra{\psi}M_{m}^{\dagger}M_{m}\ket{\psi}=\sum_{m}p(m)=1$ (2.17)

This probability rule for quantum systems, also known as _Born’s rule_ , for a
general mixed system is given as follows:

$p(m)=Pr[\text{obtaining result }m]=\mathsf{Tr}[M_{m}\rho M_{m}^{\dagger}]$
(2.18)

The first type of measurement, and a very useful one, are _projective
measurements_ , which are given by a set of projective operators. A simple
example is a set $\\{M_{0},M_{1}\\}$ where $M_{0}=\ket{0}\bra{0}$ and
$M_{1}=\ket{1}\bra{1}$. This is a qubit measurement which projects everything
in the $Z$ basis of the Bloch sphere, and it is also famously known as
_measurement in the computational basis_.444The computational basis
measurement can be easily generalised to any dimension by only making the
projective operator from the computational basis of that Hilbert space.

The most general class of measurement in the quantum world is given by a
mathematical formalism known as _Positive Operator-Valued Measure (POVM)_. A
POVM is described as a set of positive operators $\\{E_{m}\\}$ satisfying the
relation $\sum_{m}E_{m}=\mathbb{I}$, and they obey the same Born’s rule as we
described earlier. This class also includes the projective measurements,
however, one difference between the projective measurements and a POVM non-
projective one is that the cardinality of the set of POVM measurements over a
Hilbert space can be larger than the dimension as opposed to the projective
ones. For instance, for qubits, we have seen that the full set of
computational basis measurements, includes 2 projectors (which is the same for
measuring on any arbitrary basis), but one can define the following valid set
of POVM measurements on a qubit:

$\begin{split}&E_{1}=(2-\sqrt{2})\ket{1}\bra{1},\quad\quad
E_{2}=(2-\sqrt{2})\ket{-}\bra{-}\\\ &E_{3}=\mathbb{I}-E_{1}-E_{2}\end{split}$
(2.19)

The POVM can be interpreted physically in different ways. The first one is
when we are applying a projective measurement on the joint state of our system
within a larger system or correlated with another system. In this case,
although the measurement on the larger Hilbert space is projective, the
resulting measurement on the main systems that we are interested in is not,
and it’s instead a POVM. This scenario is similar to the case we have
discussed before regarding the CPTP maps and there is a good reason for this
resemblance due to the fact that POVMs are also CPTP maps and can be described
in that formalism. Another way of physically interpreting the POVM is when the
real measurement devices are not perfect and instead of performing a perfect
projection, they perform a combination of a projection and another quantum
operation. In that case, again the measurement can be mathematically described
as a POVM. This last point is very important in distinguishing quantum states
from each other as we will see in Section 2.2.

####  2.1.4 Distance measures

Distance measures are mathematical tools for comparing systems on different
aspects, for instance, their information quantity. In the classical world,
these comparisons are often straightforward. As an example, to compare
classical bit strings, we can simply check their equality. But one can also
define a better and more fine-grained distance for classical information, for
example, by counting the number of places where two bitstrings are different.
This distance is called _Hamming distance_ in classical information theory and
gives a good measure for quantifying classical information in many cases. But
how about quantum information. As we know by now, the quantum information
lives inside the state of a qubit, that is, a vector in a continuous vector
space. And more importantly, while revealing this information (measurement) we
are dealing with a probabilistic process. Hence comparing and quantifying the
distance between quantum information and generally quantum systems are more
tricky! Fortunately, the mathematical background of quantum mechanics and
quantum information is strong enough to handle this more complicated
situation, and a large variety of quantum distance measures have been defined
in the literature, each of which, is useful for different problems that we
face in this field [316, 78, 202, 300, 298, 52, 197]. Here we only introduce
the very few most relevant distance measures for this thesis.

But before, that let us start with a classical distance, which has been
incorporated in the quantum regime very similarly. This is the case when we
want to compare two probability distributions $\\{p(x)\\}$ and $\\{q(x)\\}$.
One very common and quite intuitive way of defining a notion of distance for
them is as follows:

$d(p(x),q(x)):=d_{\ell_{1}}(p(x),q(x))=\frac{1}{2}\sum_{x}|p(x)-q(x)|$ (2.20)

This distance is called _trace distance_ or _$\ell_{1}$ -norm_. And the first
quantum distance that we introduce is the generalisation of this distance. The
trace distance is defined as follows:

######  Definition 2 (Trace distance).

For any general quantum state $\rho$ and $\sigma$, their trace distance is
defined as:
$d_{\text{Tr}}(\rho,\sigma):=\frac{1}{2}\mathsf{Tr}|\rho-\sigma|=\frac{1}{2}\sum_{i}|\lambda^{\rho\sigma}_{i}|$
(2.21) where $|\rho-\sigma|:=\sqrt{(\rho-\sigma)^{\dagger}(\rho-\sigma)}$ is
defined as the positive square root of the matrix, and
$\lambda^{\rho\sigma}_{i}$ are eigenvalues of the Hermitian, but not
necessarily positive, matrix $(\rho-\sigma)$.

The second measure of distance that is widely used all over quantum
information, and this thesis included, is _fidelity_. Although fidelity is not
a _metric_ on the space of density matrices [316], it is one of the most
useful measures of the ‘closeness’ of two quantum states. One of the reasons
is that fidelity has an operational meaning: intuitively it expresses the
probability that one state will pass a test to identify as the other one. The
fidelity between two quantum states in the most general case is known as
_Uhlmann’s fidelity_ and is defined as follows:

######  Definition 3 (Fidelity).

For any general quantum state $\rho$ and $\sigma$, their Uhlmann’s fidelity is
defined as:
$F(\rho,\sigma):=\left(\mathsf{Tr}\left[\sqrt{\sqrt{\rho}\sigma\sqrt{\rho}}\right]\right)^{2}$
(2.22) which is equal to the squared overlap
$F(\ket{\psi_{\rho}},\ket{\psi_{\sigma}}):=|\bra{\psi_{\rho}}\psi_{\sigma}\rangle|^{2}$,
for two pure quantum states $\ket{\psi_{\rho}}$ and $\ket{\psi_{\sigma}}$.

The third quantum distance that we introduce, is closely related to the
fidelity. In fact, we first define a geometrical metric in the space of
quantum states, known as _Bures angle_ , as follows:

$\Theta_{\text{BA}}(\rho,\sigma):=\arccos{\sqrt{F(\rho,\sigma)}}$ (2.23)

The Bures angle is itself a distance but it is also associated with another
important metric in the quantum information, known as _Bures distance_ which
is also the quantum equivalent of _Fubini-Study_ metric [389].

######  Definition 4 (Fubini-Study/Bures distance).

For any general quantum state $\rho$ and $\sigma$, their Bures/Fubini-Study
distance is defined as follows:
$d_{\text{FS}}(\rho,\sigma):=\left(2(1-\sqrt{F(\rho,\sigma)})\right)^{\frac{1}{2}}=\sqrt{2(1-\cos{\Theta_{\text{BA}}})}$
(2.24)

There are several important and useful properties and features of these
distances which we need to cover for the purpose of this thesis. First, we
need to note that all these distances, including the trace distance and
fidelity, should be preserved under the unitary evolution of quantum states.
This is because unitaries, preserve the inner product and hence should also
preserve any notion of distance that we define over the space of density
matrices. Thus we have the following central relations [316]:

$\begin{split}d_{\text{Tr}}(U\rho U^{\dagger},U\sigma
U^{\dagger})&=d_{\text{Tr}}(\rho,\sigma)\\\ F(U\rho U^{\dagger},U\sigma
U^{\dagger})&=F(\rho,\sigma)\end{split}$ (2.25)

But how about the distance between quantum states, after a non-unitary general
quantum channel is applied to them? It can be shown that quantum channels are
_contractive_ , meaning that they decrease the distance between quantum
states. This is captured in the following theorem in terms of trace distance:

######  Theorem 1.

[Contractivity of quantum channels [316]] Suppose $\mathcal{E}$ is a CPTP map.
Let $\rho$ and $\sigma$ be any two density operators. We have:
$d_{\text{Tr}}(\mathcal{E}(\rho),\mathcal{E}(\sigma))\leqslant
d_{\text{Tr}}(\rho,\sigma)$ (2.26)

The same result can be reformulated in terms of fidelity leading to the fact
that $F(\mathcal{E}(\rho),\mathcal{E}(\sigma))\geqslant F(\rho,\sigma)$ under
any CPTP operation, which is usually referred to as _Monotonicity of the
fidelity_[316].

Another property of trace distance that will come in very handy in our proofs
is what is known as _strong convexity_ and is stated as follows:

######  Theorem 2.

[Strong convexity of the trace distance [316]] Let $\\{p_{i}\\}$ and
$\\{q_{i}\\}$ be two probability distributions over the same index set, and
$\rho_{i}$ and $\sigma_{i}$ be density matrices associated with the same index
set. Then the trace distance satisfies the following:
$d_{\text{Tr}}\left(\sum_{i}p_{i}\rho_{i},\sum_{i}q_{i}\sigma_{i}\right)\leqslant
d_{\ell_{1}}(p_{i},q_{i})+\sum_{i}d_{\text{Tr}}(\rho_{i},\sigma_{i})$ (2.27)
where $d_{\ell_{1}}(p_{i},q_{i})$ is the classical trace-distance between the
two probability distribution.

Similarly, we have _strong concavity_ for fidelity:

######  Theorem 3.

[Strong concavity of fidelity [316]] Let $\\{p_{i}\\}$ and $\\{q_{i}\\}$ be
two probability distributions over the same index set, and $\rho_{i}$ and
$\sigma_{i}$ be density matrices associated with the same index set. Then the
trace distance satisfies the following:
$F\left(\sum_{i}p_{i}\rho_{i},\sum_{i}q_{i}\sigma_{i}\right)\geqslant\sum_{i}\sqrt{p_{i}q_{i}}F(\rho_{i},\sigma_{i})$
(2.28)

which also results in the weaker version called _concavity_ of the fidelity:

$F(\sum_{i}p_{i}\rho_{i},\sigma)\geqslant\sum_{i}p_{i}F(\rho_{i},\sigma)$
(2.29)

Finally, it is important to be able to translate between fidelity and trace
distance. The relation between the two, is given via the following inequality:

$1-\sqrt{F(\rho,\sigma)}\leqslant
d_{\text{Tr}}(\rho,\sigma)\leqslant\sqrt{1-F(\rho,\sigma)}$ (2.30)

One can also define distances and norms on the operator space. These distances
are called _operator norms_. The first important example is the _operator
infinity norm_ or $\ell^{\infty}$-norm. In general, an operator norm
$\ell^{\infty}$ is defined on a Banach space555Banach space is a complete
normed vector space. That is, a Banach space is a vector space with a metric
that allows the computation of vector length and distance between vectors, and
is complete in the sense that a ‘Cauchy sequence’ of vectors always converges
to a well-defined limit that is within the space [2] or a bounded sequence of
elements or vectors of that space as follows:

$||x||_{\infty}=\sup_{n}|x_{n}|,$ (2.31)

The operator norm on the Hilbert space is defined over the space of bounded
linear operators as,

$||O||_{\infty}=\sup||Ox||:\forall||x||\leqslant 1,$ (2.32)

We also note that for the operator norms, $||.||_{1}$ is the dual norm of
$||.||_{\infty}$ [221].

The final distance measures that we introduce, which is particularly
beneficial distance in the quantum setting, is a distance called _diamond
norm_ , defined as follows:

######  Definition 5 (Diamond norm).

For any two CPTP map (quantum channel) $\Lambda_{1}$, $\Lambda_{2}$, their
diamond norm is defined as,
$\parallel\Lambda_{1}-\Lambda_{2}\parallel_{\diamond}:=\underset{\rho}{\max}(\parallel(\Lambda_{1}\otimes\mathbb{I})[\rho]-(\Lambda_{2}\otimes\mathbb{I})[\rho]\parallel_{1})$
(2.33) where $\parallel.\parallel_{1}$ is the _$\ell_{1}$ -norm_, and the
maximum has been taken over all the density matrices $\rho$.

Operationally diamond norm quantifies the maximum probability of
distinguishing operation $\Lambda_{1}$ from $\Lambda_{2}$ in a single-use, and
it is a sensible measure to quantify the difference between unitary operators
or other quantum channels.

####  2.1.5 Entropic uncertainty relations

In this section, we introduce a more advanced but very useful toolkit in
quantum information that is also related to cryptography. It consists of a
mathematical framework and several inequalities known as _conditional
entropies_ or _entropic uncertainty relations_ , which have been used in the
formal security proofs of several quantum protocols, specifically, the Quantum
Key Distribution (QKD) protocols [352, 391].666For this subsection we assume
some familiarity with the concept of QKD protocols since we refer to it
several times. However, the details of the protocol are not compulsory for
understanding the tools that we introduce here. We do not intend to give a
background on the QKD protocol(s) as it will make this preliminary even longer
than it is. We refer the readers to [316] for a general overview of the
protocol and to [391] for a comprehensive and advanced description and
security proofs. We have mostly exploited the content of this section in
Chapter 6, Section 6.4.5 and 6.4.6 and Chapter 7 Section 7.2.1.

But first, we need to introduce the notion of entropy in quantum and classical
information. In classical information theory, the entropy for a random
variable is defined as follows, and it is called _Shannon’s entropy_.

######  Definition 6 (Shannon’s entropy).

Let $X$ be a discrete random variable on a finite set
$\mathcal{X}=\\{x_{1},\dots,x_{n}\\}$, with probability distribution function
$p(x)=Pr(X=x)$. The entropy $H(X)$ of $X$ is defined as:
$h(X)=-\sum_{x\in\mathcal{X}}p(x)\log p(x)=\mathbb{E}[-\log p(X)]$ (2.34)
while we consider $0\log 0=0$ and logarithm is usually taken to the base $2$,
in which case the entropy is measured in bits.

Intuitively, this measure quantifies the amount of ‘information’ (or on the
other side ‘uncertainty’) in a system. As we mentioned, quantum states also
include a certain degree of classical information, which we can extract
through the probabilistic procedure of measurements. As a result, we can also
assign entropy to quantum states. The quantum version of Shannon’s entropy is
called _Von Neumann entropy_ 777In this thesis, we mostly use $H(.)$ to denote
the general notion of entropy which can in some cases refer to Shannon’s
entropy and in some others to Von Neumann entropy. However, if we specifically
want to emphasise Shannon’s entropy, we use the notation $h(.)$ which is
defined as follows:

######  Definition 7 (Von Neumann entropy).

For a quantum-mechanical system described by a density matrix $\rho$, the von
Neumann entropy is
$S(\rho)=-\mathsf{Tr}(\rho\log\rho)=-\sum_{i}\lambda_{i}\log_{2}(\lambda_{i})$
(2.35) where $\lambda_{i}$ are the eigenvalues of $\rho$, we consider $0\log
0=0$ and logarithm is taken to the base $2$ or $e$. Furthermore $S(\rho)$ is
zero if and only if $\rho$ represents a pure state.

We are now ready to talk about uncertainty in quantum mechanics, in terms of
entropy. Heisenberg’s uncertainty principle is one of the most important
fundamental properties of quantum mechanics which is mathematically speaking
due to the non-commuting property of observables, like Pauli $X$ and $Z$.
Reformulating these relations in terms of entropic quantities has been very
useful and the most well-known uncertainty relation for these operators was
given by Deutsch [142] and later improved [311]. The relation, for $X$ and $Z$
observables, is given as follows:

$H(X)+H(Z)\geqslant\log_{2}(\frac{1}{c})$ (2.36)

where $c$ denotes the maximum overlap between any two eigenvectors of $X$ and
$Z$. Since the entropy is defined with respect to a random variable, we need
to see what are our random variables here. First, we consider a quantum system
$A$ where the state is described with the density matrix $\rho_{A}$ on a
finite-dimensional Hilbert space. We then assume a measurement is performed on
a $X$ and $Z$ basis as projective operators that project the state into the
subspace spanned by those bases. Thus the random variables are defined via
measurements of the observers $X$ and $Y$. In the most general case, the
measurements are a set of POVM operators on system $A$ denoted as
$\\{M^{x}\\}_{x}$ and $\\{N^{z}\\}_{z}$ satisfying the Born rule for obtaining
outcomes $x$ and $z$ to be as follows:

$P_{X}(x)=\mathsf{Tr}[\rho_{A}M^{x}]\quad,\quad
P_{Z}(z)=\mathsf{Tr}[\rho_{A}N^{z}]$ (2.37)

In this case, the Eq. (2.36) still gives the generalised uncertainty relation
with the difference that the $c$ is defined as follows:

$c=\max_{x,z}c_{zx},\quad\text{and}\quad
c_{xz}=\parallel\sqrt{M^{x}}\sqrt{N^{z}}\parallel^{2}$ (2.38)

where $\parallel.\parallel$ denotes the operator norm (or infinity norm)
defined in Section 2.1.4. The above uncertainty relation can be extended to
conditional entropy as well in the context of _guessing games_ as has been
defined in [102]. Assume two parties, Alice and Bob, where Bob prepares a
state $\rho_{A}$ and Alice randomly performs the $X$ and $Z$ measurements
leading to a bit $K$. Then Bob wants to guess $K$ given the basis choice
$R=\\{0,1\\}$. The conditional Shannon entropy is defined as follows:

$H(K|R):=H(KR)-H(R)$ (2.39)

Thus one can get the same uncertainty relation with the conditional entropy
as:

$H(K|R=0)+H(K|R=1)\geqslant\log_{2}(\frac{1}{c})$ (2.40)

Similar, to the classical case, for a bipartite system $\rho_{AB}$ the
conditional Von Neumann entropy is defined as follows:

$H(A|B):=H(\rho_{AB})-H(\rho_{B})$ (2.41)

Furthermore, this can be generalised to any tripartite quantum system with
state $\rho_{ABC}$. An interesting property here is an inequality referred to
as _data processing inequality_ [102] which states that the uncertainty of $A$
conditioned on some system $B$ never goes down if $B$ performs a quantum
channel on the system. In other words for any tripartite system $\rho_{ABC}$
where system $C$ will perform a quantum operation on the quantum state to
extract some information, we have the following:

$H(A|BC)\leqslant H(A|B)$ (2.42)

Given the above inequality leads to the general uncertainty relations between
any tripartite system. One of the most common scenarios is when we have two
honest parties, Alice and Bob, and an _eavesdropper_ or _adversary_ called
Eve, for example in the QKD protocol. In this case, the following entropic
inequality holds:

$H(K|ER)+H(K|BR)\geqslant\log_{2}(\frac{1}{c})$ (2.43)

Where $K$ is the measurement output and $R$ is the basis bit. This imposes a
fundamental bound on the uncertainty in terms of von Neumann entropy, in other
words, the amount of information that an eavesdropper can extract from the
joint quantum systems shared between the three parties, is fundamentally
bounded by quantum mechanics. These inequalities can also be extended to the
case where $n$ bits are encoded in $n$ quantum states where $R^{n}$ and
$K^{n}$ are bit-strings denoting the basis random choices for the qubits and
measurement outputs respectively, and $B^{n}$ denotes Bob’s bit-string. Also,
$E$ denotes Eve’s system which is a general quantum system operating on
$n$-qubit messages and any arbitrary local system. We have the following
inequality:888This is the main result we will use in Section 6.4.5 and Section
6.4.6 for our security proof.

$H(K^{n}|ER^{n})+H(K^{n}|B^{n}R^{n})\geqslant n\log_{2}(\frac{1}{c})$ (2.44)

The amount of information shared between joint quantum systems can also be
defined in terms of other informatic quantities such as _mutual information_
or _accessible information_. Again, let us discuss these quantities in a two
party scenario. Consider a scenario where Alice prepares a pure quantum state
drawn from the ensemble $\\{p_{y},|\psi_{y}\rangle\\}$ with the density matrix
$\rho_{AB}$, where

$\rho_{AB}=\sum_{y}p_{y}|y\rangle_{A}\langle
y|\otimes|\psi_{y}\rangle_{B}\langle\psi_{y}|.$ (2.45)

Bob knows the ensemble i.e., the mixed state $\rho_{AB}$, but not the
particular state that Alice chose. He wants to acquire as much information as
possible about $y$. Bob collects his information by performing a generalized
measurement, the POVM ${M_{\tilde{y}}}$. Bob’s state is of the form
$\rho_{B}=\mathsf{Tr}_{A}(\rho_{AB})$ as it is the subsystem of the larger
density matrix. If Alice’s preparation choice was $y$, Bob will obtain the
measurement outcome $\tilde{y}$ with conditional probability
$p(\tilde{y}|y)=\bra{\psi_{y}}M_{\tilde{y}}\ket{\psi_{y}}$. For this kind of
classical-quantum state $\rho_{AB}$, the amount of information Bob can extract
from this measurement is given by a quantity called _mutual information (MI)_
$I(Y;\tilde{Y})_{\rho}$ between $Y,\tilde{Y}$ which is defined as follows.

$I(Y:\tilde{Y}):=h(Y)-h(\tilde{Y}|Y),$ (2.46)

Nonetheless, all the entropic quantities that we have discussed so far, work
well in the asymptotic limit, while other similar quantities are more suited
to capture the finite-size systems. _Min- and max-entropy_ are the notion
first proposed by Renner [352] as the natural generalizations of what was
known as _conditional Rényi entropies_ [364] to the quantum setting. The
definition is as follows:

######  Definition 8 (Min- and max- entropy [257]).

Let $\rho=\rho_{AB}$ be a bipartite density operator. The min-entropy of $A$
conditioned on $B$ is defined by: $H_{\text{min}}(A|B)_{\rho}:=-\inf
D_{\infty}(\rho_{AB}\parallel\mathbb{I}_{A}\otimes\sigma_{B})$ (2.47) where
the infimum ranges over all normalized density operators $\sigma_{B}$ on
subsystem $B$ and $D_{\infty}(.\parallel.)$ is defined as follows:
$D_{\infty}(\tau\parallel\tau^{\prime}):=\inf\\{\lambda\in\mathbb{R}:\tau\leqslant
2^{\lambda}\tau^{\prime}\\}$ (2.48) and the max-entropy is defined as:
$H_{\text{max}}(A|B)_{\rho}:=-H_{\text{min}}(A|C)_{\rho}$ (2.49) where the
min-entropy is evaluated for a purification $\rho_{ABC}$ of $\rho_{AB}$.

The above entropies can be then parameterised by a parameter
$\varepsilon\geqslant 0$ called the _smoothness_ parameter. The smooth version
of the min and max entropies can be defined as follows:

######  Definition 9 ($\varepsilon$-smooth min/max entropy [257]).

Let $\rho=\rho_{AB}$ be a bipartite density operator and let
$\varepsilon\geqslant$ be a parameter. The $\varepsilon$-smooth min/max
entropy of $A$ conditioned on $B$ are defined by:
$\begin{split}H^{\varepsilon}_{\text{min}}(A|B)_{\rho}&:=\underset{\rho^{\prime}}{\sup}H_{\text{min}}(A|B)_{\rho^{\prime}},\\\
H^{\varepsilon}_{\text{max}}(A|B)_{\rho}&:=\underset{\rho^{\prime}}{\inf}H_{\text{max}}(A|B)_{\rho^{\prime}}\end{split}$
(2.50) where the supremum ranges over all density operators
$\rho^{\prime}=\rho^{\prime}_{AB}$ which are $\varepsilon$-close to
$\rho$.999The $\varepsilon$-closeness can be defined with respect to both
trace distance and fidelity. However usually defining them in terms of
fidelity is more suitable since it is invariant under purification.

The final relevant tool of information theory that we need to introduce in
this section is called quantum _Asymptotic Equipartition Property (AEP)_
defined in [352]. This is the quantum equivalent of classical (AEP) that
roughly speaking, talks about the probability of typical sets occurring in a
random or stochastic process when having a series of many random variables.
Here we need a special case of quantum AEP for a $n$-fold quantum-classical
system, which we represent as the following theorem.

######  Theorem 4 (quantum AEP for quantum-classical states [352]).

Let $\rho_{XB}\in\mathcal{S}(\mathcal{H}_{X}\otimes\mathcal{H}_{B})$ be
density operator that is classical on $\mathcal{H}_{X}$ and let
$N\in\mathbb{N}$. Then, for any $\varepsilon\geqslant 0$ we have,
$\frac{1}{N}H^{\varepsilon}_{min}(\rho_{XB}^{\otimes N}|\rho_{B}^{\otimes
N})\geqslant H(\rho_{XB})-H(\rho_{B})-\eta$ (2.51) where
$\eta:=(2H_{max}(\rho_{X})+3)\sqrt{\frac{\log(\frac{1}{\varepsilon})}{N}+1}$,
is a function of the smoothing parameter $\varepsilon$ and $N$.

####  2.1.6 Quantum computing

We have so far given a brief and general background on quantum information. In
this section, we will glance over the necessary tools and concepts from
quantum computing that we will require for the rest of this thesis. Let us
begin with this question: _What do we need to make a quantum computer?_ This
question was answered by DiVincenzo in [156], where certain criteria have been
proposed for constructing a quantum computer. The following are the seven
proposed criteria (the last two are necessary for _quantum communication_).

DiVincenzo criteria [156] 1. A scalable physical system with well-
characterized qubit 2. The ability to initialize the state of the qubits to a
simple fiducial state (quantum state preparation) 3. Long relevant decoherence
times 4. A qubit-specific measurement capability 5. A _universal_ set of
quantum gates * The ability to interconvert stationary and flying qubits * The
ability to faithfully transmit flying qubits between specified locations

In the previous sections, we have covered the first four criteria since we
have introduced qubits and their transformations (as well as the notion of
noise) and measurements. In this section, we will focus on the fifth one while
we introduce quantum computation and quantum gates. To see why we need quantum
gates, we need to have a look at different models of computation, especially
in the quantum world.

##### Different models of quantum computation

The first abstract classical model for computation was a _Turing machine
(TM)_. A Turing machine contains four main elements [316]: (a) a program, (b)
a finite state control, co-ordinating the other operations of the machine; (c)
a tape, (which is like a memory); and (d) a read-write tape-head, which points
to the position on the tape which is currently readable or writable. This
simple system is capable of capturing any classical algorithm. The _Quantum
Turing machine (QTM)_ gives the same type of abstraction for quantum
computing. Quantum Turing Machine was firstly proposed by Paul Benioff in 1980
and 1982 [56, 57], and then further formalised by David Deutsch in 1985 [143]
while the alternative model which we will talk about has also been introduced.
Similar to the classical case, a QTM has also a finite set of states
$Q=\\{q_{0},q_{1},\dots\\}$, a finite set of input and working alphabet and an
infinite quantum tape that models the quantum memory and a single ‘head’. QTM
is usually initialised at a state $\ket{\psi(0)}$ and will perform the
computation by applying unitary transformation to the state _i.e._ at every
step $\ket{\psi(i+1)}=U\ket{\psi(i)}$. Finally, the process of reading will
include quantum measurements as one can expect. Although the intuitive notion
of QTM is quite simple, the formal definition is rather complicated and hence
we skip introducing it here.101010Moreover this is not the model of
computation that we use in this thesis.

The most common model of quantum computation (and the one used in this thesis)
is the _quantum circuit model_ , which is a quantum generalisation of the
classical _circuit model_. Classically, a circuit consists of several inputs
and outputs (bits), wires which describe these systems, and several logical
gates [316]. A logical gate is a binary function
$f:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$ for example, AND, OR or NOT gates.
In the quantum circuit model, on the other hand, our inputs are qubit (or more
generally quantum states), and our logical gates are unitary transformations.
In the classical circuit model, to be able to perform _any_ classical
computation we need a _universal gate set_. The quantum circuit model is no
different. A set of quantum gate $\mathcal{G}=\\{G_{i}\\}$ is universal if
_any general $n$-qubit unitary operation_ can be approximated using a quantum
circuits that uses this gate set, with an arbitrary accuracy [316].

The set of universal quantum gates is not _unique_ and different options have
been proposed with different theoretical and most importantly implementational
advantages and disadvantages for implementing over different types of hardware
[117]. All of them, however, require some _sing-qubit_ gates and some
_entangling gates_. In the next section, we introduce some of the most widely
used quantum gates.

To conclude this section, let us briefly mention another model of quantum
computing known as _Measurement-Based Quantum Computing (MBQC)_ introduced in
[351]. The reason for this naming is that in this model, the initial resource
is an entangled state in a form of a graph or cluster (called _graph state_
and _cluster state_), and each operation is performed by applying a
measurement. This technique is also known as _gate teleportation_ [185].
Moreover, MBQC has been shown to be equivalent to the circuit model. We do not
go into further details about this model, since we will not use it in the
thesis.

##### Quantum gates

The first set of single-qubit quantum gates that we introduce is _Pauli_ gates
represented by the Pauli matrices we have seen in Eq. (2.6). We first note
that the computational basis, are the eigenvectors of $Z$, and the plus-minus
basis, are the eigenvectors of the Pauli matrix $X$. The eigenvectors of the
$Y$ operator are also very similar to the $X$ and are given as follows:

$\ket{+i}=\frac{1}{\sqrt{2}}(\ket{0}+i\ket{1}),\quad\quad\ket{-i}=\frac{1}{\sqrt{2}}(\ket{0}-i\ket{1})$
(2.52)

Also one can easily check the action of $X$, $Y$ and $Z$ gate on the
computational basis, by applying their matrix on the basis vectors.

$\begin{split}&X\ket{0}=\ket{1},\quad X\ket{1}=\ket{0}\\\
&Y\ket{0}=-i\ket{1},\quad Y\ket{1}=i\ket{0}\\\ &Z\ket{0}=\ket{0},\quad
Z\ket{1}=-\ket{1}\\\ \end{split}$ (2.53)

The $X$ gate is the equivalent of the classical ‘bit-flip’ gate, and the $Z$
gate is a ‘Phase gate’. The $Y$ gate is the combination of both since $Y=iXZ$.

The next gate is called _Hadamard gate_ , denoted as $H$ that acts as follows
on the computational basis:

$\begin{split}H\ket{0}=\ket{+}&=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\\\
H\ket{1}=\ket{-}&=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})\end{split}$ (2.54)

The Hadamard gate in fact transforms the computational basis to plus-minus
basis. Also, the Hadamard gate creates the symmetric superposition of
computational basis even in higher dimension if it is applied as a tensor
product form $H^{\otimes n}$ over $n$ qubits. The matrix representation of $H$
is as follows:

$H=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\ 1&-1\end{pmatrix}$ (2.55)

As mentioned before, the unitary transformation of a qubit is equivalent (up
to a global phase) to rotation on the Bloch sphere, hence one can define the
general following rotation single-qubit gates [316]:

$\begin{split}R_{X}(\theta)&:=e^{-i\theta/2X}=\begin{pmatrix}\cos{\frac{\theta}{2}}&-i\sin{\frac{\theta}{2}}\\\
-i\cos{\frac{\theta}{2}}&\cos{\frac{\theta}{2}}\end{pmatrix}\\\
R_{Y}(\theta)&:=e^{-i\theta/2Y}=\begin{pmatrix}\cos{\frac{\theta}{2}}&-\sin{\frac{\theta}{2}}\\\
-\cos{\frac{\theta}{2}}&\cos{\frac{\theta}{2}}\end{pmatrix}\\\
R_{Z}(\theta)&:=e^{-i\theta/2Z}=\begin{pmatrix}e^{-i\theta/2}&0\\\
0&e^{i\theta/2}\end{pmatrix}\end{split}$ (2.56)

The most useful 2-qubit gates are CNOT (also called CX or controlled-X) and CZ
(or controlled-Z) gates. The importance of these gates is that they can create
entanglement. Let us first give the matrix representation of these gates:

$\text{CNOT}=\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&0&1\\\
0&0&1&0\end{pmatrix},\quad\quad\text{CZ}=\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\
0&0&1&0\\\ 0&0&0&-1\end{pmatrix}$ (2.57)

In the above gates, the first qubit acts as a ‘control’ and the second qubit
as a ‘target’. CNOT applies a bit-flip or $X$ gate on the second qubit if the
control qubit is $\ket{1}$ (and does nothing if it is $\ket{0}$), and
similarly, CZ applies a $Z$ gate on the second qubit conditioned on the first
one being $\ket{1}$. We also note that the CNOT together with the set of all
single-qubit unitary gates form a universal gate set.

Other general _controlled-gates_ can be also defined similarly as follows:

$\text{CU}_{12}=\ket{0}\bra{0}_{1}\otimes\mathbb{I}_{1}+\ket{1}\bra{1}_{2}\otimes
U_{2}$ (2.58)

where $U$ is conditionally applied on the second qubit.

Finally, a quantum gate that we will use throughout this thesis is another
2-qubit (or generally multi-qubit gate) gate known as the $\mathsf{SWAP}$
gate. The $\mathsf{SWAP}$ gate on two quantum states with arbitrary dimensions
acts as follows:

$\mathsf{SWAP}\ket{\psi}\ket{\phi}=\ket{\phi}\ket{\psi}$ (2.59)

This gate swaps between the Hilbert space of two quantum states. The qubit
$\mathsf{SWAP}$ gate can be built from three CNOT gates, and is given with the
following matrix:

$\mathsf{SWAP}=\begin{pmatrix}1&0&0&0\\\ 0&0&1&0\\\ 0&1&0&0\\\
0&0&0&1\end{pmatrix}$ (2.60)

As a final remark, we note that any single-qubit gate may be approximated to
arbitrary accuracy using a finite set of gates [316]. This is the result of
one of the most important theorems in quantum computing, namely
_Solovay–Kitaev theorem_ [242]. More precisely, the Solovay–Kitaev theorem
states that for any single-qubit gate $U$ and any $\varepsilon\geqslant 0$, it
is possible to approximate $U$ to a precision $\varepsilon$ using
$\Theta(log^{c}(1/\varepsilon))$ gates from a fixed finite set, where $c$ is a
small constant approximately equal to 2.

###  2.2 Distinguishability and verification of quantum states

An important difference between qubits and classical bits (and generally
quantum and classical states) is that it is impossible to obtain the exact
classical description111111Here by ‘classical description’ we mean the value
of the amplitudes in a specific basis with arbitrary precision of a single
given copy of a quantum system. This important limitation imposed by quantum
mechanics is closely related to _no-cloning theorem_ , which we will
thoroughly introduce in Section 2.3, and we will also further discuss this
fundamental connection in Section 3.2. However, having access to copies of the
same quantum system allows for the extraction of the state’s description. As a
result, there exists a bound on how well one can derive the classical
description of quantum states depending on their dimension and the number of
available copies. This problem is known as the problem of _state estimation_
in quantum information [222, 343]. Due to the experimental relevance, in
addition to quantum information, this problem has been also widely studied in
quantum optics [343, 157, 177, 325].

Another tightly related yet different problem in quantum information is the
problem of _state discrimination_. State discrimination refers to the task of
distinguishing an unknown (pure or mixed) state $\rho$ in a known set of
states. More precisely, given an $d$-level quantum system $\rho$ be one of the
states from the set $\\{q_{i},\rho_{i}\\}^{N}_{i=1}$, that the ensemble of
states $\rho_{i}$s, each happening with probability $q_{i}$, the goal is to
determine $\rho$ is which one of the states of the set, by performing the best
possible POVM, leading to the minimum error discrimination probability.

For the case of two mixed states, the best probability of discrimination is
given by a famous bound in quantum information theory known as _Holevo-
Helstrom_ bound:

$Pr^{opt}_{\text{guess}}=\frac{1}{2}+\frac{1}{2}|\\!|q_{1}\rho_{1}-q_{2}\rho_{2}|\\!|_{1}=\frac{1}{2}+d_{\text{Tr}}(q_{1}\rho_{1}-q_{2}\rho_{2})$
(2.61)

Also, for two pure quantum states $\ket{\psi_{1}}$ and $\ket{\psi_{2}}$, there
exists a general optimal strategy for state discrimination with projective
measurements. This result which we represent in the following theorem is an
indirect consequence of _Neumark’s theorem_ (or Naimark’s theorem) for general
POVMs [75], and hence sometimes called Neumark’s measurements.

######  Theorem 5.

The best discrimination strategy for two pure state $\ket{\psi_{1}}$ and
$\ket{\psi_{2}}$ with projective measurements $\\{\ket{v_{1}},\ket{v_{2}}\\}$,
where $\ket{v_{1}}$ and $\ket{v_{2}}$ are in the span of $\ket{\psi_{1}}$ and
$\ket{\psi_{2}}$such that $\bra{v_{1}}v_{2}\rangle=0$, is when they are
symmetric with respect to the angle bisector of $\ket{\psi_{1}}$ and
$\ket{\psi_{2}}$, and $\ket{v_{i}}$ is closer to $\ket{\psi_{i}}$ for $i=1,2$.
On outcome ”$\ket{v_{i}}$”, we guess $\ket{\psi_{i}}$. Moreover, let the angle
between $\ket{\psi_{1}}$ and $\ket{\psi_{2}}$ be defined as:
$\theta=\arccos{|\bra{\psi_{1}}\psi_{2}\rangle|^{2}}$. Then the success
probability of this strategy is given by:
$Pr_{\text{succ}}=|\bra{\psi_{1}}v_{1}\rangle|^{2}=\cos^{2}{(\frac{\pi/2-\theta}{2})}=\frac{1}{2}+\frac{1}{2}\sin{\theta}$
(2.62)

One can check that this optimal probability, can be obtained from Holevo-
Helstrom bound in Eq. (2.61) as a special case.

We can also assume another quantum state discrimination scenario where we do
not get any false results, while we allow the measurement outcome to be
inconclusive. This means that if the measurement outcome indicates one of the
states, we know, for sure, that it’s the correct state. Although sometimes the
measurement’s outcome is: ‘I don’t know’! In the literature of quantum
computing, this scenario is known as _unambiguous state discrimination_ [228,
155, 334]. We note that this problem is particularly of interest from an
experimental point of view and while dealing with imperfect measurement
devices and observers [58, 306, 59]. In this problem again, the goal is to
find the best set of POVM measurements for this problem. Then minimise the
probability of an inconclusive outcome, finding the optimal POVMs. For the
case of two pure quantum states with equal prior probability, the following
optimal strategy has been given and proved optimal in [228, 155, 334].

######  Theorem 6.

The best strategy to unambiguously discriminate two pure states
$\ket{\psi_{1}}$ and $\ket{\psi_{2}}$ is to carry out the POVM
$\\{E_{0},E_{1},E_{2}\\}$ where we guess $\ket{\psi_{2}}$ if the outcome is 1,
we guess $\ket{\psi_{1}}$ if the outcome is 2, and the discrimination is
inconclusive if the outcome is 0. The optimal probabilities for this case are
given as follows for the angle between $\ket{\psi_{1}}$ and $\ket{\psi_{2}}$
is $\theta$. $\begin{split}&Pr[\text{outcome
1}]=tr(E_{1}\rho)=1-\cos{\theta}\\\ &Pr[\text{outcome 2}]=tr(E_{2}\rho)=0\\\
&Pr[\text{outcome 0}]=tr(E_{0}\rho)=\cos{\theta}\end{split}$ (2.63)

Nevertheless, this is the simplest case of unambiguous state discrimination
and the problem has been generalised to $N$ linearly independent states in
[101], and to mixed states in [60, 362] and the reader can also find one of
the most recent developments on this topic in [234].

Note that, in general, the discrimination problem is directly related to the
trace distance between the given quantum states. More generally,
distinguishing between different quantum states is related to their _quantum
distance_ , quantified by distance measures. We have introduced some of them
in Section 2.1.4. While possibly the most common distance measure for this
purpose is the trace distance, here we want to give a general definition of
distinguishability with Uhlmann fidelity. This definition is one of the most
acquainted definitions in the thesis.

######  Definition 10 ($\mu$-distinguishability).

Let $0\leqslant\mu\leqslant 1$ be the distinguishability threshold parameter.
We say two quantum states $\rho$ and $\sigma$ are $\mu$-distinguishable if
$0\leq F(\rho,\sigma)\leqslant 1-\mu$.

Note that two quantum states, $\rho$ and $\sigma$, are _completely
distinguishable_ or 1-distinguishable ($\mu=1$), if $F(\rho,\sigma)=0$.

One can also define the $\nu$-indistinguishability in the same manner:

######  Definition 11 ($\nu$-indistinguishability).

Let $0\leqslant\nu\leqslant 1$ the indistinguishability threshold parameter.
We say two quantum states $\rho$ and $\sigma$ are $\nu$-indistinguishable if
$\nu\leq F(\rho,\sigma)\leq 1$.

####  2.2.1 Verifying quantum states

Due to the impossibility of perfectly distinguishing quantum states, checking
the equality of two completely unknown states is a non-trivial task. The task
of _equality testing_ is a simple but an extremely important task and a
building block for lots of complicated quantum protocols [49, 37, 418]. The
objective is to test whether two _unknown_ quantum states are the same. First,
we introduce the most well-known quantum algorithm for equality testing. The
content of this section is widely used throughout the thesis in all the
chapters (perhaps less used in Chapter 7). Thus, familiarity with the notions
and notations used here is crucial.

##### SWAP test

Given a single copy of two unknown quantum states $\rho$ and $\sigma$, is
there a simple test to optimally determine whether the two states are equal or
not? This question was answered affirmatively by Buhrman et al. [49] when they
provided a test called the SWAP test. This test was initially used by the
authors to prove an exponential separation between classical and quantum
resources in the simultaneous message passing model. Since then it has been
used as a standard tool in the design of various quantum algorithms [48, 238].
A SWAP test circuit takes as an input the two unknown quantum states $\rho$
and $\sigma$ and attaches an ancilla $\ket{0}$. A Hadamard gate is applied to
the ancilla followed by the control-SWAP gate and again a Hadamard on the
ancilla qubit. Finally, the ancilla is measured in the computational basis and
we conclude that the two states are equal if the measurement outcome is ‘0’
(labelled accept). Fig. 2.2 illustrates this test in the special case when the
state $\sigma$ is a pure state and shown by $\ket{\psi}$.

$\Qcircuit<EMAIL_ADDRESS>\lstick{\rho}\qw\multigate{1}{\text{SWAP}}\qw\qw\\\
\lstick{\ket{\psi}}\qw\ghost{\text{SWAP}}\qw\qw}$ Figure 2.2: The SWAP test
circuit

It can be shown that the probability the SWAP test accepts the states $\rho$
and $\sigma$ is [252],

$\text{Pr}[\text{SWAP accept}]=\frac{1}{2}+\frac{1}{2}\text{Tr}(\rho\sigma)$
(2.64)

In the special case of when at least one of the states (let’s say $\sigma$) is
a pure state $\sigma=\ket{\psi}\bra{\psi}$, the probability of acceptance is,

$\text{Pr}[\text{SWAP
accept}]=\frac{1}{2}+\frac{1}{2}|\bra{\psi}\rho\ket{\psi}|=\frac{1}{2}+\frac{1}{2}F(\rho,\ket{\psi}\bra{\psi})$
(2.65)

Thus when at least one of the two states is a pure state, the acceptance
probability is related to the fidelity between the states. Implying that if
the states are the same, the acceptance probability is 1. However, when the
states are different, the SWAP test accepting the states implies an error. The
error in the SWAP test, when the states are not identical (also called the
one-sided error), is $\text{Pr}[\text{accept}]$. Nevertheless, this error can
be brought down to any desired error $\varepsilon>0$ by running multiple
instances of the SWAP test circuit. Let $M$ be the number of copies of both
input states. Then the number of instances, required to bring down the error
probability to a desired $\varepsilon$ is,

$\begin{split}\text{Pr}[\text{SWAP
error}]&=\prod^{M}_{j=1}\text{Pr}[\text{SWAP
accept}]_{j}=(\frac{1}{2}+\frac{1}{2}F)^{M}=\varepsilon\\\ &\Rightarrow
M(\log(1+F)-1)=\log(\varepsilon)\Rightarrow
M\approx\mathcal{O}(\log(1/\varepsilon))\end{split}$ (2.66)

where $F=F(\rho,\ket{\psi}\bra{\psi})=\bra{\psi}\rho\ket{\psi}$ and we use the
fact that fidelity is independent of $\varepsilon$.

Now let us introduce a generalisation of this equality test.

##### Generalised SWAP test

The above SWAP test is optimal in Equality testing (in a single instance) of
two unknown quantum states when one has a single copy of the two states.
However, there are certain quantum protocols where one has access to multiple
copies of one unknown state $\ket{\psi}$ and only a single copy of the other
unknown state $\rho$ and the objective is to provide an optimal Equality
testing circuit. Considering this scenario, Chabaud et al. [109] provided an
efficient construction of such a circuit, a generalised SWAP (GSWAP) test
circuit. A GSWAP circuit takes as an input a single copy of $\rho$, M copies
of $\ket{\psi}$ and $\lceil\log M+1\rceil$ copies of the ancilla qubit
$\ket{0}$. The generalised circuit is then run on the inputs, and the ancilla
qubits are measured in the computational basis. Fig. 2.3 is a generic
illustration of such a circuit. For more details on the circuit refer to the
original work [109].

Figure 2.3: GSWAP: A generalisation of the SWAP test with a single copy of
$\rho$ and $M$ copies of $\ket{\psi}$. The circuit also inputs
$n=\big{\lceil}\log M+1\big{\rceil}$ ancilla qubits in the state $\ket{0}$. At
the end of the circuit, the ancilla states are measured in the computational
basis.

It can be shown that the probability the GWAP circuit accepts two quantum
states $\rho$ and $\ket{\psi}$ is,

$\text{Pr}[\text{GSWAP
accept}]=\frac{1}{M+1}+\frac{M}{M+1}\bra{\psi}\rho\ket{\psi}=\frac{1}{M+1}+\frac{M}{M+1}F$
(2.67)

where $F=F(\rho,\ket{\psi}\bra{\psi})$. We note that in the special case of
$M=1$, the GSWAP test reduces to the SWAP test. Also in a single instance,
GSWAP provides a better Equality test compared to the SWAP test since it
reduces the one-sided error probability. In the limit $M\rightarrow\infty$, we
obtain the optimal acceptance probability of
$\text{Pr}[\text{accept}]=F=\bra{\psi}\rho\ket{\psi}$. Another important
feature of GSWAP is that it can achieve any desired success probability
$\varepsilon(\geqslant F)$ in just a single instance which is impossible to
achieve using SWAP circuit. However, the number of copies required is
exponentially more than the number of instances that the SWAP circuit has to
run to achieve the same error probability,

$\begin{split}\text{Pr}[\text{GSWAP error}]&=\text{Pr}[\text{GSWAP
accept}]=\frac{1}{M+1}+\frac{M}{M+1}F=\varepsilon\\\ &\Rightarrow
M\approx\mathcal{O}(1/\varepsilon)\end{split}$ (2.68)

##### Abstract quantum test

We can also abstract the notion of quantum equality testing of quantum states.
We introduce our own abstract version of such test algorithms by defining the
necessary conditions for a general quantum test.

######  Definition 12 (Quantum Testing Algorithm).

Let $\rho^{\otimes\kappa_{1}}$ and $\sigma^{\otimes\kappa_{2}}$ be
$\kappa_{1}$ and $\kappa_{2}$ copies of two quantum states $\rho$ and
$\sigma$, respectively. A Quantum Testing algorithm $\mathcal{T}$ is a quantum
algorithm that takes as input the tuple
($\rho^{\otimes\kappa_{1}}$,$\sigma^{\otimes\kappa_{2}}$) and accepts $\rho$
and $\sigma$ as equal (outputs 1) with the following probability
$\small\mathrm{Pr}[1\leftarrow\mathcal{T}(\rho^{\otimes\kappa_{1}},\sigma^{\otimes\kappa_{2}})]=1-\mathrm{Pr}[0\leftarrow\mathcal{T}(\rho^{\otimes\kappa_{1}},\sigma^{\otimes\kappa_{2}})]=f(\kappa_{1},\kappa_{2},F(\rho,\sigma))$
where $F(\rho,\sigma)$ is the fidelity and
$f(\kappa_{1},\kappa_{2},F(\rho,\sigma))$ satisfies the following limits:
$\begin{cases}\lim_{F(\rho,\sigma)\rightarrow
1}f(\kappa_{1},\kappa_{2},F(\rho,\sigma))=1&\quad\forall\>(\kappa_{1},\kappa_{2})\\\
\lim_{\kappa_{1}=1,\kappa_{2}\rightarrow\infty}f(\kappa_{1},\kappa_{2},F(\rho,\sigma))=F(\rho,\sigma)\\\
\lim_{\kappa_{1}\rightarrow\infty,\kappa_{2}=1}f(\kappa_{1},\kappa_{2},F(\rho,\sigma))=F(\rho,\sigma)\\\
\lim_{F(\rho,\sigma)\rightarrow
0}f(\kappa_{1},\kappa_{2},F(\rho,\sigma))=\texttt{Err}(\kappa_{1},\kappa_{2})\end{cases}$
(2.69) with $\texttt{Err}(\kappa_{1},\kappa_{2})$ characterising the
statistical error of the test algorithm.

As an example, for the GSWAP test where $\kappa_{1}=1$ and $\kappa_{2}=M$, we
obtain from Eq. (2.68) that the probability of acceptance in the limit
${F(\rho,\ket{\psi}\bra{\psi})\rightarrow 1}$ is 1, while it is
$\frac{1}{M+1}$ in the limit ${F(\rho,\ket{\psi}\bra{\psi})\rightarrow 0}$. It
can be inferred from the above definition that the quantum test can be
idealized by forcing the $\texttt{Err}(\kappa_{1},\kappa_{2})$ to be zero for
any given number of copies. We discuss this last point later in Chapter 4,
when we introduce an ideal version of such abstract tests.

###  2.3 Quantum cloning

In this section, we introduce one of the core concepts of this thesis: the no-
cloning theorem and quantum cloning. This section (specifically subsection
2.3.1) is essential for Chapter 7 and not mostly used in other chapters,
except for the general notion of no-cloning. First, we discuss the
impossibility of _perfectly_ cloning quantum states via the no-cloning theorem
and then we discuss how we can step out of this limitation on the quantum
world and go beyond this impossibility.

The no-cloning theorem states that it is not possible to perfectly clone an
_unknown_ quantum state. The proof of this theorem is most commonly known to
be the work of Wootters and Zurek [417], and also independently done by Dieks
[154] in 1982. Although it seems that it has originally been discovered in
1970 by Park [331]. One formulation of the no-cloning theorem is as follows.

######  Theorem 7 (The no-cloning theorem).

There exists no unitary transformation $U_{c}$ that performs the following
operation on an arbitrary unknown state $\ket{\psi}\in\mathcal{H}$, a blank
(or reference) state $\ket{0}\in\mathcal{H}$ of the same Hilbert space and any
arbitrary ancillary state $\ket{a}$:
$\ket{\psi}\ket{0}\ket{a}\overset{U_{c}}{\rightarrow}\ket{\psi}\ket{\psi}\ket{a_{\psi}}$
(2.70)

There exist several proofs of this theorem. Here we give a simple one, similar
to what can be found in [78]. The proof is by contradiction. Let us assume
that such a unitary $U_{c}$ exists. We note that all the states $\ket{\psi}$,
$\ket{0}$ and $\ket{a}$ (whose dimension does not need to be specified) are
normalized. Since the state $\ket{\psi}$ is arbitrary, the unitary should be
working similarly for any state. Now we assume two non-orthogonal input states
$\ket{\psi}$ and $\ket{\phi}$, for which the cloning transformation should be
as follows.

$\begin{split}&U_{c}(\ket{\psi}\ket{0}\ket{a})=\ket{\psi}\ket{\psi}\ket{a_{\psi}}\\\
&U_{c}(\ket{\phi}\ket{0}\ket{a})=\ket{\phi}\ket{\psi}\ket{a_{\phi}}\end{split}$
(2.71)

where $\ket{a_{\psi}}$ and $\ket{a_{\phi}}$ represent the output states of the
ancilla after the cloning transformation. Regardless of the dimension of the
ancillary states, we have that $|\bra{a_{\psi}}a_{\phi}\rangle|\leqslant 1$.
Also, the unitary transformation preserves the inner product. Now, let us
inner product both sides of the Eq. (2.71), which leads to the following:

$\bra{\psi}\phi\rangle=\bra{\psi}\phi\rangle^{2}\bra{a_{\psi}}a_{\phi}\rangle\Rightarrow\bra{\psi}\phi\rangle=\frac{1}{\bra{a_{\psi}}a_{\phi}\rangle}$
(2.72)

which can clearly be never satisfied and hence the contradiction has been
shown. There are two cases where one cannot reach such contradictions. The
first one is the trivial case of $\bra{\psi}\phi\rangle=1$, and the other one
is the two states are known to be orthogonal _i.e._ $\bra{\psi}\phi\rangle=0$.
The latter case is intuitively very insightful since it corresponds to cloning
a classical bit, which we know is possible. We will dig further into this in
Chapter 3. Moreover, we note that here, no assumption has been made on the
unitary, and the no-cloning has been only the result of the unitarity of the
transformations in quantum mechanics.

It is also worth mentioning that no-cloning is such a fundamental aspect of
nature that it extends to other areas of physics. In fact, cloning is also
impossible if we consider the impossibility of superluminal signalling to be
held, which we do, due to special relativity. This no-go theorem is known as
_no-signalling_ [193, 315] and it is known that if perfect cloning could be
possible, it would lead to a contradiction with the fact that no signal can
travel faster than the speed of light. No-cloning, is also deeply connected to
many other no-go results in quantum information, such as no-broadcasting
theorem [44, 335], no-deleting theorem [255], no-superposing theorem [324,
159].

####  2.3.1 Cloning beyond the no-cloning theorem

Well, _the show must go on_! The no-cloning theorem has not been the end of
the road for this part of quantum information. On the contrary, the beginning
of a rich field of research. To go around the no-cloning limitation, we must
lower our expectations from the cloning machine! Remember that we expected the
cloning machine to be _deterministic_ (meaning that we always want to get the
clones with probability 1) and _exact_ (which means that the output states
should be both perfect copies of the initial state). It turned out that by
relaxing each of these conditions, quantum cloning can be made possible. We
call the transformation that achieves such tasks a quantum cloning machine
(QCM).

Relaxing the first condition leads to a class of quantum cloning known as
_probabilistic cloning_ , originated by these works [148, 149]. A
probabilistic cloning machine produces _perfect_ clones, but only _some times_
, i.e. it succeeds with a certain probability. As one can guess, there are
information-theoretic upper bounds on this success probability. In this
thesis, we do not focus on probabilistic cloning, although we refer the
interested readers to these reviews on quantum cloning, including the
probabilistic cloning [373, 182, 78].

The second condition, on the other hand, was historically the first one to be
relaxed by Buzek and Hillery in [67], leading to the field of _Approximate
quantum cloning_. In approximate cloning, the operation is deterministic,
however, we allow the clones to be not perfect, i.e. have some distance from
the original quantum state. The most important property of an approximate
cloner is the quality of the output clones, which is measured by the fidelity
between the clone and the original state. The next important factor is the
family of states we require the cloning machine to clone. Each family of
states leads to a class of approximate cloning machines. For instance, if the
family of states we consider is _all_ the possible states of a Hilbert space,
the cloner is called _universal quantum cloner_. However, this set can be made
more restricted, meaning that more prior information of the initial states is
known, which in turn will lead to cloners with higher optimal fidelity as we
will see.

Another property of a cloning machine is _symmetry_. When a cloning machine is
symmetric, it means that both of the outputted clones should be the same,
relative to the comparison measure. This symmetry is considered when the
fidelity is to be optimised, which means that most of the time the symmetric
cloners are optimised with respect to _local fidelity_ , i.e. the fidelity of
each clone state. While we can also have _asymmetric cloners_ [113, 112, 227,
146] where the fidelity of one clone is higher than the other one. The quality
(especially in the asymmetric case) of the cloner can also be measured with
respect to the joint state of both of the clones in comparison to two perfect
clones. This fidelity measured is referred to as _global fidelity_. In Chapter
7, where we introduce a machine learning algorithm for the task of cloning,
this distinction between global and local fidelity becomes a subtle and
important factor.

Finally, the generalisation of the cloning problem is when we have $M>1$
copies of the input state and we require to create $N>M$ approximate clones
(known as $N\rightarrow M$ cloning). In this case enforcing _symmetry_ would
correspond to

$F^{j}_{\operatorname{\textsf{L}}}=F^{k}_{\operatorname{\textsf{L}}},\qquad\forall
j,k\in\\{1,\dots N\\}.$ (2.73)

Where $F$ denotes the fidelity. Now let us briefly discuss three main classes
of cloning machines.

##### Universal quantum cloning

The earliest result in approximate cloning was a universal symmetric cloning
machine (UQCM) [67]. A UQCM is completely agnostic about the input state and
is aimed to clone any given quantum state of a Hilbert space with a given
dimension. For the case of a qubit, where we want to clone all the qubits on
the Bloch sphere, it has been shown that this cloner can achieve the optimal
cloning fidelity of $5/6\approx 0.8333$. This optimal cloner, takes as input
an initially unknown state, a blank state and an ancillary qubit, and maps
them to a 2-qubit state (the ancillary state is traced out) where the fidelity
of each subsystem, or in other words, each reduced density matrices, is
optimised to the maximum value of fidelity, leading to the optimal local qubit
fidelity of
$F_{\mathsf{L},\textrm{opt}}^{\text{U},1}=F_{\mathsf{L},\textrm{opt}}^{\text{U},2}=5/6$.

Now, in the generalised case, we can provide multiple ($M$) copies of a state
to the cloner and request $N$ output approximate clones which is referred to
as $M\rightarrow N$ cloning [199, 55]. Generalizing the universal cloning
fidelity
($F_{\mathsf{L},\textrm{opt}}^{\text{U},j}):=F_{\mathsf{L},\textrm{opt}}^{\text{U},j}(1,2))$
to the $M\rightarrow N$ scenario, the optimal local fidelity becomes:

$F^{\textrm{U},j}_{\operatorname{\textsf{L}},\textrm{opt}}(M,N)=F^{\textrm{U}}_{\operatorname{\textsf{L}},\textrm{opt}}(M,N)=\frac{MN+M+N}{N(M+2)}$
(2.74)

Here $N-M$ ancilla qubits are used to assist, so the initial state is
$\ket{\psi_{A}}^{\otimes M}\otimes\ket{0}^{\otimes N-M}$. We also note that in
the limit $M\rightarrow\infty$, an optimal cloning machine becomes equivalent
to a quantum state estimation machine [373] for universal cloning. We will
further discuss the intuitive meaning and relevance of this important result
for our purpose in Chapter 3. In the context of cryptography, $M\rightarrow N$
cloning can be also modelled as having $N$ adversaries, $E_{1}\dots E_{N}$ who
receive $M$ copies of the state to be cloned.

##### Phase-covariant cloning

Phase-covariant (introduced by [47]) states are equatorial states of Bloch
sphere. It is common to choose the $\mathsf{X}-\mathsf{Y}$ plane to describe
such states:

$\ket{\psi_{xy}(\eta)}=\frac{1}{\sqrt{2}}\left(\ket{0}+e^{i\eta}\ket{1}\right)$
(2.75)

It is known that a phase-covariant cloning machine (PCQCM) that clones one
equatorial qubit to two clones has the optimal local fidelity
$F_{\mathsf{L},\text{opt}}^{\text{PC}}\approx 0.85>5/6$, which is notably
higher than the universal case.

These states are relevant since they are used in BB84 QKD protocols and also
in universal blind quantum computation protocols [35, 61]. Here in the context
of QKD, we have the following scenario: Assume that Alice wishes to transmit
quantum information to Bob (here the information is the bits of the key) but
the channel is subject to an eavesdropper, Eve, who wishes to adversarially
gain knowledge on the message sent by Alice.

Figure 2.4: Cartoon illustration of an eavesdropping attack by Eve, trying to
clone the state, $\rho_{A}$, Alice sends to Bob. Eve injects a ‘blank’ state
(which can be a specific state or an arbitrary state depending on the
scenario, which ends up as a clone of $\rho_{A}$) and an ancillary system
($E^{*}$). She then applies the cloning unitary, $U$. We can assume the cloner
is manufactured by Eve to give her the greatest advantage. The state Bob
receives will be the partial trace over Eve’s subsystems,
$\rho_{B}=\mathsf{Tr}_{EE^{*}}(\rho_{BEE^{*}})$, and Eve’s clone will be
$\rho_{E}$, where $\rho_{BEE^{*}}$ is the full output state from the QCM.

We illustrate this in Fig. 2.4, for a single Eve. In this picture, Alice ($A$)
sends a quantum state121212This will typically be a pure state,
$\rho_{A}:=\ket{\psi}\bra{\psi}_{A}$, but it can also be generalised to
include mixed states, in which the task is referred to as _broadcasting_[44,
103, 144]. The _no-broadcasting_ theorem is a generalisation of the no-cloning
theorem in this setting., $\rho_{A}$, to Bob ($B$). A cloning based attack
strategy for Eve ($E$) could be to try and clone Alice’s state, producing a
second (approximate) copy which she can use later in her attack, with some
ancillary register ($E^{*}$).

Interestingly, the cloning of phase-covariant states can be accomplished in an
_economical_ manner, meaning without needing an ancilla system for Eve,
$E^{*}$[318]. However, as noted in [373], removing the ancilla is useful to
reduce resources if one is _only_ interested in performing cloning, but if Eve
wishes to attack Alice and Bob’s communication, it is more beneficial to apply
an ancilla-based attack. Intuitively, this is because the ancilla also
contains information about the input state which Eve can extract. Of interest
to our purposes, is an explicit quantum circuit which implements the cloning
transformation. A unified circuit [40, 182, 180] for the above cases
(universal and $\mathsf{X}-\mathsf{Y}$ phase covariant) can be seen in Fig.
2.5. The parameters of the circuit,
$\boldsymbol{\alpha}=\\{\alpha_{1},\alpha_{2},\alpha_{3}\\}$, are given by the
family of states the circuit is built for [40, 182, 180].

For phase-covariant cloning of $\mathsf{X}-\mathsf{Y}$ states, we explicitly
have the following optimal angles: