Foundations for quantum algorithms and complexity

Carlos Eduardo Teixeira Tavares June 2022 UMinho|2020 Foundations for Quantum Algorithms and Complexity Foundations for Quantum algorithms and Complexity Carlos Eduardo Teixeira Tavares Universidade do Minho Escola de Engenharia The MAP-i Doctoral Programme in Computer Science, of the Universities of Minho, Aveiro and Porto Universidade do Minho June 2022 Supervisor: Professor Doutor Luís Manuel Dias Coelho Soares Barbosa Carlos Eduardo Teixeira Tavares Foundations for Quantum Algorithms and Complexity Universidade do Minho Escola de Engenharia The MAP-i Doctoral Programme in Computer Science, of the Universities of Minho, Aveiro and Porto Universidade do Minho COPYRIGHT AND TERMS OF USE FOR THIRD PARTY WORK This dissertation reports on academic work that can be used by third parties as long as the internationally accepted standards and good practices are respected concerning copyright and related rights. This work can thereafter be used under the terms established in the license below. Readers needing authorization conditions not provided for in the indicated licensing should contact the author through the RepositóriUM of the University of Minho. license granted to users of this work: CC BY https://creativecommons.org/licenses/by/4.0/ ii ACKNOWLEDGEMENTS The first time I heard about quantum computation was in the far far away year of 2002, when I was still in high school, during a conversation with my colleagues in the interval of physics class. It came at a time where I was simultaneously entering my adulthood and taking important decisions about what to do with my professional life. I can say that the idea immediately captured my attention, not only due the potential impact of the technology, which was clear from the very first moment, but mostly because it somehow combined two things I truly enjoyed: physics and computation. For practical reasons, I did not pursue the study quantum computation immediately by then, but many years later, after many twists and turns in my career and life, I decided to enroll on a doctoral programme to study the topic and many years after that moment, I am able to put together this work. The path was long, and somehow tortuous at times, but definitely rewarding. There are, of course, many important people who supported me along the way, helping to make this work a reality, to whom I feel very grateful. First and foremost, my most sincere thanks to my advisor Prof. Luís Soares Barbosa, for the great opportunity of pursuing this interest of mine, for the uncountable opportunities that truly helped me becoming a better researcher, and also for the patience, generosity, time and dedication to this work, for which I will be forever indebted. I did not have no one assigned, formally, the role of co-advisor, but definitely there were some people with whom I ended up collaborating more closely. My thanks for Prof. Mikhail Vasilevskiy for the great cooperation, and for always being able, and available, to answer all my questions about physics, from whom I learnt a lot. Also, to professor Alexandru Baltag, for the profound insights on quantum logic and for the warm welcome during my stay in Amsterdam and to Professor Jamie Vicary, my external advisor, for his availability and valuable insights about quantum computation and about doing research and being a researcher. My time of being student of quantum computation also coincided with the birth of a wide interest on the study of the discipline in the university across many departments, and due to this I had the privilege of collaborating with many people from different backgrounds, who definitely influenced me, as well as the ideas that shape this work. A word of thanks to professors José Espírito Santo, Pedro Patrício, José Nuno Oliveira, Manuel Martins and Rui Soares Barbosa for helping shape my understanding of computation, logic, mathematics and physics. Also, my acknowledgements, to prof. Andrei Postnikov and Tomás Veloz, for providing valuable contributions to my research work. Finally, a word of thanks to prof. Nuno Peres, for letting me assist to his classes and introducing me, seriously, to quantum mechanics, I could not wish for a better introduction. iii iv Teaching was one of the greatest experiences of this past few years, and of course I would thank to all my students, with their young and bright minds, for pushing me forward to learn more about quantum computation, so that I could teach them. Some of them ended up having a closer cooperation with me, and here, my special thanks to José Guimarães, Vitor Gonçalves and Marta Sofia Oliveira. Not only of science is made a doctoral programme, and I would also to thank the people who shared with me the pains of being a PhD student and have been present in many cheerful events that took place throughout these years: from conferences in Brasil, to a certain summer school in a convent near Braga, our hiking trips to the Gerês region, or simply during our lunches at the canteen of University of Minho. My thanks to my colleagues from the ARCA group: Alexandre, Leandro, Renato, José Proença, Guillermina, who became my friends. Also, to my colleagues of 2.17 laboratory, for the relaxed environment in the laboratory and outside of it, in our numerous field trips to settle the most important research question: which Francesinha is best, Porto or Braga. The quest, despite the extensive field work, the long argumentations about the historical importance of the former and the innovative character of the latter, apparently fostered by an excess of eggs and cream in the region of Braga, remains open, i.e. it remains a question of personal taste. Also, my thanks to the innumerous brilliant people I have met during my stay in HASLAB laboratory, Ana, Ali, Paolo Masci, Vitor Enes and many others, for all the nice conversations about multiple subjects. Outside research there should be a life too, although severely conditioned at certain stage, due to the demands of academic work, but lately, also due to a unfortunate pandemic situation. To my friends and colleagues who have supported me in this endeavour throughout the years, sometimes without knowing it, from toy assignments about quantum computation in the early years of college, to cheerful moments around a table, or simply through kind words in darker days, a big word of thanks. Finally, to my family, specially to my parents, Ana Maria and Jorge, an infinite word of thanks, for the unconditional love and truthfully rock-solid support, but mostly, for everything . I would like also to acknowledge the institutions where I carried this work, University of Minho and the High-Assurance software laboratory (HASLAB/INESCTEC), for providing me with the necessary conditions to do so. Partial finantial support is acknowledged to INESC TEC, through the internal grant of reference 3179/BI_B2C/15 within the project INESC TEC-EEA/50014, funded by national funds and FEDER, in scope of Portugal 2020, as well as to the FCT – Fundação para a Ciência e Tecnologia (FCT) by means of the individual grant SFRH/BD/116367/2016, funded under the POCH programme and MCTES national funds. This dissertation was partially supported by the ERDF – European Regional Development Fund through the Operational Programme for Competitiveness and Internationalisation - COMPETE 2020 Programme and by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia, within project POCI-01-0145-FEDER-030947. iv STATEMENT OF INTEGRITY I hereby declare having conducted this academic work with integrity. I confirm that I have not used plagiarism or any form of undue use of information or falsification of results along the process leading to its elaboration. I further declare that I have fully acknowledged the Code of Ethical Conduct of the University of Minho. v FOUNDATIONS FOR QUANTUM ALGORITHMS AND COMPLEXITY Recently, quantum computation has been generating a lot of interesting from both industry and academia, due to the first results on quantum supremacy, i.e. the first time quantum computers were able to perform efficiently tasks deemed unfeasible to classical computers, made possible by the state-of-art qubit technology. These achievements, despite the unusefulness of the tasks performed (quantum circuit sampling), provide evidence that real world quantum computation is not only evolving, but also, that full-scale quantum computers may be a reality in the mid-term future. The benefits of quantum computation are well-known to be potentially ground-breaking, from making RSA cryptography unsecure, to the efficient simulation of quantum systems. On theoretical side, the algorithm body of knowledge has evolved, and nowadays, there is already a huge number of algorithms and techniques scattered across a vast realm of applications, from solving certain linear equations to optimization. Nonetheless, the progress in the development of new algorithms with an exponential advantage , rather than polynomial , has been quite slow and even the application of the existent quantum computational techniques to new problems is far from being a trivial task. The main motivation for this work was to contribute to this problem, and do so by following a foundational approach, i.e. by the understanding of the structures of the computational advantage of quantum algorithms and the conception of formal methods to aid in their application to new problems. Such an approach has to deal with two somewhat orthogonal perspectives of quantum algorithms: complexity and semantics. The contribution of this work can also be divided in these two perspectives: in one hand we try to identify and characterize the structures that carry the so-called quantum advantage and exercise them with new applications, and in the other hand we propose tools to deal with the correction of quantum algorithms, particularly, we discuss a dynamic logic for a class of quantum programs: the ones expressible in the quantum assembly programming language (QASM). Concerning the algorithmic side of the contribution we propose two new applications for quantum algorithms: the first one from quantum biology, concerning the simulation of the non-radiative effects of electronic transport through a molecular chain in a photosynthesis system; the second one belongs to the field of quantum chemistry, and concerns the calculation of the ground state of the Hydrogen and Lithium-Hydride molecules, under the action of a strong electrical field (the stationary Stark effect). Both applications were implemented and experimented in a real-world quantum computer, the IBM Q. keywords: biology, chemistry, dynamic logic, quantum computation vi FUNDAMENTOS DE ALGORITMOS QUÂNTICOS E COMPLEXIDADE Recentemente, o interesse em computação quântica tem vindo a aumentar exponencialmente, devido ao facto da meta da ”supremacia quântica”, momento em que os computadores quânticos são capazes de realizar tarefas intratáveis para computadores clássicos, ter sido recentemente atingida por equipas independentes, utilizando arquiteturas de qubits quânticos diferentes. Isto dá evidência da saudável velocidade de evolução da área, e fortalece a ideia de que os computadores quânticos em grande escala, podem vir a ser uma realidade no futuro. Os benefícios, há muito conhecidos, podem ser realmente transformadores em campos como a criptografia, ao tornar a criptografia RSA obsoleta, assim como tornar possível a simulação de muitos sistemas quânticos, com aplicações em muitas áreas da ciência, como na química, ou na física de partículas. O campo teórico dos algoritmos, baseando-se nos sucessos dos primórdios da computação quântica, como foram os algoritmos de Grover e Shor, tem vindo a crescer, sendo que existe um vasto campo de aplicações, desde a resolução de equações lineares, até variados métodos de resolução de problemas de otimização. Não obstante, o progresso no desenvolvimento de algoritmos quânticos que consigam tirar completo proveito da vantagem quântica tem sido lento, e mesmo a aplicação das técnicas existentes a novos problemas, revela-se complexa. A motivação deste trabalho é contribuir para a mitigação deste problema, através de uma abordagem ”fundacional” dos algoritmos e da sua complexidade, ou seja, através da análise e classificação das estruturas que adicionam a vantagem quântica aos programas quânticos e, se possível, da concepção de técnicas formais que permitam ajudar na engenharia de novos algoritmos. Esta abordagem oferece o desafio de ter de gerir duas dimensões dos algoritmos quânticos, tradicionalmente estudadas em separado: complexidade e semântica. Assim, a abordagem deste trabalho baseou-se também nessas duas dimensões: por um lado, no estudo das estruturas que permitem a vantagem nos algoritmos quânticos, e por outro na concepção de uma lógica dinâmica para uma classe específica de programas quânticos: aqueles que são exprimíveis na linguagem QASM. Relativamente à parte mais algorítmica da contribuição, são propostas duas novas aplicações em dois campos ciêntificos diferentes: a simulação do transporte electrónico sem recurso a radiação no campo da biologia quântica; no campo da química quântica, o cálculo do estado fundamental da moléculas 𝐻2 e 𝐿𝑖𝐻 , sob acção de um campo elétrico forte (efeito de Stark). Ambas as aplicações foram implementadas e experimentadas num computador quântico real, o IBM Q. palavras-chave: biologia; computação quântica; química; lógica dinâmica vii 2 ABRIEFJOURNEYONQUANTUMCOMPUTATION I think I can safely say that nobody understands quantum mechanics. Richard P. Feynman, The Messenger Lectures, 1964, MIT. This chapter aims at revisiting the fundamental theoretical notions of quantum computation, as a background of the following chapters. We explore the fundamental mathematical concepts of quantum mechanics, the Hilbert space and density operators formalisms, as well as the distinctive characteristics of quantum mechanics, i.e. interference and entanglement . Arguably, are the main source of the socalled quantum advantage, playing a vital role in many quantum technologies, from communication and cryptography, to computation. We also explore the main quantum computation models and programming languages, including quantum circuits, and we provide a general perspective of the quantum complexity classes. 2.1 Quantum physics At the beginning of the 20 𝑡ℎ century, physics was thought to be complete, unifying all known physical forces and regimes, from the small to the very large. This, in despite of some small issues to solve, such as the divergences verified in the calculation of black-body radiation , and the incomplete understanding of the photoelectric effect. The solutions to these problems, led to the introduction of the of the concept of quantum, the smallest amount of a physical quantity, for example, the Planck constant 1 , which is the quantum of the orbital angular momentum. This allowed simultaneously the resolution of the divergences of the radiation of black bodies [ 290 ] as well as the full understanding of the photoelectric effect [ 141 ], for which Albert Einstein was awarded the Nobel prize in 1921. The latter, however, also included the radical idea of discretization of electromagnetic waves, whose quanta were later called photons . 1 A constant ℎ = 6.62607004 × 10−34𝑚2𝑘𝑔/𝑠 introduced by Max Planck, to fit the data of black body radiation experiments 4 2.2. The Hilbert space formulation 5 These findings along with several other ideas and experiments, such as the experimental validation of the wave-particle duality 2 and the new atomic models proposed by Bohr [ 72 ], shaped and gave experimental validation to a radically different theory from classical mechanics: the quantum theory. This body of ideas required a sound mathematical formulation, and this was initially achieved by two different and independent formulations: the Erwing Schrödinger’s formulation [ 319 ], based on waves ,and the Heisenberg-Jordan formulation [ 196 ], based on matrices . Both formulations were, later, shown to be equivalent by Schrödinger [ 318 ], and later, mathematically unified under the Hilbert space formalism by Von Neuman [ 276 ]. Both of such formalisms are canonical examples of a complex Hilbert space : Schrodinger’s formulation happens in the space 𝑙2 , the space of all square summable complex sequences, and the Heisenberg’s in the 𝐿2(ℝ3) space, the set of all square integrable complex functions of three real variables [14]. Another important formalism is the one of density matrices, also introduced by Von Neumann in 1927 [ 361 ], targeting at the representation of statistical ensembles of quantum states, useful to represent uncertainty in quantum states, e.g. fuzziness in preparation of quantum states. The Hilbert and density matrices formalisms, particularly the finite-dimensional ones, are the most commonly used ones in quantum computation. In the following sections we revisit the main principles of quantum mechanics through them. 2.2 The Hilbert space formulation Despite of the complexity of its consequences , quantum theory is defined by only four postulates, in addition to the algebraic laws governing a Hilbert space, and can be interpreted as state-based systems, where states are unity vectors and transitions correspond to unitary transformations between states, preserving energy conservation laws . Definition 2.2.1. Avectorspace 𝑉 over a field 𝔽 ,isasetsuchthatforevery 𝑥,𝑦∈𝑉 ,the following laws apply: 𝑥+𝑦∈𝑉; 0𝔽𝑥=0𝑉; 𝑥+𝑦=𝑦+𝑥; 1𝔽𝑥=𝑥; 0𝑉+𝑣=𝑥+0𝑉=𝑥; 𝛼(𝑥+𝑦)=𝛼𝑥+𝛼𝑦; 𝛼𝑥∈𝑉; (𝛼+𝛽)𝑥=𝛼𝑥+𝛽𝑥; Definition 2.2.2. ([ 109 ]) A Hilbert space is a vector space 𝐻 ,overthecomplexnumbers ℂ , with an internal product of type: ⟨−|−⟩∶𝐻×𝐻→ℂ. (1) 2 The idea that both waves and particles had similar behaviour, as proposed theoretically by Louie De Broglie [127], and experimentally demonstrated by Compton [113] 5 2.2. The Hilbert space formulation 6 In this operation, for all 𝜓,𝜙,𝜖∈𝐻and 𝜆∈ℂthe following algebraic rules apply: ⟨𝜓|𝜆𝜙+𝜖⟩=𝜆⟨𝜓|𝜙⟩+⟨𝜓|𝜖⟩; ⟨𝜆𝜓+𝜙|𝜖⟩=𝜆∗⟨𝜓|𝜖⟩+⟨𝜙|𝜖⟩; ⟨𝜓|𝜙⟩=(⟨𝜙∣𝜓⟩)∗; ⟨𝜓|𝜓⟩≥0for all 𝜓≠0 where (−)∗ is the conjugate of complex numbers. Additionally, Hilbert spaces of infinite dimensions must be Cauchy complete, i.e. for any (Cauchy) convergent sequence (𝑣𝑖)𝑖 of vectors in H, there exists 𝑣∈𝐻,suchthat||𝑣𝑖−𝑣||→0. 2.2.1 The state space The first postulate , defines the set of possible states in a quantum system: Postulate 1. The state space of an isolated physical system is the set of unitary vectors of an Hilbert space. We denote an Hilbert space by ℋ . In 1939, Paul Dirac proposed a notation to express vectors in the Hilbert space, the so-called Dirac notation [ 137 ]. Following this notation, a vector 𝑣∈ℋ , i.e. a state, is expressed as |Ψ⟩ . Every vector is generated by a basis, a subset of linearly independent vectors ∣𝑣1⟩,…,∣𝑣𝑛⟩ .Hence, in its general form, a vector 𝑣∈𝑉, can be expressed as a linear combination of elements of a basis, |Ψ⟩=∑ 𝑖𝛼𝑖∣𝑣𝑖⟩, (2) where ∣𝑣𝑖⟩ correspond to vectors of the basis, and 𝛼𝑖 are complex numbers corresponding to their amplitudes . In the matricial form ∣𝑣𝑖⟩corresponds to a column vector: |Ψ⟩=⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 𝛼1 𝛼2 ⋮ 𝛼3 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦.(3) A basis may be or not be complete, it is complete if the following condition holds, ∑ 𝑖𝛼𝑖∣𝑣𝑖⟩=0if 𝛼𝑖=0,for all i .(4) The dimension of ℋ is the maximum number of linearly independent vectors in ℋ . A further condition of valid states is unitarity , which is provided by normalization, i.e. the norm of all valid vectors is equal to 1 , |||𝑣⟩||=1,where||.||is given as: |||Ψ⟩||=√∑ 𝑖𝛼† 𝑖𝛼𝑖(5) 6 2.2. The Hilbert space formulation 7 where 𝛼𝑖 and 𝛼∗ 𝑖 are the amplitudes and their conjugates, respectively. Another relevant mathematical object in quantum mechanics is the bra ⟨Ψ|, which corresponds to the conjugate transpose of a vector ⟨Ψ|=|Ψ∗⟩𝑇=[𝛼∗ 1,𝛼∗ 2,…,𝛼∗ 𝑛]. (6) Conceptually, kets correspond to the states of a quantum system, and bras to the tests that can be performed over states. Finally, the internal product provides notion of distance between vectors. In the Dirac notation, for instance, an internal product is denoted as ⟨Ψ1∣Ψ2⟩and can be calculated as follows: ⟨Ψ1∣Ψ2⟩=[𝛼∗ 1,𝛼∗ 2,…,𝛼∗ 𝑛].⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 𝛼1 𝛼2 ⋮ 𝛼3 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦.(7) In other words, the internal product provides a measure of the likelihood that a test ⟨Ψ1∣ results successfully in a state ∣Ψ2⟩ . If the internal product ⟨Ψ1∣Ψ2⟩=0 ,then ⟨Ψ1∣ and ∣Ψ2⟩ are independent, i.e. orthogonal , while if the internal product is one, means they coincide. It can be easily observed that two kinds of states are possible in an Hilbert space : |Ψ⟩=∣𝑣𝑖⟩ corresponding to a single element of the basis, and |Ψ⟩=∑𝑖𝛼𝑖∣𝑣𝑖⟩ with 𝛼𝑖∈ℂ , corresponding to linear combinations of basis elements, both having fundamental differences in terms of physical interpretation. The former ones are called stationary states and correspond to states where the energy of the system is well known, i.e. with no uncertainty associated, corresponding to different quantum numbers , and being perfectly distinguishable. The latter ones correspond to the so-called superposition states , |Ψ⟩=𝜆1|Ψ1⟩+𝜆2|Ψ2⟩+…+𝜆𝑚|Ψ𝑚⟩, (8) where the energy is not well-defined, possessing an uncertainty associated. The proper physical understanding of such states is still under debate, due to their unobservability in the classical world. However in practice, according to the statistical interpretation of Quantum Mechanics originally proposed by M. Born [ 315 ], a measurement of such a quantum state can randomly yield one of the eigenvalues of its energy, 𝐸𝑛 , with the probabilities given by the squared amplitudes of the corresponding basis elements, |𝜆𝑛|2. 2.2.2 Interference A closer look to the possible state spaces in quantum mechanics, leads to the observation of one of its distinctive properties : interference. In general, a quantum state, can be written as 𝐴𝑒𝑖𝜃1|0⟩+𝐵𝑒𝑖𝜃2|1⟩≡𝜆|0⟩+𝛽|1⟩with |𝜆|2+|𝛽|2=1. (9) 7 2.2. The Hilbert space formulation 8 Interference concerns the non-independence of certain pairs of events in quantum mechanics, which can be verified, for instance, in the so-called double slit experiment [ 18 ]. This prevents that the probability of such events is given by the sum of their probability, i.e. 𝑃(𝐴∨𝐵)=𝑃(𝐴)+𝑃(𝐵) ,asiftheywere independent. Interference requires two or more events to be calculated: considering the state described in equation (9) , and that 𝐴⊔𝐵 corresponds to the quantum union of the two possible quantum events, i.e. to obtain 0or 1upon measurement, the probability of 𝐴⊔𝐵is calculated as follows: 𝑃(𝐴⊔𝐵)=(𝐴.𝑒𝑖𝜃1+𝐵.𝑒𝑖𝜃2)†(𝐴.𝑒𝑖𝜃1+𝐵.𝑒𝑖𝜃2)=|𝐴|2+|𝐵|2+𝐴.𝐵.𝑐𝑜𝑠(𝜃2−𝜃1). (10) It is easily observable that the probability depends on the phase difference between the two waves (eigenfunctions) of the stationary states, i.e. by the term 𝑐𝑜𝑠(𝜃2−𝜃1) . Formally, the actual calculation of interference is given by the difference between the probability of quantum union and the classical union: 𝐼(𝐴,𝐵)∶=𝑃(𝐴⊔𝐵)−𝑃(𝐴)−𝑃(𝐵) ∶=(𝐴.𝑒𝑖𝜃1+𝐵.𝑒𝑖𝜃2)(𝐴.𝑒𝑖𝜃1+𝐵.𝑒𝑖𝜃2)†−𝐴.𝑒𝑖𝜃1.(𝐴.𝑒𝜃1)†−𝐵.𝑒𝑖𝜃2.(𝐵.𝑒𝜃2)† ∶=𝐴.𝐵.𝑐𝑜𝑠(𝜃2−𝜃1) It can be easily concluded, that the events can only be treated as independent only when interference 𝐼(𝐴,𝐵) is 0 . On the other hand, when the interference factor is not 0 , the two waves corresponding to the events are said to be coherent . There is always interference in superposition states, i.e. eigenwaves of the system are always in coherence, and the probability calculations the only depend on the phase differences (local phases) between them. The common denominator between all phases is the so-called global phase , and while essential to the composition of quantum systems, does not have any observational relevance, i.e. it is not relevant to probabilistic calculations. In other words, it can be stated that 𝜆|Ψ⟩≅|Ψ⟩,with 𝜆∈ℂ (11) where 𝜆 is a global phase factor, i.e. it affects the whole system, and ≅ means observational equivalence and |Ψ⟩is an arbitrary state. Interference is well known to happen with waves in classical physics, but in quantum mechanics it is known to happen with photons , but also with particles, e.g. electrons, i.e. e providing evidence that also matter can behave as waves, in agreement with the hypothesis wave-particle duality . In fact, interference has also shown to be existent in much larger bodies at mesoscopic scale, such as in large molecules [ 168 ], but not at macroscopic level. 8 2.2. The Hilbert space formulation 9 This was shown in quantum mechanics resorting to different devices and methods, such as slit experiments , observation of electron diffraction or interferometers of many kinds. A paradigmatic example of interferometers is the so-called Mach-Zender interferometer, depicted in figure 1, initially targeted to photons. Figure 1: The Mach-Zender interferometer, is a optical device where, upon the application of a beam splitter, photons can travel through two possible paths, until reaching one of two detectors. Such paths can be transversed with equal probability. The detection of the photon in the first detector corresponds to the basis state |0⟩ and in the second detector as |1⟩.Adaptedfrom[133]. In the experiments with the Mach-Zender interferometer, the end states read as follows: 1 √2(|0⟩+|1⟩) (12) with 1/2 probability of obtaining 1 or 0 . However, the probability can be controlled by the phase difference, which establishes the difference between a purely random distribution, where there is no control over the distribution and it is constant throughout time, and the distributions of quantum mechanics, by-product of coherence between waves, controllable, and oscillatory throughout the action of Hamiltonian. The loss of coherence, which can happen through many processes, causes the decay of a quantum superposition state exhibiting coherence to a classical probabilistic state. 2.2.3 Unitary evolution The evolution of quantum mechanical systems has to be reversible , due to the laws of energy conservation, and preserve linearity. Therefore, the evolution in a quantum system is given by a unitary operator 𝑈, ∣Ψ𝑡+𝛿𝑡⟩=𝑈∣Ψ𝑡⟩, (13) which preserves linearity: 9 2.2. The Hilbert space formulation 10 𝑈⎛ ⎜ ⎝∑ 𝑖𝛼∣𝑣𝑖⟩⎞ ⎟ ⎠=∑ 𝑖𝛼𝑖𝑈(∣𝑣𝑖⟩). (14) Postulate 2. The evolution of a closed system is described by a unitary transformation i.e. an operator 𝑈such that 𝑈.𝑈−1 =𝐼. A corollary of these postulates is that the temporal evolution of a quantum mechanical system is given by the Schrödinger equation [ 318 ], which is the cornerstone of Schrödinger’s formulation of quantum mechanics. Postulate 2.1. The time evolution of the state of a closed quantum system is described by the Schrödinger equation, 𝑖~𝜕 𝜕𝑡|Ψ(𝑡)⟩=𝐻|Ψ(𝑡)⟩. (15) The Schrödinger’s formulation of quantum mechanics, is centred at the action of the Hamiltonian operator over quantum systems, 𝐻=𝑇+𝑉 , 𝑇 being the kinetic energy of the constituent particles and 𝑉 the potential energy of all interactions and fields in the system, both internal and external, whose action yields the total energy of a system if in a stationary state, 𝐻|Ψ⟩=𝐸|Ψ⟩. (16) Notation |Ψ(𝑡)⟩ denotes the system’s wavefunction (WF), which represents the timed evolution of an eigenstate |Ψ⟩ , resulting from the action of an Hamiltonian operator. The set of WF’s correspond to all physically meaningful solutions of the Schrödinger equation, which are mutually orthogonal. Usually, there are several possible solutions to the equation, corresponding to different values of the energy (energy levels or eigenvalues, 𝐸𝑛 ), which are discrete for a confined (or bound) physical system. The wavefunction |Ψ⟩ , may also depend on other arguments (such as spatial coordinates and spin components) according to the representation used. In section 4.3,onchapter4, this formalism is further explored, when addressing a problem of simulation of a many-body system for quantum chemistry. 2.2.4 Observables A quantum state, i.e. a wavefunction , carries information about all the observations that can be made, by characterizing their probability distribution. In quantum mechanics one may be interested in an infinity of types of observations, e.g. one can be interested in measuring the position of a particle, or its velocity. Observables in quantum mechanics, are operators with a special status, known as Hermitian linear operators which conjugate transpose (𝐴∗) equals itself, 𝐴∗=𝐴. (17) 10 2.2. The Hilbert space formulation 11 It can be easily verified that such operators possess real eigenvalues, and indeed correspond to those who are empirically meaningful, as in the classical world all physical quantities are real values. A difference between classical and quantum mechanics is that observables, in general, do not commute ,i.e. the commutator given by [𝐴,𝐵]=𝐴𝐵−𝐵𝐴, (18) is not necessarily 0 for all pairs of observables. The most well-known example of this is the non-commutativity of position and momentum operators, which constitute the so-called Heisenberg uncertainty principle .The commutator, basically allows the evaluation of the effect of the order of application of the observations, i.e. if the commutator is different from zero, i.e. [𝐴,𝐵]≠0, (19) the observations interfere with each other and it is impossible to estimate with arbitrary accuracy both observables at the same time, meaning that observables are correlated, and even more, that it is impossible to find separable distributions for the statistics of both observables and assign definite values to both of them [ 73 ]. On the other hand, if (19) is 0, then observables are independent, and hence, it is possible to estimate both observables with arbitrary accuracy. Einstein defined this impossibility of assigning a definite value to every observable of a quantum system in a given instant as some sort of anti-realism , stating that quantum mechanics should be incomplete. This, however, was proven experimentally several times, and, is an important ingredient of several quantum technologies. Niels Bohr stated that this is a very powerful assumption, which invalidates the calculation of joint probabilities for events that do not commute. 2.2.5 Measurements The postulates enumerated so far, describe the possible states connected by transitions in quantum mechanics, which include a special kind of states, the superposition states . Such states, cannot be observed in the classical world, i.e. objects at macroscale can only be observed in a stationary and not in a superposition of states, although they have been observed at micro and mesoscopic scales. This disparity between classical and quantum worlds is known as the so-called measurement problem [ 375 ], for which multiple possible theories have been developed, unfortunately, undistinguishable from the experimental point of view with current technology. However, the process of causing the collapse of a superposition state to a classical state is known as measurement and measurements have a stochastic nature in quantum mechanics. 11 2.2. The Hilbert space formulation 12 Postulate 3. Measurements cause the collapse of quantum states into classical states. Mathematically, they correspond to projection operators: ∣𝑀𝑚⟩⟨𝑀𝑚∣ , where 𝑚 is the desired outcome. The calculation of the resulting state after a measurement over |Ψ⟩is given by 𝑀𝑚|Ψ⟩ √⟨Ψ|𝑀† 𝑚𝑀𝑚|Ψ⟩,(20) and the probability of obtaining a specific measurement by 𝑝(𝑚)=√⟨Ψ|𝑀† 𝑚𝑀𝑚|Ψ⟩.(21) The set of measurement operators, for all possible outcomes, respects the condition that ∑𝑚𝑀† 𝑚𝑀𝑚= 𝐼. Each measurement operator corresponds to only one possible outcome. Example 2.2.1. Consider state ∣𝜓⟩=𝑎|0⟩+𝑏|1⟩ and measurements 𝑀0=|0⟩⟨0| , 𝑀1=|1⟩⟨1| ; then, 𝑝(0)=⟨𝜓∣𝑀† 0𝑀0∣𝜓⟩=⟨𝜓∣𝑀0∣𝜓⟩=|𝑎|2(22) 𝑀0∣𝜓⟩ |𝑎| =𝑎 |𝑎||0⟩ (23) 𝑀1∣𝜓⟩ |𝑏| =𝑏 |𝑏||1⟩ (24) 2.2.6 Combining quantum systems In quantum mechanics there is the possibility of combining smaller quantum systems can be combined to obtain larger one. The last postulate of quantum mechanics corresponds exactly to this: Postulate 4. The state space of a composite physical system corresponds to the tensor product of the state spaces of the component physical systems. A tensor is operator ⊗∶ℂ𝑛 1×ℂ𝑛 2→ℂ𝑛1+𝑛2,(25) and its calculation for two vectors spaces corresponds to the following linear operation: 𝑇=𝑛 ∑ 𝑖=1 𝑛 ∑ 𝑗=1 (𝑣𝑖𝑤𝑗)(𝑒𝑖⊗𝑓𝑗)(26) 12 2.3. The density matrix formalism 13 ⎡ ⎢ ⎣𝑎1,1 𝑎1,2 𝑎2,1 𝑎2,2⎤ ⎥ ⎦⊗⎡ ⎢ ⎣𝑏1,1 𝑏1,2 𝑏2,1 𝑏2,2⎤ ⎥ ⎦=⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 𝑎1,1 ⎡ ⎢ ⎣𝑏1,1 𝑏1,2 𝑏2,1 𝑏2,2⎤ ⎥ ⎦𝑎1,2 ⎡ ⎢ ⎣𝑏1,1 𝑏1,2 𝑏2,1 𝑏2,2⎤ ⎥ ⎦ 𝑎2,1 ⎡ ⎢ ⎣𝑏1,1 𝑏1,2 𝑏2,1 𝑏2,2⎤ ⎥ ⎦𝑎2,2 ⎡ ⎢ ⎣𝑏1,1 𝑏1,2 𝑏2,1 𝑏2,2⎤ ⎥ ⎦ ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ (27) =⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 𝑎1,1 ∗𝑏1,1 𝑎1,1 ∗𝑏1,2 𝑎1,2 ∗𝑏1,1 𝑎1,2 ∗𝑏1,2 𝑎1,1 ∗𝑏2,1 𝑎1,1 ∗𝑏2,2 𝑎1,2 ∗𝑏2,1 𝑎1,2 ∗𝑏2,2 𝑎2,1 ∗𝑏1,1 𝑎2,1 ∗𝑏1,2 𝑎2,2 ∗𝑏1,1 𝑎1,2 ∗𝑏1,2 𝑎2,1 ∗𝑏2,1 𝑎2,1 ∗𝑏2,2 𝑎2,2 ∗𝑏2,1 𝑎1,2 ∗𝑏2,2 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ (28) 2.3 The density matrix formalism Density matrices were introduced by Von Neumann in 1927 to represent mixtures of physical systems [ 360 ], i.e. the so-called mixed states , which correspond to stochastic (classical probabilisties) combinations of quantum systems. This representation is useful in a plethora of situations of quantum mechanics, but the most obvious example happens there is uncertainty over the preparation of quantum states. The latter is a common phenomenon in quantum mechanics. Following equation (6) , a quantum state can be written as: |Ψ⟩=∑ 𝑖𝛼𝑖∣Ψ𝑖⟩(29) The density operator can be obtained by the projection of a state over itself, which reads as 𝜌=|Ψ⟩⟨Ψ|,(30) which results in a matrix of the following type: 𝜌=⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 𝛼1𝛼† 1𝛼2𝛼† 1…𝛼 𝑛𝛼† 1 𝛼1𝛼† 2𝛼2𝛼† 2…𝛼 𝑛𝛼† 2 ⋮⋮⋱⋮ 𝛼1𝛼† 𝑛……𝛼 𝑛𝛼† 𝑛 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠.(31) In this matrix lines correspond to kets, ∣Ψ𝑖⟩ , and columns to bras, ⟨Ψ𝑗∣ , and each position of the matrix contains the correspondent eigenvalue of the projection ∣Ψ𝑖⟩⟨Ψ𝑗∣ , the multiplication of the 𝛼𝑖 for ∣Ψ𝑖⟩ for its conjugate 𝛼† 𝑖. Fue to the spectral decomposition theorems, the matrix operator can be written as ∑ 𝑖(𝛼† 𝑖∗𝛼𝑖)∣Ψ𝑖⟩⟨Ψ𝑖∣.(32) 13 2.3. The density matrix formalism 20 Figure 2:Local operations and classical communication operator definition. Adapted from [291] However, this measure does not behave in mixed-state scenarios, due to the existence of processes able to transform them in pure states and vice-versa , i.e. processes of purification [ 356 ]. Therefore, a more general definition of measure of entanglement is necessary, which is given, for instance, as 𝐸(𝜎)∶=min𝑝∈𝒟𝒟(𝜎||𝜌), (54) where 𝐷 is a measure of distance between two matrices, 𝜎 is an entangled state subject to purification , 𝜌 is a classical state and 𝒟 is the set of convex states. Any valid measure of entanglement, shall obey to the following conditions: • for separable states 𝐸(𝜎) = 0 , i.e. the state is not entangled, and cannot be purified to an entanglement state; • any measure of entanglement remains unchanged under the action of locally unitary operations5; • any measure 𝐸(𝜎) cannot be increased by local operations, classical communication and subselection (see figure 2)𝐸(𝜎)≥∑ 𝑖𝑝𝑖𝐸(𝜎𝑖). (55) There are many measures which respects these conditions, for instance: relative entropy, entanglement of formation, or entanglement of distillation, or Schmidt rank [ 143 ]. Nowadays the quantification of entanglement is very relevant, specially in many-body systems, which, however, has revealed itself as challenging [354,317,22]. 5 Local unitary operations, are operations which can be written in the form 𝑈𝐴⊗𝑈 𝐵(note that the CNOT gate is not) 20 2.3. The density matrix formalism 21 2.3.4 Decoherence The nature of the wave collapse in quantum mechanics, defined by the so-called measurement problem, is still an unsolved problem, and subject to intense debate in many areas of knowledge. Decoherence processes, introduced by Zeh in 1970 [ 384 ], while not solving the measurement problem, provide a very good explanation for the apparent decay of pure (quantum) states to mixed (quantum) states observable at macroscopic level [387]. As discussed in section 2.3.1, every mixed state can be purified into an e ntangled pure state, i.e. a mixed state is always part of a pure state of larger dimension. The process of decoherence is somehow a purification process , where due to the introduction of entanglement between a closed system ℋ𝑠 and its environment ℋ𝑒, ℋ𝑠⊗ℋ𝑒, errors are introduced into the state ℋ𝑠 , which then decays to a (classical) mixed state. Unfortunately, this process happens in an unpredictable and uncontrollable way, and the incapacity of controlling such system-environment interactions, has been the major problem in the conception of quantum computers (more on this on section 2.4). Nonetheless, this type of systems, interacting with their environments (also known as baths ), constitutes an area of study on their own: open quantum systems . While the methods of this area are limited, and only able to deal to small systems, very far from physically meaningful systems for decoherence processes, they provide useful insights in many applications, for instance in biology (see more on this on section 3.3). Decoherent processes The decoherence observed in the large quantum systems, for instance in quantum technology, is an uncontrollable and unpredictable process, exactly because the number of quantum interactions is completely intractable for classical computers, and arguably, will still be too hard even for quantum computers. However, the effects such interactions have in closed systems, due to action of the bath , are well-known, which simplifies the conception of strategies to compensate them, and can be divided into three categories [83]: •amplitude damping; • dephasing; •depolarization. Hereby, we further describe each of these processes. 21 2.3. The density matrix formalism 22 •Amplitude damping interactions encompass the processes that cause loss of the amplitude of one or more system’s eigenstates . The spontaneous emission of a photon from the system to the environment from a two-level atom is an example of this kind of processes, which can cause the decay of an excited state to its ground state [277]. •Phase damping, or dephasing processes cause the decay of the off-diagonal terms from the system’s density matrix, over time, down to zero, removing superpositions , i.e. coherences, of the system state. An example of this process can be observed by the interaction of a two-level system with its environment, letting the initial state of the latter system be given as ∣𝜓⟩=𝑎|0⟩+𝑏|1⟩ . Coupling this system with an environment, and modelling the environmental effect as a Gaussian distribution of relative phases 𝜃 , with zero mean value and variance 2𝜆 , gives raise to the following mixed state [179]: 𝜌=⎛ ⎜ ⎝|𝑎|2𝑎𝑏∗𝑒−𝜆 𝑏𝑎∗𝑒−𝜆 |𝑏|2⎞ ⎟ ⎠.(56) It is easily observable, that the off-diagonal elements decay exponentially to 0 as 𝜆 increases, and as the variance 𝜆 is proportional to the time variable, the coherence in the initial two-level system decays over time [ 277 ], ultimately, removing any coherence from the system, turning the original coherent probability distribution, into a non-coherent, classical, one. These processes conserve the energy of the system, contrary to what happens with amplitude damping. • The Depolarization changes the system state to a mixed state, with a probability 𝑃 of another pure state and the probability (1−𝑃) of the initial state of the system, and it can be thought as a combination of the other two types of decoherence [1]. 22 2.4. Quantum Computing 23 2.4 Quantum computing Quantum computation is a scientific discipline born in the eightie’s, following the idea proposed Feynman in 1982 [ 151 ] to employ quantum mechanical systems in the simulation of quantum mechanical systems themselves. This process, nowadays known as quantum simulation, as already foreseen by Feynman, yields a huge (exponential) computational advantage in some quantum simulations. This was the first idea leading to quantum computation, which was followed by the first formal computational models introduced by Benioff [ 53 , 54 ], based on Hamiltonian evolution and being continuous . Later, in 1985, David Deutsch [ 130 ] provided a more general quantum universal computing model, the so-called quantum Turing machines, as an extension of their classical counterparts. Borrowing notions from the field of reversible computing, he introduced the notion of a quantum circuit. These are, still today, the fundamental notions of the quantum computing models, from which originated a flurry of theoretical work, encompassing possible implementations, programming languages and formal methods to deal with them. From the implementation point of view the hardest challenge is decoherence [ 82 ], the conservation of superposition and entanglement in quantum states, against the errors caused by the environmental interaction. To solve this problem, many physical architectures have been developed, as well as alternative computing models and error correction strategies. However, it cannot be said that this problem has been overcome and that quantum computing is a reality. This section is devoted to the discussion of the main concepts underlying quantum computation, as well as the abstract models for quantum computers, from of a state-based perspective, as seen in by Deutsch [130]. 2.4.1 The state space: finite vs infinite dimension The state space for a quantum computation is given by the set of unitary vectors (vectors of norm 1) in a Hilbert space , which can be of finite or infinite dimension. Most of computer models, fall in the former category, however the latter have also shown to be relevant, for instance, in quantum computing with continuous variables [ 288 , 368 ], or for dealing with systems whose number of particles in the system changes throughout the computational process. Nonetheless, the most common form of quantum computation resorts to a notion of qubit , 2-dimensional Hilbert spaces, ℋ2 , with {|0⟩,|1⟩} as basis, i.e. the so-called computational basis, from which spaces of arbitrary dimension can be built. The state space of a qubit reads as follows: ∣𝜓⟩=𝛼|0⟩+𝛽|1⟩such that |𝛼|2+|𝛽|2=1;𝜆∣𝜓⟩=∣𝜓⟩,𝜆∈ℂ (57) 23 2.4. Quantum Computing 24 where 𝜆 is a global phase and does not possess any observational effects . Such state space possesses a geometric interpretation given by the Bloch sphere [ 277 ], mostly useful to understand single-qubit unitary transformations, where a state is described in polar coordinates by two angles in a three-dimensional space, as presented in figure 3. Figure 3:Bloch sphere, adapted from [277]. The state spaces of qubits can be combined with the tensor product ⊗ to larger quantum systems. For a 𝑛-qubit system, the set of possible states is 𝑛−1 ⨂ 𝑖=0 ℋ2 𝑖.(58) For instance, the state space of a two-dimensional space, is ∣𝜓⟩=𝛼|00⟩+𝛽|01⟩+𝛾|10⟩+𝜆|11⟩, (59) for 𝛼,𝛽,𝛾,𝜆 such that |𝛼|2+|𝛽|2+|𝛾|2+|𝜆|2=1 . Furthermore, in a purely abstract setting, one can group a set of qubits into a register: register with l qubits ⏞⏞⏞⏞⏞ 𝑞1⊗⋯⊗𝑞𝑙⊗register with m qubits ⏞⏞⏞⏞⏞⏞⏞ 𝑞𝑙+1 ⊗⋯𝑞𝑚+𝑙 ⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟ Aggregation with l+m qubits . A set of registers defines the quantum computer’s memory , whose semantics is given by the set of all possible quantum states. An important property of a quantum memory is that it cannot be replicated :as stated in the no cloning theorem , proven by Wooters and Zurek in 1982 [ 377 ], it is not possible to make an exact copy of a quantum state. This is a simple consequence of linearity, but significantly changes the way quantum programs are built. 2.4.2 Transitions between states: unitarity and time In quantum mechanics, transitions preserve unity of states and are unitary, hence, programs are given by the class of such linear unitary operators ( 𝑈.𝑈†=𝐼 ) in a Hilbert space. For a quantum system with 𝑛 qubits the signature of the transition operators reads as follows: 24 2.4. Quantum Computing 25 𝑈⊗𝑛 ∶ℋ2⊗𝑛 →ℋ2⊗𝑛 A particular relevant class of unitary operators used in quantum computation is that of Hamiltonian evolution operators, i.e. operators that characterize the evolution of an Hamiltonian, which possess the form 𝑒𝑖𝐻𝑡 ,where 𝐻 is an Hermitian operator. Many computer models correspond to actual analog quantum simulators, i.e. quantum systems, which under appropriate preparation processes, are sufficiently similar to systems to be simulated , and hence suitable to be used as quantum simulators . Timed evolution In quantum mechanics, non-relativistic quantum systems, are captured under the Hamiltonian formalism, where the evolution of a quantum system, along a time 𝑡 is given by the exponentiation of its Hamiltonian operator, given as: |Ψ⟩=𝑒𝑖𝐻𝑡/~|0⟩ (60) The dimension of the Hamiltonian operator is exponential in terms of the size of the basis of the system it operates, i.e. for a system with 𝑁qubits, the dimension of the matrix is exponential 2𝑁×2𝑁. As a result, the dimension of the evolution operator grows very quickly, which makes the calculations intractable even for systems with a small number of particles: procedures such as matrix multiplication , or diagonalization , vital in the calculation of the evolution, or estimation of eigenvalues , while efficient in terms of matrices dimension (complexity ∼𝐷3 ,where 𝐷 is system’s dimension), become 2− exponential ( 𝐷2𝑁3 )for 𝑁 particle systems. However, as suggested by Feynman, quantum mechanics yields a huge advantage, i.e. an exponential one, in the simulation of the evolution operators if the evolution operator can be efficiently approximated (more on this on chapter 3). The circuit model Following to the discovery of quantum Turing machines, and based on the theory of Boolean and reversible circuits, Deutsch proposed the notion of quantum circuits: acyclic graphs connecting qubits, used as inputs, and sequences of unitary operators acting as transformations, mapping them into outputs. Quantum circuits have a specific notation, where qubits are represented by wires, and transformations by boxes, as in the following example: 25 2.4. Quantum Computing 26 𝑞1 𝑈1𝑈2 𝑞2⋯⋯ ⋯ ⋯⋯⋯⋯⋯ 𝑞𝑛𝑈3 , where 𝑈1,𝑈2 and 𝑈3 are unitary transformations and 𝑞1 up to 𝑞𝑛 are input qubits. Quantum circuits are analogous to Boolean circuits: qubits are the quantum counterparts of classical bits, quantum gates are the counterpart of Boolean gates, and quantum circuits are the counterpart of Boolean circuits. Similarly to the classical case, Yao [ 379 ] has shown that families of quantum circuits can simulate quantum Turing machines, implying that they provide a complete quantum computational model. Furthermore, it has also been shown in the so-called Solovay-Kitaev theorem that any unitary operation can be approximated by a set of universal quantum gates [226]. Nowadays, quantum circuits are the useful components of real world quantum programs. Hence, it becomes specially important to identify minimal sets of gates from which all possible quantum circuits can be generated, and to find automatic means to approximate generalized unitary operators by them. In this area, one can observe that unitary operators, are fundamentally reversible operators , and, hence, some techniques can be inherited from the fields of low power and adiabatic electronics [ 129 ], i.e. subfield of electronics where electronic circuits have no dissipation of energy (and information) to the environment, which can be achieved, for instance, by not using electronic resistances . Examples of Boolean universal reversible gates are the Fredkin and Toffoli gates (presented in table 1), which were shown to be (the first) universal gates also in quantum computation [131]. Later, it was shown that the set of all single-quantum quantum gates (some of them are presented in table 2), along with a controlled NOT gate, were universal [ 46 ]. Another universal gate set is given in the case of many individual two-qubit quantum gates, as shown by DiVicenzo in [ 139 ]. In fact, this type of results has been shown to a wide class of sets of unitary quantum gates [248]. A well-known set of universal quantum gates is formed by the single-qubit gates 𝑋 , 𝐻 , and the two-qubit gate 𝐶𝑁𝑂𝑇 (presented in table 3), and another set, named standard basis , is given by the set of gates {𝐻,𝑇,𝐶𝑁𝑂𝑇} . The latter is particularly important because it is very close to the so-called called Clifford circuits [ 264 ], which replaces 𝑇 by the phase gate , 𝑃=𝑇2 .The Clifford circuits , are efficiently simulatable by classical computer, bearing no quantum advantage, according to Gottesman-Knill theorem [ 7 ], hence the presence of the 𝑇gate is a syntactic indicator of quantum advantage. However, the base given by the Clifford plus T gate circuits is universal, and there is a wide range of literature about the exact synthesis of unitaries [ 169 ], for instance, efficient classical algorithms to approximate unitaries with entries in the ℤ[1 √2,𝑖] ring [ 229 ]. Nonetheless, not all operators can be approximated efficiently with these gates and a more accurate description the possible approximations is 26 2.4. Quantum Computing 27 Gate Circuit form Matrix form Toffoli Gate (CCNOT Gate) • • ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 10000000 01000000 00100000 00010000 00001000 00000100 00000001 00000010 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ Fredkin gate • × × ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 10000000 01000000 00100000 00010000 00001000 00000010 00000100 00000001 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ Table 1: The original three-qubit, Fredkin and Toffoli, gates. Gate Circuit form Matrix form 𝑅(𝜙) 𝑅(𝜙) [10 0𝑒 −𝑖𝜙] X𝑋[01 10 ] Z𝑍[10 0 −1] H𝐻1 √2[11 1 −1] Y𝑌[0 −𝑖 𝑖0 ] S𝑆[10 0𝑒 𝑖𝜋 2] T𝑇[10 0𝑒 𝑖𝜋 4] Table 2:Single qubit gates. given in [ 23 ]. More general ways of approximating unitaries, are based on the theory of matrix factorization. Relevant works on the subject are given, for instance, in [119], or [353,245]. 27 2.4. Quantum Computing 28 Gate Circuit form Matrix form CNOT •[𝐼0 0𝑋 ]≡⎡ ⎢ ⎢ ⎢ ⎣ 1000 0100 0001 0010 ⎤ ⎥ ⎥ ⎥ ⎦ CU (Controlled unitary) • 𝑈[𝐼0 0𝑈 ] SWAP × ×⎡ ⎢ ⎢ ⎢ ⎣ 1000 0010 0100 0001 ⎤ ⎥ ⎥ ⎥ ⎦ Table 3:Two-qubit quantum gates. 2.4.3 Acceptance states In previous sections it were discussed two of the components for a state-based notion of computation, states and transitions: states are given by Hilbert spaces of qubits involved in the computation and valid transitions between states correspond to unitary transformations. The third component is the one of acceptance state, which in the quantum context, corresponds states where the correct output can be obtained upon measurement, with a probability that allows statistical distinguishability from the wrong one. Measurements are mathematically captured by projection operators 𝑃𝑟𝑜𝑗𝜑,𝑜𝑟∣𝜑⟩⟨𝜑∣ , as discussed in section 2.3.2.In the language of quantum circuits, a measurement is depicted as follows: . A very simple example of a circuit including a measurement is given by |0⟩𝐻, which aims at creating a quantum coin , i.e. a qubit in the superposition 1 √2(|0⟩+|1⟩) , which upon measurement will randomly yield either |0⟩or |1⟩, with 0.5of probability (because (1 √2)2=0.5). 28 2.4. Quantum Computing 29 2.4.4 Semantics of quantum programming languages In the previous sections, quantum computation was introduced from the perspective of a (state-based) operational semantic model. In this section, we shift attention to programming, focusing on the essentials of quantum programming languages and denotational semantics, in order to obtain a clearer connection between the programming instructions, and the corresponding physical processes. Broadly speaking, a quantum programming language is composed of two main parts: the control component and the actions. Actions are, in general, measurements or unitary operations. The control statements, which aim coordinating the execution of actions, are the usual of programming languages: conditions , loops and recursion . The control component can be of two types, classical or quantum. The former relies using only on classical variables , i.e. variables in quantum stationary states, in control instructions. The latter allows variables in quantum ( superposition ) states, leading to the ”strange” idea of superposition of fluxes (programs), which under certain conditions becomes unphysical , i.e. transitions may become non-completely positive, when measurements are involved. Every quantum programming language fall into one of these schemes. In this section, we briefly discuss these families of programming languages, their features, associated physical effects and semantics. Quantum data with classical control The main paradigm in real-world quantum computation is the so-called quantum data with classical control , a term firstly coined by Knill in 1996 [ 230 ]. This covers all programming languages involving unitary operations, to be executed in a quantum device, and classical control instructions, to be executed by a classical agent that controls the quantum device, as depicted in figure 4. Figure 4: Quantum data with classical control. In this setting, the execution processes in the quantum device are only a small part of the whole computational process. The latter, in the classical setting, can involve: • creation and destruction of classical and quantum bits; • generation of circuits (see section 2.4.2) to be executed in the quantum device; • controlled execution of quantum circuits using classical variables; 29 2.5. Quantum Complexity 36 Probabilistic Polynomial time, Quantum Interactive Polynomial Time and PSPACE The probabilistic polynomial time complexity class encompasses all problems that are solvable probabilistically, i.e. that the correct answer can be obtained with more than 1/2 of probability, and it is known to contain the class QMA. The Quantum Interactive Polynomial (QIP) is the complexity class that contains all problems that can be solved by a proof-verifier protocol, where the prover has infinite computational power, the verifier has access to a quantum computer, and both can exchange an unbounded number of messages. The PSPACE class is defined by all problems that can be solved with polynomial resources except for time and has shown to be equivalent to QIP [366,207]. 2.5.2 Quantum advantage The algorithmic resources presented in table 6, do not provide any insight on which the structures of quantum theory contribute to the quantum advantage , i.e. the structures that make that some problems that fall in the BQP class being intractable in classical computing, have efficient algorithms in quantum computers. The analysis of such structures brings insight on how to build new quantum algorithms. One may think that the main advantage of quantum computers resides in the so-called ”quantum parallelism”, which is partially true. The actual resources available in quantum theory that provide quantum advantage are precisely the features of quantum mechanics that are not available in classical mechanics: entanglement and interference. The former is, as it is well-known, the most distinguishable feature of quantum mechanics and essential to guarantee the existence of states with n-ary qubits, as otherwise only single qubit states would be achievable. It is also the hardest resource to obtain in practice, and the current attempts with short-term devices are basically about obtaining higher degrees of entanglement .However, while entanglement provides the notion of parallelism, the differentiating factor for quantum algorithms is interference , as argued, for instance, in the works of Fortnow and Lloyd [ 155 , 250 ]. Further evidence is also provided in the studies made in [ 81 ], or [ 336 ], where interference of quantum algorithms is measured and compared, and it is concluded that interference is more intense in Shor algorithm [ 329 ], than in the Grover one [178], the former associated with an exponential advantage and the latter with a quadratic advantage . Hence, interference and entanglement are the essential resources of the quantum advantage, where they play a complementary role, entanglement being the basic component, and interference the differentiating component. An interesting discussion in quantum computation, regards the computational power of variations of quantum mechanics, which is not a purely philosophical discussion, as the hypothesis that a theory of quantum gravity fits in some sort of extension of quantum mechanics is real. Two main lines of work shall be considered in this field. One considers variations on the interference patterns of quantum mechanics, 36 2.6. Summary 37 which yields a hierarchy of different quantum theories [ 335 , 120 , 240 ]. Another one deals with non-linear quantum theories. The latter were considered to solve the issues of quantum mechanics [ 375 ], but that bring problems on their own [ 65 , 370 , 369 ], and have a strong relationship with the existence of closed timelike curves , which besides bringing a great computational advantage, pose physical problems under certain conditions [ 194 ]. In 1992 David Deutsch proposed a model for quantum mechanics, which, simultaneously, allows the action of curved spacetimes possessing closed time-like curves (D-CTC’s), and is free of paradoxes and superluminal signaling [ 132 ]. This model is based on the additional requirement of self-consistency of the closed time-like curves, namely, only the ones having fixed points are considered. In this model it is possible to do perfect cloning of quantum states and distinguish efficiently any non-orthogonal states [ 85 ]. Exactly because of this, there is a significant quantum advantage, implying efficient solutions for all problems in PSPACE [ 9 , 35 ]. This model is, however, equivalent to a classical theory, and quantum effects are irrelevant for the computation [ 8 ], being no more powerful than a classical computer with access to the same timelike curves [ 24 ]. Following these lines, based on a model of closed timelike curves using teleportation and post-selection (P-CTC’s) [ 252 ], Aaronson has shown that quantum computers could solve all problems of the class PP, and hence of the class NP [4], less powerful than D-CTC’s. The calculation of properties such as entanglement and interference are not compositional and may be as complex as conducting the whole simulation of the quantum process, and hence, very complex from the computational perspective. The development of easier measurements to detect entanglement and quantum advantage is now a very wide and fruitful line of research, which ranges from complex metrics to trivial properties that can be verified at the syntax level, in the definition of quantum circuits. Some measures that can be applied, are for instance, Schmidt rank [ 359 ], factorization into a product state of small subsystem [ 214 ], factorization into Clifford gates [ 176 ], existence of matchgates [ 348 ], small tree width [ 213 , 262 ] or non-negative Wigner representation [ 357 , 261 ]. Furthermore, it is also worth looking into the field of descriptive complexity , which aims at defining the characteristic languages of complexity classes, , ultimately guaranteeing that a well-formed program in the syntax, is automatically within a certain complexity class. This was, for instance achieved in the work of Dal Lago et al. [ 121 ], where a characteristic lambda-calculus of the BQP class (see section 2.5.1) was obtained. 2.6 Summary In this chapter it were reviewed the Hilbert space and density matrices formalism for expressing quantum theory as well as the latter’s distinctive properties, such as interference and entanglement, and how they are crucial to quantum information and computation. It also introduced the fundamentals of quantum computation, such as the circuit model, and other well-known quantum computational models, the semantics of quantum programming languages, and complexity. Some conclusions can be made in this section: 37 2.6. Summary 38 • Entanglement and interference are the most distinctive features of quantum mechanics. • They are also the essential components of quantum advantage, where they do play a complementary role. There is also a wide range of methods to quantify them. • The computational processes allowed in quantum mechanics can be soundly captured, compositionally, in a wide range of quantum programming languages. • A multitude of methods has been conceived to preserve quantum advantage against environmental effects, from quantum simulators, measurement-based computers, or recently, variational methods. • Variations of quantum mechanics may yield computational advantage but may also raise other issues from the physics point of view. 38 3 ON EFFICIENT QUANTUM ALGORITHMS The number of existent quantum algorithms is now significantly bigger than in the early days of quantum computation, following the successes of Grover, Shor, or Simon algorithms. The range of applications has also extended, from machine learning, or finance, to the simulation of a wide class of physical systems. However, the progress on the development of efficient quantum algorithms, bearing the so-called exponential advantage to classical ones, has been slower than expected. However, the main structures and building blocks of the algorithms in this situation are short in number and very well studied, which suggest that a way of trying to find new quantum algorithms is to characterize these structures and extend them to new applications. In this chapter, following this idea, we characterize the main quantum efficient algorithms, that is the ones within BQP class, and the structures behind them. We also explore a quantum simulation of the energy transport in a small photosynthetic system, i.e. an example from the biology domain, as an instance of a system that can be efficiently handled by quantum computers: it is driven by a local-Hamiltonian. The work was published in co-authorship with Jose Guimarães et al. [179]. 3.1 The Bounded Quantum Probability class The Bounded quantum probability (BQP) class is believed to enclose all the problems that possess an efficient quantum algorithm , i.e. algorithms where the number of classical steps, gates and qubits required to do the computation is given by a polynomial function. It is believed to contain the classical efficient P ( polynomial ) class, and there is evidence of the existence of problems belonging to the class BQP, but not to the class P1, e.g. the Shor [329] or Simon algorithms [331] are believed to be in the class NP. Nowadays there is a wide range of efficient quantum algorithms, for which a comprehensive survey seems completely unfeasible, but good starting points are given for instance in [ 272 , 108 , 100 , 212 ]. From here, one can identify two types of algorithms possessing quantum advantage, which we denote as the dynamic ones and the static ones. The former ones encompass the simulation of processes, and the latter 1 Only evidence because there is no proof that the class P is not the same as the class NP 39 3.2. Search, sampling and simulation algorithms 40 the calculation of algebraic properties of certain mathematical objects. From both, it is possible to identify algorithmic building blocks, which, presumably, yield the quantum advantage, by maximizing the effects of interference allowed by sets of entangled qubits. In one hand, the simulation of quantum processes, i.e. the dynamic algorithms, consists in the efficient conception of computational processes that are able to mimic , i.e. by being statistically indistinguishable, a quantum process to be simulated up to an error 𝜖 . This type of simulation is also known as weak simulation , in opposition to strong simulation , where it is expected that both processes produce exactly the same results. On the other hand, the static problems concern the extraction of generative characteristics of functions, e.g. the period of a function as it happens in the Shor algorithm [ 329 ]. These algorithms seem to resort to the Fourier transform and Phase estimation algorithms, which possess an exponential advantage (more on this on section 3.4). The relationship between both types of algorithms is, however yet unclear. Finally, there is a class of algorithms, which somehow makes use of both types of strategies, and includes algorithms such as the eigenvalue estimation [ 10 ] and the HHL algorithm for the resolution of linear equations [191]. 3.2 Search, sampling and simulation algorithms The Hamiltonian simulation and quantum walks provide universal models for quantum computation, which imply that not only all quantum algorithms can be put in such forms, but also that they can be reduced to each other. Both of these conceptual models provide a complementary perspective on quantum algorithms, allowing the unified study of, among others, search, sampling and simulation problems and provide insight about the specific structural properties that help in the characterization of their efficiency. First of all, search and sampling problems are considered to be equivalent [ 6 ], i.e. for each problem of sampling there is an equivalent problem of searching and vice-versa, and both can be captured by discrete quantum walks. A search problem can be interpreted as sampling problem , where the correct solution is expected with high probability, as it happens, for instance, in the Grover algorithm [ 178 ], i.e. a generic search algorithm appliable to any search space with known dimension. It yields constant quadratic advantage ,i.e.ittakes √𝑁 steps, where 𝑁 is the size of the search space, and it can be efficiently reduced to a quantum walk, as extensively studied in many works [327,292]. There are two useful specific measurements of complexity in quantum walks for the of study sampling and search problems: the hitting time , which concerns the amount of steps a specific marked state is achieved, useful to characterize search problems and the mixing time , i.e. the time a quantum walk takes to get to its stationary distribution , characteristic of sampling problems [259]. Moreover, discrete quantum walks can be always be reduced to Hamiltonian simulations, i.e. continuous quantum walks, where the Hamiltonian corresponds to the diffusion matrix of the discrete quantum walk, as discussed, for instance, in [ 96 ], drawing a common foundation between search, sampling and Hamiltonian 40 3.2. Search, sampling and simulation algorithms 41 simulation algorithms. In the setting of Hamiltonian simulation, one can obtain a clearer idea on the simulation and sampling problems that possess efficient algorithms, due to the extensive work on this regard. As discussed in sections 3.2.1 and 3.2.2 there are efficient algorithms for a wide range of Hamiltonians, which encompasses local, sparse and d-sparse ones. Therefore, it can be assumed that the sampling/simulation problems that can be phrased in a local, sparse, or d-sparse Hamiltonian, or graph, most likely possess an efficient quantum algorithm. For searching problems the criteria are less clear, although it can be stated that simulation problems are, most likely, simpler than a search problems, as one can naturally expect that the mixing time is smaller than hitting time, as in the latter one is interested in obtaining a specific element, of set elements, rather than a global distribution. In [ 97 ] a translation between a search problem and finding a ground-state of k-local Hamiltonian is proposed. Finding the ground state of Hamiltonian is known to be very complex, if it involves components with dimension greater or equal to 2, as it will be discussed in chapter 4. Therefore, search problems that cannot be mapped into Hamiltonian simulation ones, which do not involve components with dimension greater or equal to 2, do not possess an efficient algorithm. On the other hand, search problems who can, possess an efficient quantum algorithm, however, it is unclear if this leads to any quantum advantage better than a quadratic one. 3.2.1 Local Hamiltonians The simplest Hamiltonians known to be simulated efficiently with an exponential improvement are local Hamiltonians, as first conjectured by Feynman and then by LLoyd [ 249 ]. Local Hamiltonians can be decomposed into their local interactions, i.e. physical interactions happening between all subsets of the particles up to a certain dimension 𝑘 , which encompass a wide class of physical systems. Example of these is the Fermionic Hamiltonians for quantum chemistry, which only involve 2 -dimensional Coulomb interactions and 1-dimensional Kinectic components (in chapter 4we deal with an Hamiltonian of this type). Mathematically, this class correspond to the Hamiltonians that can be expressed as a sum of their local components: 𝐻=∑ 𝑖𝐻𝑖(62) The simulation of such Hamiltonian requires the existence of an efficient classical method to construct acircuitthatapproximatestheevolutionoperator 𝑒𝑖𝐻𝑡 ,uptoanerror 𝜖 . If the Hamiltonians in the sum commute pairwise [𝐻𝑖,𝐻𝑗]=0 (see section 2.2.4), then the order of application of the Hamiltonians is irrelevant and the evolution of the Hamiltonian operator is simply given by 𝐻=∏ 𝑖𝑒𝐻𝑖.(63) 41 3.2. Search, sampling and simulation algorithms 42 The simplest case of these type of Hamiltonians happens when the Hamiltonians are diagonal ,whichcan be trivially approximated by quantum circuits. The problematic cases start when the Hamiltonians do not commute, for which a multitude of approximation strategies are available. The simplest one, without diagonalizing the whole operator, is to use the diagonalization matrices in between every Hamiltonian component that does not commute, 𝑒𝐻1𝐷𝑒𝐻2𝐷−1 (64) ,where 𝐷 is the diagonalization matrix that makes 𝑒𝐻2 diagonal. This approach is quite limited, as the obtention of the diagonalization matrix is computationally complex, however, it is possible to apply it in several cases, for instance, in the simulation of the Schrödinger equation, where the basis transformation matrix ( Fourier transform ) is efficient and expressed as, 𝑋𝐹𝑃𝐹−1 (65) ,where 𝑋 and 𝑃 constitute the position and momentum operators . Furthermore, beyond these conceptually straightforward techniques, there exist a wide range of approximation techniques. The cornerstone of many of such approximation methods is the Trotter formula , based in the Lie product formula lim𝑛→∞ (𝑒𝐴𝑡/𝑛𝑒𝐵𝑡/𝑛)𝑛=𝑒𝑖(𝐴+𝐵)𝑡, which reads as 𝑒𝑖𝐻𝑡 ∼(𝑒𝑖𝐻1𝑡/𝑛 …𝑒𝑖𝐻𝑛𝑡/𝑛)𝑛+∑ 𝑖>𝑗[𝐻𝑖,𝐻𝑗]𝑡2/2𝑛+ ∞ ∑ 𝑘=3 𝐸(𝑘). (66) This expression states that an Hamiltonian operator, where local components do not commute can be approximated by the repetition (through 𝑛 steps) sequence of local operators 𝑒𝑖𝐻1𝑡/𝑛 …𝑒𝑖𝐻𝑛𝑡/𝑛 (as if they would commute), where the time is discretized in steps of size 𝑡/𝑛, , and with the error bounded by the 𝐸(𝑘) formula, always being less than ||𝑛(𝑒𝑖𝐻𝑡 −1−𝑖𝐻𝑡/𝑛)|| and the error can be arbitrarily small with the increase of n. The computational complexity can be estimated by the number of operations needed for the repetition of the operators involved. Each 𝐻𝑗 acts on a local Hilbert space, the number of operations needed to simulate 𝑒𝑖𝐻𝑗𝑡/𝑛 ∼𝑚𝑗2 . Hence the global simulation time obeys the inequality 𝑛(∑𝑙 𝑖𝑚2 𝑖)≤𝑛𝑙𝑚2 ,where 𝑚=𝑚𝑎𝑥{𝑚𝑖} . The error in each of the operations must be minor than 𝜖/𝑛𝑙𝑚2 . Now everything depends on 𝑙, some number of components of the variable. 3.2.2 Sparse and d-Sparse Hamiltonians Sparse Hamiltonians are a more general setting than local Hamiltonians, encompassing a wider class of physical systems, as well as other algorithmic problems with practical interest, such as quantum walks 42 3.3. Case study: Simulation of non-radiative energy transfer in photosynthetic systems using a quantum computer 43 with exponential gain [ 101 ], or NAND trees approximation [ 102 ]. Sparse Hamiltonians are defined as Hamiltonians with a limited number of non-zero entries per row: 𝑑 = 𝑝𝑜𝑙𝑦(𝑙𝑜𝑔𝑁) ,where 𝑁 is the dimension of the Hamiltonian. For a 𝑘− local Hamiltonian with 𝑚 terms, the Hamiltonian is sparse if 𝑑=2𝑘𝑚. The first algorithm to deal efficiently with this kind of Hamiltonians was introduced by Aharonov et al. [ 16 ], where both the number of gates and of oracle calls are polynomial. Since then, there has been a significant amount of work on the subject, striving to reach optimality of such parameters, where the works of [ 255 ] and [ 61 ], (almost optimal) and the recent ones of [ 254 , 255 ] (optimal), shall be highlighted. The methods employed in these approximations are the recent technique of qubitization [ 256 ], and the truncated Taylor series method [60]. There is also some work on the simulation of non-sparse Hamiltonians , only applied in very limited cases [ 98 ], and for which no general efficient quantum algorithm is known [ 364 ]. Furthermore, to the best of our knowledge it is not clear how interference is used in these algorithms. 3.3 Case study: Simulation of non-radiative energy transfer in photosynthetic systems using a quantum computer We explore now the experimental simulation of a local Hamiltonian, which can be also interpreted as discrete quantum walk, that can be built and runned in a quantum computer: the one of transfer energy, by non-radiative means, existent in first stage of photosynthesis. This process has been shown to be influenced both by quantum coherent and decoherent effects, aspects also explored in this simulation. This exploration also helps understanding, besides the quantum aspects of photosynthesis, how the theoretical aspects of quantum mechanics, particularly the environmental ones introduced in section 2.3.4,work. Photosynthesis is a vital and pervasive complex physical process in nature, where the radiation of the Sun is captured by certain living beings , such as plants and bacteria, and transformed into the necessary carbohydrates needed for their survival [ 267 , 238 ]. From the physics and chemistry perspective, it is a complex process occurring through several stages with several kinds of physical phenomena involved, namely, the light absorption, energy transport, charge separation, photophosphorylation and carbon dioxide fixation [ 154 ]. The understanding of such phenomena has greatly progressed in the past 40 years with the physical characterization of the structure of many photosynthetic complexes [ 128 , 321 , 94 ]. The comprehension of such processes would allow for many potential huge-impact industrial breakthroughs in the field of energy, from the great efficiency improvement in energy capture of solar panels [ 244 ]tothe construction of artificial light-harvesting devices and solar fuels [378,182,183,312]. The photosynthesis begins by the absorption of a photon. It occurs via excitation of a pigment molecule, which acts as a light-harvesting antenna connected to the rest of the photosynthetic apparatus by protein molecules. Photosynthetic pigment-protein complexes transfer the absorbed sunlight energy, in the form 43 3.3. Case study: Simulation of non-radiative energy transfer in photosynthetic systems using a quantum computer 44 of molecular electronic excitation, to the reaction center, where charge separation initiates a series of biochemical processes [ 267 ]. This work is focused on the first stage of photosynthesis, more precisely, on the transport of the absorbed radiation energy from the antenna to the reaction centre, which proceeds in the form of the so-called Excitonic Energy Transfer (EET), as schematically shown in Fig.7. Figure 7: Schematics of the energy transfer process from light-harvesting antenna (the donor) through a chain of acceptor molecules to the reaction center. The excited states of the participating molecules, denoted 𝜖𝑚 , are broadened and it allows for resonance energy transfer via irreversible Förster-type resonant process of exciton transfer from donor to acceptor even if 𝜖𝑚≠𝜖𝑚+1 , which is denoted by the thick arrow labelled FRET. However, if the coupling between the donor and the acceptor molecules is strong enough, the process becomes reversible and the exciton can go to and through many times before it is transferred; this situation is labeled by "reversible EET" and it does not require matching of the energy levels 𝜖𝑚and 𝜖𝑚+1.Picturetakenfrom[179]. This transport is known to be very efficient in photosynthesis, as is the whole process, with the overall quantum efficiency of initiation of charge separation per absorbed photon up to 95% [ 267 ]. The absorbed photon creates an exciton on the antenna molecule, which can eventually transfer it to other molecules. In this context, it is called donor, while the others are called acceptors and the EET process can be described by the following reaction equation: 𝐷⋆+𝐴→𝐷+𝐴⋆.(67) One may be lead to believe that, given the ”size” of the physical components involved, the EET is a fully classical (i.e. irreversible and unidirectional) process, however experimental results have shown the opposite, with the verification of coherence between molecules over some period of time, evidenced by long-lived oscillatory features in the dynamical response of several photosynthetic systems in many experimental works [ 144 , 241 , 199 ]. However, it is predicted that these processes are still strongly influenced by the environment [ 303 ], as the donor-acceptor pairs are not isolated from the rest of the world, and, hence, the 44 3.3. Case study: Simulation of non-radiative energy transfer in photosynthetic systems using a quantum computer 45 appropriate theoretical setting to deal with this kind of systems is the one of quantum open systems . In this setting, quantum systems are treated as part of a larger system ones, composed by the EET system under study and the environment. The latter is modeled by a thermal bath, which interacts with the EET quantum system, introducing relaxation and dephasing into and, therefore, influencing the efficiency of the energy transport. The theoretical treatment of such systems is very complex from the computational point view, to which a myriad of methods is available, grouped by the type of regimes they can be applied, characterized by the coupling strength between environment and main systems , as well as the presence of memory effects (i.e. whether the system can be considered as Markovian or not) [267,209,308,152,339,340,205] This case-study proposes a quantum simulation for the EET quantum transport, and the behaviour of the system is evaluated on different environment regimes: from the unexistence of environmental effects (pure) to different system-environment couplings, with the environment being modeled only by the employment of pure dephasing effects . The experimentally Hamiltonians defined [ 19 ], and already used in other quantum simulations [ 363 ], were used and the experimental study was conducted in the commercially available IBM Q of 5 qubits [116], which makes it a different approach from the existent ones [273,293,341,363]. 3.3.1 Modeling the simulation Our implementation contains a quantum part, aimed at simulating the unitary part of the system’s evolution, and a classical part that simulates the stochastic interaction with the environment, the latter only being able to mimic pure dephasing environmental effects. We aim at exploring the energy transport underlying the photosynthesis, throughout time, under two regimes: (i) in an isolated system and (ii) under an action of the environment causing decoherence. Concerning the particular qubit encoding chosen, a chain of 𝑁=2𝑞 molecules is encoded by a set of 𝑞 qubits, where |𝑚⟩ corresponds to the excitation (exciton) on the 𝑚 -th molecule, e.g. for a two-molecule chain, state |0⟩ represents the exciton on the first molecule and |1⟩ on the second one, and a possible successful transport of energy would correspond to the transition of the state |0⟩ to the state |1⟩ . We denote this as the site basis . The computational Hamiltonians under this encoding for the cases under study are discussed in the following sections. From now on, we shall set ~=1 . Also, it is convenient to measure the energies/frequencies in cm−1, as it is common in spectroscopy. 3.3.2 No–decoherence Hamiltonian Considering a small chain of 𝑁molecules, the system’s Hamiltonian in the site basis reads as follows, 45 3.3. Case study: Simulation of non-radiative energy transfer in photosynthetic systems using a quantum computer 52 to the model in this setting, had one free parameter regarding the environment, the dephasing rate , 𝛾𝑑𝑒𝑝ℎ . The Lindbland equation in the Haken-Ströbl model reads: 𝑑𝜌 𝑑𝑡 =ℒ[𝜌]=−𝑖[𝐻𝑆,𝜌]+𝛾𝑑𝑒𝑝ℎ ∑ 𝑚(𝐿𝑚𝜌(𝑡)𝐿† 𝑚−1 2𝜌(𝑡)𝐿† 𝑚𝐿𝑚−1 2𝐿† 𝑚𝐿𝑚𝜌(𝑡)) (81) where 𝐿𝑚=|𝑚⟩⟨𝑚| are the Lindbland operators, responsible for the system-environment interaction. The system Hamiltonian, 𝐻𝑆 , is given by the matrix (79) for the near-resonant system and the matrix (80) for the non-resonant system. The environment contains only one fluctuator interacting with each molecule with switching rate 𝛾=125 THz . As mentioned above, the dephasing rate, 𝛾𝑑𝑒𝑝ℎ , for the Lindbland equation is adjusted to the behaviour of the system under the action of a fluctuation strength 𝑔 . For a range of fluctuation strengths of [100,1000] 𝑐𝑚−1 , in the quantum algorithm, and the corresponding dephasing rate of the Haken-Ströbl model lies in the ∼[2.3,70]THz range. Due to the existence of random fluctuations, large number of samples had to be generated. The algorithm was implemented with 250 runs, where 5000 shots were performed for each time 𝑡 .Figures13 and 14 present the simulation results for different values of the fluctuation strength, along with the theoretical evolution dynamics, for the near-resonant and non-resonant systems, respectively. It is seen in Figures 13 and 14 that oscillation amplitudes decay over time, as expected, due to the loss of relative phase coherence between the excited states of the two molecules, evidenced by the disappearance of the quantum beatings. This is associated with the irreversible evolution when the system loses its capacity of performing coherent transport. Additionally, it is clear that the system is led to a classical distribution of the populations in the site eigenbasis. In the regime under the study, where the environment is assumed to be at thermal equilibrium, the final probability distribution is calculated in the limit of the classical Boltzmann distribution ⟨𝑚|𝜌𝑆(𝑡→ ∞)|𝑚⟩=𝑐𝑜𝑛𝑠𝑡×𝑒−𝜖𝑚 𝑘𝐵𝑇 .Here 𝑘𝐵 is the Boltzmann constant, 𝑇 is the temperature of the bath and 𝑐𝑜𝑛𝑠𝑡 is a normalization constant [ 83 ]. Taking the limit of very high temperatures, the population terms approach the Boltzmann distribution ⟨0|𝜌𝑆(𝑡→∞)|0⟩≈⟨1|𝜌𝑆(𝑡→∞)|1⟩≈1 2 , which is compatible with the results obtained. The relaxation can not be fully observed in Figs. 13a,14a and 14b because a very large number of iterations would be required for this. 52 3.3. Case study: Simulation of non-radiative energy transfer in photosynthetic systems using a quantum computer 53 (a) 𝑔 = 100 𝑐𝑚−1,𝛾𝑑𝑒𝑝ℎ = 2.3 𝑇𝐻𝑧.(b) 𝑔 = 300 𝑐𝑚−1,𝛾𝑑𝑒𝑝ℎ = 10 𝑇𝐻𝑧. (c) 𝑔 = 700 𝑐𝑚−1,𝛾𝑑𝑒𝑝ℎ = 41 𝑇𝐻𝑧.(d) 𝑔 = 1000 𝑐𝑚−1,𝛾𝑑𝑒𝑝ℎ =70𝑇𝐻𝑧. Figure 13: Evolution dynamics of the system with decoherence obtained by employing the quantum algorithm for the near-resonant system: simulation results (points) and theory (lines). The switching rate must be high enough to observe the dephasing effects. Here we used a value ≈33 times larger than the transfer rate, 𝐽 (that is, the fluctuator waiting time must be shorter than 𝐽−1 ). As observed in the simulations, it is a suitable value for observing the relevant effects of random fluctuations in the system. At very low rates, it leads the system’s evolution to a behaviour similar to the previously observed in the no-decoherence regime, Figs. 11 and 12. The time that coherence lasts in the system is essentially defined by the fluctuation strength, 𝑔: in Figs. 13a,13b,14a and 14b (lower 𝑔 ) the coherence is maintained for some time, while in Figures 13c,13d,14c and 14d (higher 𝑔 ) it is quickly suppressed. In the latter regime, an approximated diffusive motion drives the system’s evolution, where quantum beating is practically absent. The time that the quantum beating lasts in these simulations (until it reaches an approximate non-oscillating behaviour), is about 350𝑓𝑠 in Figure 13b (near-resonant system) and 200𝑓𝑠 in Figure 14b (non-resonant system), with a fluctuation strength 𝑔=300𝑐𝑚−1 . At a longer time, it has been experimentally observed to persist ( 𝑡>660𝑓𝑠 [ 283 ]), a timescale which could be modeled in the present simulation by changing the environment parameters, i.e. lowering the fluctuation strength 𝑔as can be observed in Figures 13a and 14a. 53 3.3. Case study: Simulation of non-radiative energy transfer in photosynthetic systems using a quantum computer 54 (a) 𝑔 = 100 𝑐𝑚−1,𝛾𝑑𝑒𝑝ℎ = 2.3 𝑇𝐻𝑧.(b) 𝑔 = 300 𝑐𝑚−1,𝛾𝑑𝑒𝑝ℎ = 10 𝑇𝐻𝑧. (c) 𝑔 = 700 𝑐𝑚−1,𝛾𝑑𝑒𝑝ℎ = 41 𝑇𝐻𝑧.(d) 𝑔 = 1000 𝑐𝑚−1,𝛾𝑑𝑒𝑝ℎ =70𝑇𝐻𝑧. Figure 14: Evolution dynamics of the system with decoherence obtained by employing the quantum algorithm for the non-resonant system: simulation results (points) and theory (lines). For each quantum simulation performed, a fitting process has been employed by adjusting the dephasing rate of the Haken-Ströbl model, so that the system’s evolution in both classical and quantum algorithms have similar behaviours. This enables one to perform a direct comparison between both theories and to find the actual dephasing rate of the modeled environment over the various regimes considered in this work. The results reflect a good agreement between the data obtained and the theoretical predictions both for the coherent case (vs Schrödinger equation) and the decoherent case (vs Haken-Ströbl model), for the different regimes definable by the coupling strength [ 303 ]. Similar to Ref. [ 363 ], this setting revealed itself as an interesting platform for the study the quantum and environmental effects in a small photosynthetic system, and therefore we consider, that the use of quantum simulations may be a feasible alternative in systems with medium-strong coupling and non-Markovian systems , in the future, whose main advantage when compared to similar works Ref. [ 363 ], is the flexibility on the implementation brought the quantum computer used. However, the algorithm obtained, possess high requirements in terms of gates and qubits, and, hence, it is feasible to implement to realistic since a realistic quantum simulation of a photosynthetic system would have to involve hundreds of light-harvesting molecules, which is beyond the current quantum technology, and simultaneously the complexity of circuit generation is still 𝑂(𝑁3) ) and it only involves pure-dephasing 54 3.4. Algorithms based in the quantum Fourier transform 55 baths. For future work, we aim at extending it to new types of bath, e.g. those allowing for higher exciton recombination rates and non-Markovian effects as well as to new geometries of photosynthetic systems, in particular, to the Fenna-Matthews-Olson complex [267]. In conclusion the coherent case is clearly described by a local Hamiltonian and hence it is efficiently simulatable, although not the best choice of circuit approximation was used in this work. The addition of environmental noise , to simulate decoherence , quickly raises the complexity of the algorithm, making a realistic simulation of a photosynthetic system unfeasible in current quantum computers. Nonetheless, a very good picture of how the environmental noise interacts with a closed system, destroying coherence, was obtained, complementing the discussion of chapter 2. 3.4 Algorithms based in the quantum Fourier transform The Fourier transform is exponentially faster in quantum computers than it is on classical ones, and it is a cornerstone of several of the most relevant and efficient quantum algorithms, such as the ones of Deutsch-Jozsa [ 134 ], Simon [ 331 ] and Shor [ 329 ]. It seems to be the main cause of quantum advantage in quantum algorithmics, making extensive use of quantum interference . Its mathematical foundation can be given in terms of group and representation theory, which allows its generalization to other algorithms, and to obtain further characterization insights about them. So far, only algorithms based on the Fourier transform over functions subject to the action Abelian groups are efficient, i.e. the only ones in which irreducible representations are in a one to one relationship with the elements of the group. From this perspective, efficient algorithms for a wide range of problems have been obtained, however, the attempts to generalize it to non-Abelian groups felt short, and no generalized algorithm for these problems exist, leaving out problems with high industrial impact such as the graph-isomorphism. In this section we explore these issues. 3.4.1 The Quantum Fourier transform algorithm The Fourier transform is a vital tool in modern mathematics, physics and engineering with a wide range of applications from quantum mechanics to signal processing. In quantum computation, it also plays a central and vital role, as it is the most important building block of the most well-known efficient quantum algorithms and, definitely, a source of quantum advantage : the fastest classical Fourier transform has a time complexity of order 𝑁𝑙𝑜𝑔(𝑁) , while the quantum one, has only (𝑙𝑜𝑔𝑁)𝑙𝑜𝑔(𝑙𝑜𝑔𝑁) , i.e. an exponential advantage. This makes the application of the quantum Fourier transform feasible, to problems where the classical Fourier transform is not, as, for example, to find the period of a function as in Shor algorithm. The most common form of the Fourier transform, used in fields such as signal processing, reads as follows: 55 3.4. Algorithms based in the quantum Fourier transform 56  𝑓(𝑥)=∫𝑒−2𝜋𝑖𝑘𝑥𝑓(𝑥)𝑑𝑥,𝑘∈ℝ (82) In this field of application, the Fourier transform, can be interpreted as a function between the domain of times and the domain of frequencies, where 𝑒−2𝜋𝑖𝑘𝑥 , corresponds to a sinusoidal function characteristic of a frequency 𝑘 ,and  𝑓(𝑥) corresponds to the frequency response of the timed function at a given point, decomposing the timed signal in its frequencies. The same intuitions are valid, for instance in quantum mechanics: the Fourier transform is a function from the position domain to the momentum domain. A more abstract treatment of the Fourier transform, phrases it in terms of group theory, where it is interpreted as a function between two groups, the group of the original function 𝑓(𝑥) , 𝐺 , and the group of unitary linear operators 𝐺𝐿(𝑉), which is given by the following expression:  𝑓(𝑝)=𝑛−1 ∑ 𝑥∈𝐺 𝑓(𝑥)𝑝(𝑥),𝑝∈𝐺𝐿(𝑉), (83) where 𝑓(𝑥) is function over 𝑥 ,where 𝑥∈𝐺 ,and 𝑝(𝑥) the irreducible representation at point 𝑥 . The first efficient algorithm for the Fourier transform, the fast Fourier algorithm (FFT) was discovered by Cooley and Tuckey [ 115 ], and its translation and application to the quantum realm was firstly made by Simon [ 331 ] and Shor [ 328 ]. The QFT algorithm starts by creating a superposition state, in which the amplitudes of the states are the actual values of 𝑓(𝑥), as follows: |Ψ⟩=2𝑛−1 ∑ 𝑥=0 𝑓(𝑥)|𝑥⟩. (84) Upon the application of the quantum Fourier transform, the resultant state is given by: |Ψ⟩=∑ 𝑦𝑔(𝑦)∣𝑦⟩ (85) where function g(y), corresponds to the amplitude of each of the elements of the 𝑦 basis, and corresponds to the actual Fourier transform formula 𝑔(𝑦)=𝑎(Φ→𝑦)=⟨𝑦∣Φ⟩= 1 2𝑛/2 2𝑛−1 ∑ 𝑥=0 𝑒2𝑖𝜋𝑥𝑦/2𝑓(𝑥). (86) The statistics of the quantum Fourier transform, is invariant to constant shifts affecting the function 𝑓(𝑥) , i.e. for functions whose resultant Fourier transform form 1 2𝑛/2 1 √𝐾 𝐾−1 ∑ 𝑘=0 𝑒2𝑖𝜋𝑦(𝑐+𝑘𝑟)/2𝑛∣𝑦⟩,(87) the statistics of of the Fourier transform, reads as 56 3.4. Algorithms based in the quantum Fourier transform 57 𝑝(𝑦)= 1 2𝑛1 √𝐾∣∣∣∣ 𝐾−1 ∑ 𝑘=0 𝑒2𝑖𝜋𝑘𝑦𝑟/2𝑛∣∣∣∣ 2,(88) i.e. it is not affected by 𝑐 . The reason for this is that 𝑐 only affects the global phase, and, hence, does not affect the statistics of the measurements. By reasoning about these statistics it is possible to retrieve important properties of the original function 𝑓(𝑥) , such as its period as done in the Shor algorithm of the following section. 3.4.2 The Shor algorithm and the hidden subgroup problem (HSP) The Shor algorithm [ 330 ] is the most important in quantum computation, due to its industrial impact, as it can break RSA cryptography [ 76 ]. In practice, what the algorithm does is finding the (large) period of a function, from which an attack on the cryptographic scheme can be built. The algorithm of Shor is based on Simon algorithm for the calculation of discrete logarithms [ 331 ], and in fact, these algorithms can be phrased in a more generic way as instances of the Hidden subgroup problem [ 75 , 225 ], a problem from the domain of group theory. Later, other instances of this problem were found, as depicted in table 7.The formal definition of the Hidden subgroup problem goes as follows: Definition 3.4.1. Given a function 𝑓∶𝐺→𝑅 , where 𝐺 is a finite group and 𝑅 an arbitrary finite range, and the assumption that there exists a subgroup 𝐻≤𝐺 , where 𝑓 is constant and distinct on the left cosets of H, find the generating set of H. The definition may sound somewhat puzzling for non-mathematicians, so the easiest way is to look into an example, which goes as follows: Example 3.4.1. Consider a periodic function 𝑓 on a group 𝐺 presented in the following table: x 0123456789 f(x) 0120120120 assumed to be of type 𝑓∶𝐺→ℝ , where + is the operation of 𝐺 . The structure of the group, i.e. including its actual number of elements is not known, but according to the definition 3.4.1, 𝑓(𝑥) is constant in the cosets of the group. Hence, from the simple observation of the function, one concludes the cosets must correspond to the following sets: {0,3,6,9,...},{1,4,7,...},{2,5,8,...}. (89) Each coset corresponds to an equivalency class, resulting from the action of an element of group, over the hidden subgroup. From group theory, it is well known that any element of 57 3.4. Algorithms based in the quantum Fourier transform 58 agroupgeneratesasubgroup.Hence,fromtheinformationavailableaboutthefunction (elements and operation), the possible subgroups read as follows: ⟨0⟩={0} ⟨1⟩={0,1,2,3,4,5,6,7,8,9,...} ⟨2⟩={0,2,4,6,8,...} ⟨3⟩={0,3,6,9,...} So, having calculated all the subgroups, is trivial to see what is the one that fits the coset structure presented in equation (89) ,isthesubgroupgeneratedbyelement 3 , ⟨3⟩ , which can be confirmed by operating a arbitrary element of each of the cosets with the subgroup determined, allowing to retrieve the cosets back again: 0⋅{0,3,6,9,...}={0,3,6,9,...} 1={1,4,7,...} 2⋅{0,3,6,9,...}={2,5,8,...} .... Hence the so-called hidden subgroup is {0,3,6,9,...} and its generator is 3 , which also corresponds to the period of the function, which can be trivially verified. It is also the number needed to perform the attack on RSA encryption scheme. In the RSA cryptographic scheme, the modular exponentiation is used, instead of the modular summing operation, as explored in example 3.4.1, and the computational solution explored in such example is clearly computationally inefficient , as it requires the calculation of all possible subgroups, being only a toy example. The Shor algorithm is able to determine the right coset structure and the generator of the correct subgroup with high probability in a very efficient way, with an exponential advantage to the best classical algorithms. The same quantum algorithm used in Shor is common and efficient for all Abelian groups with many applications [ 186 , 185 , 271 ]. It has also been shown that the algorithm works efficiently for all groups, which even not Abelian, if they possess normal subgroups [187], only. Problem Query Complexity Main Technique Abelian Stabilizer Problem Polynomial Fourier Sampling/Transform [225] Shor algorithm for factoring and discrete logarithm Polynomial Fourier Sampling/Transform [329] Simon’s XOR-mask finding a Polynomial Fourier Sampling/Transform [331] Pell’s equation and Principal Ideal Polynomial Fourier Sampling/Transform [186] Unit Group and Class group Polynomial Fourier Sampling/Transform [185] Table 7: Some problems with efficient quantum algorithms using the Fourier transform The algorithm starts with the state preparation, where two logical registers are used, to encode the domain and codomain of a homomorphic function between Abelian groups. The first step corresponds to the preparation of the domain of the function in the first register, building a homogeneous superposition of values of the domain: |Φ⟩= 1 2𝑛/2 ⎛ ⎜ ⎝ 2𝑛−1 ∑ 𝑥=0 |𝑥⟩⎞ ⎟ ⎠⊗|0…0⟩ (90) 58 3.4. Algorithms based in the quantum Fourier transform 59 The second step corresponds to the application of an oracle 𝑓 , which is based on the domain elements of the first register, constructs the codomain elements in the second register: ∣Ψ𝑓⟩=𝑈𝑓|Φ⟩= 1 2𝑛/2 ⎛ ⎜ ⎝ 2𝑛−1 ∑ 𝑥=0 ∣𝑥⊗𝑓(𝑥)⟩⎞ ⎟ ⎠.(91) At this stage, due to the requirement of being constant on the cosets, for each 𝑓(𝑥) is associated a coset of the function, i.e. a potential measurement of the second register will yield the corresponding coset in the first register: ∣Ψ0⟩=1 √𝐾 𝐾−1 ∑ 𝑘=0 ∣𝑥0+𝑘𝑟⟩.(92) In equation (92) , 𝑘𝑟 , corresponds to the exponentiation of the generator of the hidden subgroup , 𝑟𝑘 ,and 𝑥0 is the coset representative, which is unknown, and thus, prevents direct measurement of the generator. However, its effect can be discarded, if one goes instead onto the phase domain, which can be done systematically by the use of the Fourier transform. The application of the Fourier transform to the coset state yields the following state: 1 2𝑛/2 1 √𝐾 𝐾−1 ∑ 𝑘=0 𝑒2𝑖𝜋𝑦(𝑥0+𝑘𝑟)/2𝑛∣𝑦⟩(93) While it can be observed that the coset representative 𝑥0 is still part of the amplitude of the basis elements ∣𝑦⟩, i.e. by looking to the amplitude of an element of the basis 𝑦given by 𝑎(Φ↦𝑦)= 1 2𝑛/2 1 √𝐾 𝐾−1 ∑ 𝑘=0 𝑒2𝑖𝜋𝑦(𝑥0+𝑘𝑟)/2𝑛,(94) it is also observable that the element 𝑥0 does not have any statistical effect on the measurement of elements, as it only affects the global phase of the state, disappearing when the amplitude is squared : 𝑝(𝑦)= 1 2𝑛1 √𝐾∣∣∣∣ 𝐾−1 ∑ 𝑘=0 𝑒2𝑖𝜋𝑘𝑦𝑟/2𝑛∣∣∣∣ 2.(95) Hence, the generator 𝑟 can be retrieved, by the use of a statistical inference technique named Fourier sampling . The equation above is equal to the geometric series, 𝑝(𝑦)=𝑠𝑖𝑛2(2𝜋.𝑐𝑠.𝑟.𝑀 2𝑛) 𝑠𝑖𝑛2(2𝜋.𝑐𝑠.𝑟 2𝑛)(96) ,if𝑦=𝑗𝐾, and 0 in the other case 59 3.5. Hybrid algorithms 60 𝑝(𝑦)= 1 2𝑛𝐾𝑠𝑖𝑛2(𝜋𝑦) 𝑠𝑖𝑛2(𝜋𝑦/𝐾)=1 𝑟.(97) It can be concluded that 𝑗/𝑟 = 𝑦/2𝑛 , and one can obtain j and r from the irreducible form of 𝑦/2𝑛 , which can be obtained by measuring 𝑦 and expanding the result towards an irreducible fraction using the Newton algorithm. The algorithm is probabilistic and the period obtained must be validated by testing it: 𝑓(𝑥)=𝑓(𝑥+𝑟) , and the execution of the algorithm repeated, if necessary. The probability of obtaining a stated reducible to 𝑗/𝑟 is high, when compared to the demanded precision, which means the algorithm in sound. The algorithm corresponds to finding the Abelian group generator. 3.4.3 Non-Abelian Hidden subgroup problem After the success of the hidden subgroup problem algorithm for Abelian groups, there has been an extensive research effort in extending the algorithm to non-Abelian groups. Examples of relevant groups in these conditions are the dihedral and symmetry group , for which efficient algorithms for their hidden subgroup problem will have an important impact, yielding efficient solutions to lattice-based cryptography [ 307 ]and graph isomorphism [ 49 , 145 ]. However, despite of some successes on this side, e.g. [ 203 , 206 ], the hidden subgroup problem for the most relevant groups is still beyond reach, even, as demonstrated, with the query complexity always being 𝑙𝑜𝑔(|𝐺|) ( |𝐺| is the size of the group involved) for these algorithms [ 146 ]. However, for some groups the information within cosets is not enough to capture the hidden subgroup and further processing may be required, which is generally timewise inefficient. For some groups it may be sufficient to enhance the HSP with the application of a proper measurement strategies [ 36 ], however it has also been shown that the application of the technique is bounded by physical limitations [ 188 ]. Such information shall then be filtered classically in order to retrieve the hidden subgroup, which may include solving linear equations [ 311 ] or other alternative techniques [ 237 ]. Moreover, an effective pretty good measurement able to distinguish such states will also need to involve an almost unfeasible amount of states. Due to impossibility of reaching an efficient algorithm for relevant groups with potential impact in industry, it was also attempted to explore different algorithms, such as hidden-shifts [ 99 , 352 ], hidden-polynomials, hidden translations [ 162 ], hidden cosets [ 162 ] and the generalized study of symmetry groups ,which may have many different applications. 3.5 Hybrid algorithms There is another class of quantum algorithm, which makes use of quantum simulation and of the exponential advantage of the Fourier transform, as it is the example of the estimation of eigenvalues of Abrams and LLoyd [ 10 ] and the HHL algorithm for the resolution of linear equations, proposed by Harrow, Hassidim 60 3.5. Hybrid algorithms 61 and LLoyd [ 191 ]. The former consists of two steps, namely, the simulation of the Hamiltonian and the application of phase estimation [ 125 ] (an algorithm relying on the Fourier transform) to obtain the eigenvalues corresponding to a given eigenvector , i.e. the composition Phase estimation ∘Hamiltonian simulation (98) Therefore, the efficiency of the algorithm is directly dependent on the efficiency of the Hamiltonian simulation, given that the phase estimation step is known to be efficient. The latter algorithm, the HHL one, can be seen as a more generalized form of finding a particular eingenvalue, and also depends on the efficient simulation of the exponential of an Hermitian operator. Briefly, the algorithm is able to solve systems of equations of the sort: 𝐴𝑥= 𝑏(99) where 𝐴 and 𝑏 define a set of linear equations. The algorithm requires the simulation of 𝑒𝑖𝐴𝑡 for different values of 𝑡 , which possess a potential exponential advantage, as explored in section 3.2.1. The matrix 𝐴 , may not always be a Hermitian operator, but it can be translated into one, by the following construction, ⎛ ⎜ ⎝0𝐴 𝐴𝑡0⎞ ⎟ ⎠(100) and whenever 𝐴𝑡 is an Hermitian operator , 𝑒𝑖𝐴𝑡 is an unitary operator. Technically, the algorithm prepares ∑𝑁 𝑖=1 𝑏𝑖|𝑖⟩ , and then using quantum simulation , calculates 𝑒𝑖𝐴𝑡 for a superposition of different times t, and further, with the help of the phase estimation algorithm, is able to decompose ∣𝑏⟩ in the eigenbasis of A and find the corresponding eigenvalues 𝜆𝑗. The result of these operations reads as: 𝑁 ∑ 𝑗=1 𝛽𝑗∣𝑢𝑗⟩∣𝜆𝑗⟩(101) where {∣𝑢𝑗⟩|𝑗∈1…𝑁N is the dimension of system} is the eigenvector basis of A, and ∣𝑏⟩=∑𝑗1𝛽𝑗∣𝑢𝑗⟩ . The only thing required right now is to find the inverse of each of the eigenvectors, producing the state 𝐶𝜆−1 𝑗∣𝜆𝑗⟩. Finally, one obtains the state 𝑁 ∑ 𝑗=1 𝛽𝑗𝜆−1 𝑗∣𝑢𝑗⟩=𝐴−1 ∣𝑏⟩=|𝑥⟩. (102) Besides the possibility of the efficient simulation the Hamiltonian, the performance of the algorithm also depends of the differences of eigenvalues, captured by a parameter 𝑘 .Theactualelements |𝑥⟩ , can be obtained individually in a single execution, which requires 𝑁 repetitions of the algorithm, if one is interested 61 4.2. Optimization using quantum computers 68 computing models; Variational methods, which are targeted to short-time devices, and mostly are classical optimization algorithms taking advantage of the exponential gain in Hamiltonian sampling. Throughout the following sections these notions are discussed with more detail. Figure 16:Types of approaches to optimization problems 4.2.1 Universal quantum algorithms There are efficient quantum algorithms to solve least-squares, linear and semi-definite programs, up to convex programs , with at least polynomial advantage. The algorithm for the least-squares problem is based on the HHL algorithm [ 373 ], where an exponential advantage to classical approaches can be obtained, despite the existence of polynomial classical algorithms to this kind of problems. Another very relevant line of work is the one started by Brandao and Svore [ 80 ] providing an algorithm for Semi-definite programs , yielding a polynomial advantage to linear programs , based on several geometrical parameters. This line of work was also pursued in [ 350 , 216 , 349 ]. There are also some results within this field, concerning more general convex optimization problems, which contrary to least-squares and SDP problems, have no natural quantum structure associated. However, an algorithm with a quadratic improvement to the classical state of the art algorithm is available [ 351 , 93 ]. In an even more general setting, shall be considered the work on quantum gradient descent algorithms [ 172 , 306 ], which can be applied to any optimization problem, including non-convex and non-linear optimization [ 93 ], in some cases with polynomial quantum advantage. In a recent line of work, it has also started to be explored the application of the Grover Adaptive algorithm in optimization problems [171,47]. 4.2.2 Quantum adiabatic computing and quantum annealing The quantum computational technique of quantum annealing was firstly introduced in 1989 by Apolloni et al. [ 26 ], being one of the first quantum computational techniques conceived. In this work it was established a correspondence between the Schrödinger operator, 𝑑2 𝑑𝑥2+𝑉(𝑥) on a semi-classical regime, and a 68 4.2. Optimization using quantum computers 69 function to be minimized , corresponding to a combinatorial optimization problem, by modeling the latter on the p-otential 𝑉(𝑥) of the former. In this setting, the local minima correspond to the points of lower potential, and, physically, the wave function will yield greater probabilities at such points. However due to the, exclusively quantum, tunneling effects , it also becomes possible that particles break potential barriers and jump to the region of other local minima, eventually finding global minima . In such work, this is clearly shown by the analysis of the semi-classical dynamics of the ground-state of the system: in one hand it is verified that the equilibrium points (points to which the dynamics tends to) of the dynamics correspond to local minima (zeros of the derivate function), and that quantum tunneling allows the jump between equilibrium points. It can also be shown that if enough time passes the dynamics tends to go to the global minima . Hence, quantum annealing can be understood as the quantum counterpart of the classical method of simulating annealing , where thermodynamical oscillations guarantee the escape from local minima, and if enough time passes the system will converge to the global minimum. However, it is believed that this method produces a quantum advantage, by converging more quickly than simulate annealing to global minimum, but most importantly, by doing so in semi-classical regimes, i.e. being more tolerant to environmental noise. The idea has already yielded several short-term devices as documented in [153,215,126]. Moreover, adiabatic quantum computing, was firstly proposed by [ 148 ], and can be understood as a particular case of quantum annealing , applicable when the environmental conditions (i.e. temperature and dissipative conditions), are compatible with the adiabatic theorem , i.e. allow for an adiabatic transition where no exchange of information with the environment happens [222]. The main idea of the technique is to prepare the system in the ground state of an easy to prepare Hamiltonian ( 𝐻𝐼 ), and then, slowly introduce the action of a second Hamiltonian (problem Hamiltonian), in a perturbative way, in the system, so that in the end the system is encountered in the ground state of the sum of Hamiltonians. The total Hamiltonian of the system shall read as: 𝐻=𝐻𝐼(𝑡𝑇)+𝐻𝑃(1−𝑡/𝑇) (105) If the transition occurs slowly enough (large 𝑇 ), the global system will stay in the ground-state , which will be equal, in the end of the transition, to the ground state of Hamiltonian 𝐻𝑃 . Hence, all that is necessary is that the solution of the problem P, coincides with the global ground state of Hamiltonian 𝐻𝑃 . There are many methods of doing this mapping, and adiabatic computing, despite being a universal computational method [17], is particularly suited for solving optimization problems [149]. These techniques find many fields of application, such as in traditional computer science, e.g. search engines [ 165 ], or even board games [ 345 ], or in a large spectrum of industrial applications. The latter includes pharmaceutics [ 286 ]), or a multitude of problems in finance, e.g. portfolio optimization [ 313 ], risk analysis [ 376 ], or the prediction of financial crisis [ 279 ]. A good review on the applications of quantum computers in finance is available in reference [ 280 ]. Finally, the spectra of applications encompass traditional 69 4.2. Optimization using quantum computers 70 areas of optimization, such as planning and scheduling problems [ 310 , 358 ], instantiated in fields such as health [ 202 ] or logistics [ 136 ]. The quantum advantage of quantum annealers is yet under discussion, as while it may not be possible to obtain an exponential advantage in exact solutions of optimization problems, it may be possible to obtain advantages in approximate versions [316]. 4.2.3 Variational methods Quantum variational methods are hybrid quantum-classical approximation algorithms, targeted at optimization problems [ 269 ], which can be applied in traditional optimization fields, such as combinatorial optimization, as well as in quantum physical problems, such as finding the ground-state of quantum physical systems [ 150 , 147 ]. The former ones are, however, particular cases of the latter, i.e. the variational methods can be applied to classical optimization problems, by finding a QUBO formulation for them, which can be trivially mapped onto an Ising Hamiltonian (there are many software tools to aid in this translation available, for instance, in the qiskit platform [ 116 ]), over which the variational method is used, to obtain its ground-state. As expected, there is evidence that the computational processes of variational methods are as complex as ground-state problems [ 67 ]. Recently, these methods have started to be used, also, in mixed-integer optimization problems, by the use of decomposition techniques [164]. Moreover, variational methods have also been used to obtain short-term versions of the most popular quantum algorithms, such as the Grover [ 270 ], or Factoring [ 25 ], although the quantum advantage is less clear in these settings. This class of methods became a cornerstone of nowadays quantum computation, due to relationship between the amount of quantum resources required and the quantum advantage obtained (more on this in section 4.2.5), i.e. low resources are required to obtain quantum advantage, turning devices based on this technique, good candidates to quantum supremacy and proof-of-concept for industrial and quantum physics optimization problems. 4.2.4 The Variational Quantum Eigensolver The Variational Quantum Eigensolver (VQE) method, is a variational method , used to estimate the lowest eigenvalue (the ground state energy) of a Hamiltonian, introduced by [ 287 ], which has been gaining relevance in recent literature on quantum computation, through its application to Hamiltonian ground-states search, and general optimization tasks – see, e.g., [268]. 70 4.2. Optimization using quantum computers 71 Fermionic problem Classical cost function qubit Hamiltonian Hq=! α hαPα=! α hα N " J=1 σαj j ! ! classical calculate energy E=! α hα!Ψ(θ)|Pα|Ψ(θ)"≥Eexact adjust parameters θ " quantum prepare trial state |Ψ(θ)" measure expectation value !Ψ(θ)| N " j=1 σαj j|Ψ(θ)" " optimization ! # " solution θ∗ Figure 17:Application of the variational method to fermionic problems, adapted from [268]. The method is a quantum version of the variational method for the calculation of the ground state energy, extensively used in Physics (also known as the Rayleigh-Ritz method) and has also been widely used for a long time in Quantum Chemistry – see, e.g., [243]. 𝐸[Ψ(  𝜃)]=⟨Ψ(  𝜃)|𝐻|Ψ(  𝜃)⟩ ⟨Ψ(  𝜃)|Ψ(  𝜃)⟩ .(106) The optimization consists of the determination of the set of parameters  𝜃 that minimize the function 𝐸[Ψ(  𝜃)] function, defined by equation (106) , consisting of the expectation value of the action of the Hamiltonian operator . The VQE method is an iterative method, wherein each iteration a quantum state, corresponding to a parameterized trial function Ψ(  𝜃) (see section 4.3.5 for an example), is prepared and the expected eigenvalue with respect to the system’s Hamiltonian is calculated. Then a classically implemented algorithm updates the parameters  𝜃∈ℝ𝑛 of the quantum state using a classical optimization routine. The previous step is repeated until some convergence criteria (e.g., in energy and/or iteration number) are satisfied. Any optimization method able to perform this task can, in principle, be used. On IBM Q [ 116 ], a few methods are available for this purpose. For instance, the Simultaneous Perturbation Stochastic Approximation Algorithm [SPSA, see 64 ], which is characterized by a very good performance under noise, or the Cobyla method [295]. The scheme of the method is depicted in Fig. 17, adapted from the latter work. Even if the optimization part is mostly classical a quantum advantage is, still, obtained, as further discussed in section, 4.2.5.A good additional discussion of this method can be found in [265]. 71 4.2. Optimization using quantum computers 72 4.2.5 The quantum advantage of the VQE method Each iteration in the VQE method, requires the evaluation of the action of the Hamiltonian over the ansatz , i.e. the estimation of the eigenvalue for the current ansatz , which corresponds to the cost function. As it is well-known, this can be done, with an exponential advantage, by the use of the quantum phase estimation (QPE) algorithm [ 10 ], which has also several other applications, such as in the resolution of linear equations [191]. The QPE method requires an approximation of the evolution operator,  𝑈=exp{(−𝑖𝐻𝑡}) ( 𝑡 is time), and its application to the initial state an appropriate number of times. For an eigenstate, the application of  𝑈 results in adding a phase (−𝐸𝑡) , so that the energy eigenvalue 𝐸 can be estimated. Unfortunately, despite its theoretical attractivity and a broad scope of possible applications, it poses serious technical difficulties, which makes its practical realization unlikely at the present level of maturity of quantum computers: it requires a very large number of entangled qubits and quantum gates to be effective. Alternatively, one can adopt a strategy of applying the Hamiltonian over a state several times, measuring the result (i.e., performing the quantum sampling ), to obtain an estimation of the expected eigenvalue , for which effective algorithms are available, particularly the Quantum Expected Eigenvalue Estimation (QEE) method. The method requires that the Hamiltonian operator can be decomposed into polynomial ( 𝑀 ) independent 𝑛 -qubit operators and consists of the “measurement” of the expectation values of such operators for a trial state |Ψ⟩(also known as the ansatz ): ⟨𝐻|𝐻⟩= ⟨Ψ|𝐻|Ψ⟩ =∑ 𝑖;𝑞 ℎ𝑖 𝑞⟨𝜎(𝑞) 𝑖∣𝜎(𝑞) 𝑖⟩+∑ 𝑖1,𝑖2; 𝑞1,𝑞2 ℎ𝑖1,𝑖2 𝑞1,𝑞2⟨𝜎(𝑞1) 𝑖1⊗𝜎(𝑞2) 𝑖2∣𝜎(𝑞1) 𝑖1⊗𝜎(𝑞2) 𝑖2⟩+⋯ (107) The estimation of the expectation values, ⟨⋯⟩ , requires repeated measurements on the polynomial number of independent terms. An objective comparison of the QPE and QEE methods is presented by [ 265 ]and summarized in Table 8. Table 8: Comparison of resources needed for two methods, QPE and QEE. 𝑀 :thenumberof independent terms of the Hamiltonian approximation, 𝑝 :theprecisionchosen, 𝑂(...) : asymptotic lower bound of the associated resource function. See text for details. Method Number of state preparations Coherence time Number of steps QEE 𝑂(𝑀) 𝑂(1) 𝑂(|ℎ𝑚𝑎𝑥|2𝑀𝑝−2) QPE 𝑂(1) 𝑂(𝑝−1) 𝑂(𝑝−1) A main advantage of the QEE, when compared with QPE, is that it largely reduces the need for gates, but, more important, the amount of time the entanglement over sets of qubits has to be maintained, i.e. 72 4.3. Case study: Calculation of the ground–state Stark effect in small molecules 73 the coherence time ,is 𝑂(1) ( independent of precision, 𝑝 ), which is within the grasp of existing quantum computers, while it grows linearly with 𝑝 , 𝑂(𝑝−1) , for QPE. However, QEE introduces the need to prepare more copies of the ansatz to maintain the independence of the terms in Eq. (107) – 𝑂(𝑀) against 𝑂(1) for QPE – requiring polynomially more memory, i.e. qubits. Furthermore, for the desired precision 𝑝 ,the number of necessary sampling steps is 𝑂(|ℎ𝑚𝑎𝑥|2𝑀𝑝−2) ,where ℎ𝑚𝑎𝑥 is the term with the maximum norm in the decomposition of the Hamiltonian. In summary, the QEE method reduces the required minimum coherence in the QPE, while preserving the significant quantum advantage in comparison to classical methods, introducing however a polynomial penalty, both in time and memory, i.e. number of qubits. 4.3 Case study: Calculation of the ground–state Stark effect in small molecules The work of LLoyd et al. [ 249 ] on the simulation of local Hamiltonians, initiated the modern era of quantum simulation research, by providing a realizable quantum process to the idea introduced by Feynman in 1982 [ 151 ]. The path from that point to the one in which it will be possible to simulate quantum chemistry systems, includes the independent works of Wiesner et al. [ 374 ], and Zalka et al. [ 383 ], and the work of Ortiz et al. [ 278 ], on the simulation of Fermionic Hamiltonians. Jointly, they provide the foundation for the simulation of quantum chemistry. Since then the number of quantum algorithms in quantum chemistry has grown exponentially, making it one of the disciplines where quantum computation can have more impact. From the technical point of view, a very relevant issue to the simulation of quantum chemistry systems, as seen in section 3.2, is to be able to efficiently approximate Hamiltonians for quantum chemistry using quantum gates and circuits. The processes for doing this have greatly improved throughout the years both in terms of the resources required [ 367 , 192 , 294 , 32 ] and of the Hamiltonian representation chosen [ 34 , 33 , 257 ], with an exponential advantage in many cases. The process of quantum simulation aims at the calculation of relevant properties, as for instance what was achieved in the seminal works of Lidar [ 246 ], on the calculation of thermal rates in chemical reactions, and Aspuru-Guzik et al. [ 31 ] on the calculation of ground states of simple molecules. These two works are also characteristic examples of the two types of properties of interest in quantum chemistry, the dynamic ones, which concern aspects of the evolution of the system, e.g. chemical reactions, and the static ones, which concern properties about the eigenvalues. Examples of the former can be found, for instance, in works on the process of nitrogen fixation [ 221 , 309 ], and of the latter in the characterization of molecular energy spectra [ 371 ], useful, for instance, to the optimization of molecular geometries [ 220 ]. A particular important static property is the calculation of the minimum eigenvalues, which can be calculated in many ways, including modified versions of phase estimation, the so-called iterative phase estimation [281,239]. More recently, the so-called short-term devices started to appear, and quickly gained relevance in the landscape of quantum simulation of chemistry research, namely the development of specific methods 73 4.3. Case study: Calculation of the ground–state Stark effect in small molecules 74 targeted to this kind of devices, e.g. based on the VQE method. On the field, these methods are already extensively studied, both from the theoretical and experimental points of view (see [ 90 ]foranexcellent review on the subject). The state of the art on this particular subject encompasses the calculation of the ground state of small molecules, namely, 𝐻2 , 𝐿𝑖𝐻 , 𝐵𝑒𝐻2 [ 218 ], or the charged 𝐻𝑒𝐻+ [ 326 , 287 ], in physical systems possessing 2 to 6 physical qubits. Still on this field with small quantum devices, one shall also highlight the very recent breakthrough of [ 300 ], on the simulation of the isomerization of diazene , using chains of 𝐻2molecules, on physical devices with 12 physical qubits. The hydrogen molecule is the simplest one existing in nature, and the LiH molecule is just a bit more complex than H 2 , lacking its mirror symmetry , which makes the calculation slightly more complicated. Both have been the natural test case for experimental and theoretical research, particularly concerned by the calculation of their ground state properties and the dissociation curves, which have recently been recalculated using advanced classical [ 362 ] and quantum [ 111 ] algorithms (the latter with extension to excited states). The following sections are focused on the exploration of the simulations of such two molecules hydrogen (H 2 )and lithium hydride (LiH) , under the action of strong stationary electric fields (Stark effect) [ 181 ], using the commercially available quantum computer, the IBM Q , accessed through the QuantaLab UMinho Academic Q Hub, and programmed using the QISKit platform [ 116 ]. To the best of our knowledge, it has not been studied directly in a NISQ machine and constitutes the main contribution of this work. We aim also at revisiting the necessary steps, as well as the relevant theory, for the construction of a quantum simulation for a small molecule using the VQE method, explored in section 4.2.4, as it poses many conceptual and practical challenges, far from trivial [ 371 ]. The VQE method, is in some sort, an algorithmic framework, requiring the following input: • A qubit Hamiltonian, which requires the calculation of the matrix elements of the fermionic Hamiltonian, and an appropriate mapping of the resultant matrix onto qubit Hamiltonians; •The choice of an appropriate ansatz and its implementation on quantum circuits; • The choice of a classical optimization method and the application of the VQE routine. Hence, over the next sections, we will discuss the relevant theory for these quantum simulations, namely, the Quantum Hamiltonian formalism for many-body systems, the Hartree-Fock approximation and the second quantization representation. A good introduction to the subject is offered, for instance, by [ 243 ]and[ 338 ]. The necessary items to the application of the VQE method are also reviewed, bearing in mind that the VQE method itself was already explored with detail in 4.2.4. The actual calculation of the specific matrix elements is extensive, but it is available in the associated publication [ 344 ] and in appendix A. We will also explain the mapping onto a system of qubits and the design of the quantum circuit corresponding to the initial Hamiltonian, and the execution of the VQE method to this case study, so as the correspondent results obtained. 74 4.3. Case study: Calculation of the ground–state Stark effect in small molecules 75 4.3.1 Many-particle systems The Schrödinger’s equation for a system of non-interacting particles can be decomposed into a set of uncoupled equations for each particle and the system’s WF suitably factorized. A combination of two non-interacting and non-entangled systems can be described by applying the tensor product to the two vector spaces,1with resultant basis given as follows: |Ψ(1)⟩⊗|Ψ(2)⟩=𝑀1 ∑ 𝛼 𝑀2 ∑ 𝛽𝜆𝛼𝜇𝛽|Ψ(1) 𝛼⟩⊗|Ψ(2) 𝛽⟩ =𝑀1 ∑ 𝛼 𝑀2 ∑ 𝛽𝜆𝛼𝜇𝛽|Ψ(1) 𝛼Ψ(2) 𝛽⟩. (108) In Eq. (108) , Ψ(𝑠) 𝛼 denotes an eigenfunction of a state 𝛼=1,…,𝑀𝑠 of the system Ψ(𝑠) ( 𝑠=1,2 ). The dimension of the product vector is dim(Ψ(1))∗dim(Ψ(2))=𝑀1⋅𝑀2. When the particles constituting the system are identical ,their spin becomes highly relevant. The spin, which is an intrinsic angular momentum of the particle, distinguishes between two different types of particles, bosons (e.g. photons) and fermions (e.g. electrons and protons). For fermions, the Pauli exclusion principle states that the system’s WF must be antisymmetric with respect to the permutation of any two particles. This entails an important restriction upon the WF, namely that the product vector (108) , if applied to a pair of non-interacting electrons, is not compatible with the Pauli principle. In Quantum Chemistry, a single-electron WF is called orbital [ 338 ]. One can distinguish spatial orbitals 𝜙(r) ,where 𝑟 corresponds to spatial coordinates, and spin orbitals 𝜒(x) ,where x=(r;𝑠) and 𝑠∈{↑,↓} stands for two possible orientations of electron’s spin. For two electrons, the Pauli principle means that 𝜒(x1,x2)=−𝜒(x2,x1)(109) or, equivalently, 𝜙(r1,r2)=∓𝜙(r2,r1), (110) where the upper (lower) sign corresponds to parallel (antiparallel) spins of the two electrons. If the electronelectron interaction is neglected, the correct (i.e. compatible with the Pauli principle) two-electron WF is written in the form of the so-called Slater determinant , |𝜒(1) 𝛼𝜒(2) 𝛽⟩= 1 √2∣∣∣∣𝜒𝛼(x1)𝜒 𝛽(x1) 𝜒𝛼(x2)𝜒 𝛽(x2)∣∣∣∣,(111) 1 For interacting or entangled systems, the total WF cannot be written as a product ofits parts. Entangled parts of a system, even if they do not interact physically, may not be described by a wave function, only represented by a density matrix. 75 4.3. Case study: Calculation of the ground–state Stark effect in small molecules 76 where 𝜒𝛼(x) and 𝜒𝛽(x) designate different spin orbitals. A Slater determinant can be straightforwardly generalized towards the case of 𝑁 identical non-interacting particles. It vanishes when any two electrons “occupy” the same spin orbital, as required by the Pauli exclusion principle. The Slater determinant is a simple way of constructing a many-electron WF from spin orbitals representing non-interacting electrons. Complete neglection of the Coulomb interaction between the electrons would be too crude an approximation, while solving directly the many-electron Schrödinger equation is an intractable problem. A compromise is achieved by a self-consistent field method also called Hartree-Fock (HF) approximation. An effective one-electron operator is introduced, 𝑣𝐻𝐹(x) ,calledtheFock operator, which includes, as a part of the single electron potential energy, the electron’s interaction with all other electrons whose positions are averaged under an assumption that the WF representing the system of 𝑁 electrons is a single Slater determinant. An explicit expression for 𝑣𝐻𝐹(x)will be presented below. 4.3.2 Molecular Hamiltonian and Hartree-Fock approximation The general form of a molecular Hamiltonian is (in atomic units): 𝐻mol =−𝑁 ∑ 𝑖=1 1 2∇2 𝑖−𝑀 ∑ 𝐴=1 1 2𝑀𝐴∇2 𝐴−𝑁 ∑ 𝑖=1 𝑀 ∑ 𝐴=1 𝑍𝐴 𝑟𝑖𝐴 +𝑁 ∑ 𝑖=1 𝑁 ∑ 𝑗>𝑖 1 𝑟𝑖𝑗 +𝑀 ∑ 𝐴=1 𝑀 ∑ 𝐵>𝐴 𝑍𝐴𝑍𝐵 𝑟𝐵𝐴 .(112) The first and second terms of (112)correspond to the kinetic energy of the electrons (numbered by 𝑖and 𝑗=1,…,𝑁 ) and nuclei (numbered by 𝐴=1,…,𝑀 ), respectively. The third one represents the Coulomb attraction of each electron to each nucleus with 𝑟𝑖𝐴 being the electron-nucleus distance and 𝑍𝐴 the nucleus charge. Finally, the fourth and fifth terms correspond to the repulsion among the electrons and the nuclei, respectively. It is common and well justified to use the Born-Oppenheimer approximation,which neglects the motion of the nuclei because they are much heavier than electrons, whereby the potential energy of the nucleus-nucleus interactions becomes a constant (for fixed placement of the nuclei) hence a parameter for the electron problem. With this, the electron Hamiltonian (112)reduces to: 𝐻𝑒𝑙 =−𝑁 ∑ 𝑖=1 1 2∇2 𝑖−𝑁 ∑ 𝑖=1 𝑍𝐴 𝑟𝑖𝐴 +𝑁 ∑ 𝑖=1 𝑁 ∑ 𝑗>𝑖 1 𝑟𝑖𝑗 .(113) For the H 2 molecule, the Hamiltonian (113) depends on a single parameter, the distance between the protons 𝑑 . If the lowest eigenvalue of (113) , 𝐸0(𝑑)<0 , is larger in absolute value than the proton-proton repulsion energy, 𝐸𝑟𝑒𝑝(𝑑)=𝑑−1, the molecule is bound, as illustrated in Fig. 18. 76 4.3. Case study: Calculation of the ground–state Stark effect in small molecules 77 Figure 18: Left: the hydrogen atom consists of a single electron and a proton and has the energy −0.5 a.u. in the ground state. Right: in the hydrogen molecule H 2 ,madeoftwo nuclei and two electrons, the total energy can be lower than −1 a.u., which makes the molecule stable. The Hamiltonian (113) has to be reduced to a single-electron one in order to proceed with the determination of its eigenvalues, which is achieved by means of the HF approximation, where one takes an average over the positions and spins of all but one (to be labelled by 𝑖=1 ) electron. This is done by multiplying equation (113) by |𝜒(1) 𝛼𝜒(2) 𝛽…𝜒(𝑁) 𝛾⟩ and the corresponding “bra”, both in the form of Slater determinants of dimension 𝑁 (the number of electrons in the system), and integrating over x2,x3,…,x𝑁 , which leads to ⎛ ⎜ ⎝−1 2∇2 1−𝑀 ∑ 𝐴=1 𝑍𝐴 𝑟1𝐴 +𝑣𝐻𝐹 1⎞ ⎟ ⎠𝜒𝛼(x1)=𝜖𝛼𝜒𝛼(x1), (114) where 𝑣𝐻𝐹 1 is the average potential experienced by the “chosen” electron, and 𝜖𝛼 is the single-electron energy. The HF potential can be written in the form: 𝑣𝐻𝐹 1=∑ 𝛽∫|𝜒𝛽(x2)|21 |𝑟12|𝑑x2 −∑ 𝛽∫𝜒∗ 𝛼(x1)𝜒∗ 𝛽(x2)1 |𝑟12|𝜒𝛽(x1)𝜒𝛼(x2)𝑑x2 |𝜒𝛼(x1)|2.(115) The two terms in Eq. (115)are called Coulomb and exchange energies, respectively. The latter poses the main difficulty in solving Eq. (114) ; however, its neglection (known as the Hartree approximation) results in an unsustainable error. Due to the nonlinearity of the HF approximation, the equations are solved in practice by self-consistent (iterative) methods, using a finite set of spatial basis functions, 𝜙𝜇(r) ( 𝜇=1,2, … , 𝐾 )–see,e.g.,[ 338 ]. The solution yields a set HF spin orbitals {𝜒𝛼} with corresponding energies {𝜖𝛼} , 𝛼=1,2,…,2𝐾 . The number of electrons in the system must be 2𝐾≥𝑁 . The possibilities to place 𝑁 electrons over 2𝐾 spin orbitals gives rise to (2𝐾)!/(𝑁!(2𝐾−𝑁)!) Slater determinants, one of which 77 4.3. Case study: Calculation of the ground–state Stark effect in small molecules 84 corresponding to 𝑛-particle excitations, namely,  𝑇1( 𝜃) = ∑ 𝛼,𝑎 𝜃𝑎 𝛼𝑎† 𝑎𝑎𝛼,(134)  𝑇2( 𝜃) = 1 2∑ 𝛼,𝛽; 𝑎,𝑏 𝜃𝑎𝑏 𝛼𝛽𝑎† 𝑎𝑎† 𝑏𝑎𝛼𝑎𝛽,(135) ⋯ The UCC ansatz usually retains only the two first terms in the expansion of  𝑇 , i.e. if neglects 3-particle and higher-order excitations. The expansion coefficients in (134) , (135) can be interpreted as matrix elements of a certain excitation operator between occupied and unoccupied orbitals. They can be assumed to be real , i.e., {𝜃𝑎 𝛼,𝜃𝑎𝑏 𝛼𝛽,…}∈ℝ. The anti-Hermitian combination  𝑇−  𝑇† in (133) makes the exponential operator unitary. Unitary operations are natural on quantum computers, yet the implementation into quantum circuits is not straightforward because of the non-commutation of different parts of the Hamiltonian. So, the order in which the different terms are written in the exponent is indeed important. This difficulty is bypassed by using the Trotter identity: 𝑒( 𝐴+  𝐵) =lim 𝑛→∞ [𝑒  𝐴/𝑛⊗𝑒 𝐵/𝑛]𝑛,(136) where  𝐴 and  𝐵 are two non-commuting operators, e.g.  𝐴=  𝑇1− 𝑇† 1 and  𝐵=  𝑇2− 𝑇† 2 .Thisisexactin the limit 𝑛→∞ , it is an approximation for finite 𝑛 . Different Trotter approximations of the operator (133) can be implemented on a quantum computer by transforming it into the qubit representation and using standard circuit compilation techniques for the “exponentiation” of the Pauli matrices [ 89 ]. Some examples of such circuits and comparison of results obtained for different orders ( 𝑛 ) of the Trotter approximation can be found in the work by [48]. 4.3.6 Results and Discussion We used the procedure outlined in previous sections to calculate the ground state energy (which can be straightforwardly converted into the dissociation energy) of two molecules, hydrogen (H 2 ) and lithium hydride (LiH). This has also been addressed, in which is presumably a novel result, under the action of stationary electric fields of four different magnitudes ( 𝔼= 0.0001, 0.001, 0.01, 0.1 atomic units; 1 a.u. ≈5⋅1011 V/m). These calculations were performed for the interatomic distances, 𝑑 , from 0.2 to 4 Å with the step 0.1 Å. The actual computational environment, where these experiments were conducted, was the IBM Q .Such computational environment is available remotely through the internet and can be accessed and programmed using the QISKit framework, written in the Python language. The actual code developed in this thesis is 84 4.3. Case study: Calculation of the ground–state Stark effect in small molecules 85 available from the following github repository: https://github.com/arcalab/experiments_quantum_chemistry/ tree/master/Qiskit_Programmatic_version_src (contents available upon request). It makes use notably of the QISkit and the PySCF python framework. The PySCF tool was used to specify the molecules and calculate the respective one-body and two-body integrals, encompassing already the action of electric fields, using the theory developed throughout appendix A. Both molecules were assumed to have zero global charge and spin zero; the STO-3G basis (116) was used to calculate the integrals. The evaluation of the corresponding integrals can then be reformulated into an assembling of quantum circuits, to be executed using the set of software packages available e.g. in the QISkit framework: Terra , Aer , Aqua and Ignis . The calculation of the dissociation curves requires the calculation of the ground state energies (discussed in section 4.2.4) over a range of distances, to be able to identify the minimum (bound molecule) and the asymptotics (separated atoms) ones. For this purpose, we used two methods: the Exact Eigensolver (classical matrix-multiplication method, as a benchmark) and the VQE. We used the UCC (discussed in section 4.2.5)asthe variational method , i.e. as the technique to build the ansätze for the molecules under study, and the HF approximation to obtain the initial solution for the VQE method. In this relation, several parameters had to be considered: the maximum number of iterations with the Cobyla method, 3 the optimization level (an IBM Q -specific parameter determining the degree of optimization of the circuits generated), the mapping method to use, such as the Jordan-Wigner (130) , Bravyi-Kitaev, or parity methods (see [ 89 ] for more information on these methods), each offering different (precision) / (circuit size) relationships. The technical parameters of calculation, selected after a course of trial and error, are summarized in Table 9. The use of quantum or hybrid (such as VQE) procedures in the IBM Q require that a backend is specified, i.e. an actual processing node able to execute the quantum circuits, which can be either a classical computer able to perform a simulation, with or without simulated quantum noise , or a real quantum device, with a number of qubits from 2 to 53. The results of this work were obtained using a simulator ,the qasm_simulator . 4.3.7 Results: H 2 molecule The total energy as a function of the interatomic distance, hence the molecule’s dissociation curve for different values of the electric field, is depicted in Figure 20. The effect of the electric field on the shape of the dissociation curve remains negligible at small values of the field inspected yet results in a drastic change of the 𝑑→∞ asymptotic (slope) and in a noticeable shift of the equilibrium position for 𝔼=0.1 a.u. The abrupt change in the 𝐸(𝑑) dependence slope at large distances, for very large electric field 𝔼=0.1 a.u., 3 In this quantum computation setting, an iteration in the Cobyla method is an expensive operation in terms of computation time, and therefore one may be interested in limiting the number of iterations. However, the method stops if convergence is achieved and in our particular case, the method always converged before 15000 iterations. 85 4.3. Case study: Calculation of the ground–state Stark effect in small molecules 86 Table 9: The set of technical parameters used for the quantum calculations. parameter value shots𝑎4096 Max. number of iterations of Cobyla 15000 Max. number of iterations of PySCF 5000 optimization level 3 mapping method Jordan-Wigner QISkit version 0.13.0 backend qasm_simulator (noisy simulator) 𝑎 number of times the execution of circuits is to be performed due to the stochastic nature of quantum computers Figure 20: Dissociation curve of the H 2 molecule, as calculated with a classical solver (full lines) and with the VQE (symbols connected by lines), for several values of the external electric field 𝔼 marked by color. The Stark effect (i.e. the shift of the minimum energy with electric field) is shown in the inset. Converged in an average of 40 Cobyla iterations for each point. can be related to the onset of the molecule’s dissociation, which becomes possible via tunneling through the energy barrier (blue curves in Fig. 20). 86 4.3. Case study: Calculation of the ground–state Stark effect in small molecules 87 The inspection of the VQE results, represented by symbols connected by lines in Fig. 20,revealsa numerical noise that apparently increases with the electric field magnitude. Possibly, the HF approximation used as input for the quantum calculation becomes unstable under the action of a strong electric field. The inset of Figure 20 shows the Stark effect for the molecule under study, that is, the shift between the ground-state energy calculated under the action of the electric field and at 𝔼=0 . The distance at which the respective energies have been extracted was the energy minimum position yielded by the classical solver at 𝔼=0 , 𝑑𝑒𝑞 =0.7 Å. We took this option because of the fluctuations of 𝐸(𝑑) obtained with the quantum solver. For a non-polar molecule without intrinsic dipole moment, as is the case of the H 2 , the stationary electronic Stark effect should be quadratic in the electric field. However, with the limited minimal basis used, it looks even weaker and becomes noticeable only for very strong fields. 4.3.8 Results: LiH molecule Figure 21: Same as in Fig. 20 for the LiH molecule. Converged in an average of 70 Cobyla iterations for each point. The results for the lithium hydride molecule are shown in Fig. 21, where the effect of the applied electric field is quite noticeable. The displacement of the 𝐸(𝑑) curve increases with the electric field: already for 0.01 a.u. the shift of the dissociation curve becomes appreciable. The Stark effect (inset in Fig. 21) increases with the field magnitude much faster then for the case of the H 2 molecule. This is due to the 87 4.4. Summary 88 intrinsic dipole moment the LiH molecule already possesses in the ground state. The Stark effect is linear in 𝔼 for small fields but than starts growing much faster because of the additional polarization of the ground state induced by the external field. Similar to what happens in the case of the H 2 molecule, the numerical noise is visible in the results and becomes more pronounced in stronger electrical fields. Also, the ground state energy obtained with the different solvers results in different values for the equilibrium distance, 𝑑𝑒𝑞, obtained for the quantum and classical solver, – 1.5 Å and 1.6 Å, respectively, at 𝔼=0 . Again, the latter was taken as the reference value for the Stark effect evaluation. 4.4 Summary In this chapter, the landscape of the application of quantum computers to very hard computational problems, was explored. The focus were on the optimization ones, which are pervasive in industry and can be divided in many types, from linear to convex and non-convex. It were also reviewed the quantum computational techniques and algorithms employed for these types of problems. The main contribution of this chapter was the calculation of the ground-state of two small molecules 𝐻2 and 𝐿𝑖𝐻 under the action of a strong electric field, which configures the so-called Stark effect . The study of the ground-state of such molecules was extensively studied in literature, including by using quantum computers, however, the inclusion of the electric field in the calculation of the ground-state on a quantum computer, poses many non-trivial challenges, in theory and in practice, which were not addressed directly in existent literature, but are addressed in the sequel. Hence, it was attempted to outline, in a concise way yet indicating the essential elements and the underlying theory, a representative practical resolution of this problem on the commercially available (since recently) quantum computer, IBM Q, involving: • The fermionic formulation of quantum chemistry systems; • The connection between fermionic Hamiltonians and the quantum circuits; • The state preparation, running of the algorithm and the evaluation of the results. The calculated results were obtained the quantum device simulator and comprise the total energy as a function of bond length (i.e. the dissociation curve), also under an applied stationary electric field. We also evaluated the shift of the molecule’s energy at a fixed 𝑑 (equal to the equilibrium interatomic distance) with the electric field, i.e. the stationary electronic Stark effect, supposedly quadratic in 𝔼 and small for the non-polar H 2 molecule but containing the linear term, and the much stronger in case of the polar LiH molecule. Summing up, our case study seems to provide evidence for the feasibility of the use of this quantum computer for small molecules, with a reasonable number of iterations performed. 88 5 A LOGIC FOR THE QASM PROGRAMMING LANGUAGE I would like to make a confession which may seem immoral: I do not believe absolutely in Hilbert space anymore. John von Neumann, letter to Garrett Birkhoff, 1935. In the beginning of the twentieth century, there was a line of thought on the derivation of a comprehensive theory, able to serve as a foundation for mathematics, out of logical principles and in a formal way: the so-called logicism . This endeavour aimed at replacing ad-hoc theories of mathematics, as it is the case of the Zermelo-Frankel set theory. Eventually, this endeavour lost interest, due mainly to Gödel incompleteness theorems, however, understanding logical structures behind scientific theories in order to have a deeper understanding of them is, still today, a widely used approach across many fields of science. In this regard, quantum theory is a very good example, as it possesses a very specific and insightful notion of logic, as firstly discussed by Von Neumman and Birkhoff in their seminal work of 1936 [66], where quantum logic was introduced for the first time. This logic is centred around the notion of observable properties, which organize themselves into an algebraic structure which is clearly not a Boolean algebra, due to the non-commutativity of some of them. The proper understanding of these notions originated an extensive research work, and it was particularly important in the understanding of quantum theory itself, for instance, by helping in the axiomatization of quantum theory in the formalism of Hilbert spaces. Furthermore, several approaches to the obtention of a quantum theory of gravity follow a somewhat logicist approach to physics, by attempting on defining the axiomatics for a potential unified theory, where, of course, the insights of quantum logic have played an important role. Nowadays, the establishment of proper logical structures for quantum theory is also driven by the interest in automated reasoning methods and tools to deal with quantum protocols and algorithms, which has become particularly relevant in the recent years. In this regard many logical frameworks have been proposed 89 5.1. Standard quantum logics 90 coming from different origins, from purely algebraic terms and category theory, to modal and linear logic. In this chapter we revisit the relevant background to understand quantum logic, in sections 5.1 and 5.2, and propose a logic able to deal with the QASM programming language, a quantum programming language involving quantum and classical procedures. An early version of this work, presented in sections 5.3,5.4 and 5.5, appeared in the Dali 2019 workshop [343]. 5.1 Standard quantum logics In 1936 Von Neumman and Birkhoff , published the seminal paper [ 66 ] on what would become quantum logic, focusing on the study the algebraic properties of quantum propositions. They consider that the latter correspond to the tests that can be performed experimentally, i.e. the so-called testable properties . Mathematically, such properties are closed linear subspaces of Hilbert spaces, which can be defined as follows: Definition 5.1.1. (Orthogonality and Orthocomplement). Let ℋ be a complex Hilbert space. Two vectors 𝑥,𝑦∈ℋ are said to be orthogonal, denoted 𝑥⊥𝑦 ,iff ⟨𝑥∣𝑦⟩=0 .Givenasubset 𝑋⊆ℋ,theorthocomplementofX,denotedby∼𝑋,isgivenas: ∼𝑋={𝑦∈ℋ|𝑦⊥𝑥for all 𝑥∈𝑋}. Definition 5.1.2. (Closed Linear Space) Let 𝑃 be a subspace of a complex Hilbert space ℋ . Pisaclosedlinearsubspaceif ∼∼𝑃=𝑃. Taking testable properties as propositions, the logic develops as expected. Negation is given by the orthocomplement of a proposition, denoted ∼𝜙 ,where 𝜙 is a proposition, and conjunction, denoted 𝜙∧𝜓 , is given by the intersection of the two closed linear subspaces. The definition of disjunction, slightly different from the classical one, is given by the quantum join: the closed linear subspace defined by the classical union of two propositions. Definition 5.1.3. (Quantum Join) Let ℋ be a complex Hilbert space and let 𝐾,𝐿⊆ℋ be two subsets. The quantum join of 𝐾and 𝐿,denoted𝑘⊔𝐿is given by 𝐾⊔𝐿=∼∼(𝐾∪𝐿). (137) A minimalistic quantum logic builds on these operations, according to the following syntax: 𝜙∶∶=⊥|∼𝜙|𝜙∧𝜙|𝜙⊔𝜙, 90 5.1. Standard quantum logics 91 where ⊥ is the property false , corresponding to the empty closed Hilbert space. Valid propositions, as usual in logic, possess an order relationship, based on the fact that some propositions can be embedded on each other. For instance, if 𝐴∧𝐵 is true, one necessarily concludes that 𝐴 is true, and hence one states that 𝐴∧𝐵≤𝐴 ,i.e. 𝐴 is more general and less restrictive. In fact, the whole set of propositions can be arranged in a bounded pre-order structure, denominated lattice (see definition 5.1.4). The most distinctive property of quantum lattices of propositions, is that the distributivity law, one of the cornerstones of classical logic, does not hold, 𝑃∧(𝑄⊔𝑅)≠(𝑃∧𝑄)⊔(𝑃∧𝑅), due to the non-commutative nature of observable properties of quantum mechanics, i.e. the order in which observation are made matters, as presented in example 5.1.1. Example 5.1.1. Due to the Heinsenberg’s uncertainty principle it is well known that it not possible to have, simultaneously, definite values for momentum and position. From this, it is possible to build an example where the distributivity law fails. Consider the following propositions, •P-|𝑝|≤1(units are irrelevant), •Q-𝑥≤0and •R-𝑥≥0 where 𝑥 regards the position of a particle and 𝑝 its momentum. From quantum mechanics, it can be stated that if 𝑃is true then (𝑃∧𝑄)is false, (𝑃∧𝑅)is false, (𝑃∧𝑄)⊔(𝑃∧𝑅)is also false, (𝑄⊔𝑅)is true, and 𝑃∧(𝑄⊔𝑅)is also true. Hence, 𝑃∧(𝑄⊔𝑅)≠(𝑃∧𝑄)⊔(𝑃∧𝑅) and in this particular case the distributivity law does not hold. This fact has important implications in the way one can build inference rules for this logic, i.e. the traditional modus ponens is not valid for the most generalized version in infinite dimensions of quantum logic, however weaker forms of the distributive law are possible in certain situations. In particular, the modular law , has been shown to hold for finite dimensional Hilbert spaces If 𝐴≤𝐵then 𝐴∨(𝐵∧𝐶)=(𝐴∨𝐵)∧(𝐴∨𝐶), (138) 91 5.1. Standard quantum logics 92 so as the orthodomular law for Hilbert spaces of arbitrary dimension, as shown by Husimi [201], If 𝐴≤𝐵and ∼𝐴≤𝐶then ∼𝐴∨(𝐵∧𝐶)=(𝐴∨𝐵)∧(𝐴∨𝐶). (139) These observations suggest that quantum logic is substantially harder for infinite dimensions. From the algebraic perspective, quantum logic presents itself in a ortholattice structure (see definitions 5.1.4 and 5.1.5), where the commutative law does dot hold, which prevents the distributive law to hold, as it would do in a Boolean algebra (definition 5.1.6). Definition 5.1.4. (Lattice) Alatticeisastructureℒ=(∧,∨)where the following laws hold: 1. 𝐴∧𝐴=𝐴;𝐴∨𝐴=𝐴(idempotence) 2. 𝐴∧𝐵=𝐵∧𝐴;𝐴∨𝐵=𝐵∨𝐴(commutativity) 3. 𝐴∧(𝐵∧𝐶)=(𝐴∧𝐵)∧𝐶;𝐴∨(𝐵∨𝐶)=(𝐴∨𝐵)∨𝐶(associativity) 4. 𝐴∧(𝐴∨𝐵)=𝐴;𝐴∨(𝐴∧𝐵)=𝐴(absorption) Definition 5.1.5. (Ortholattice) An ortholattice is a lattice ℒ=(∼,∧,∨,0,1)where the following laws hold: 1. Has a least element (0) and greatest element (1), thus called bounded; 2. Complemented, every element A has a orthocomplement ∼𝐴 ,( 𝐴∨ ∼ 𝐴 = 1 ), (𝐴∧∼𝐴=0), 3. which is an involution (∼∼𝐴=𝐴). Definition 5.1.6. (Boolean algebra) ABooleanalgebraisanortholattice ℒ=(∼,∧,∨,0,1) , where the distributivity laws hold: 1. 𝐴∧(𝐵∨𝐶)=(𝐴∧𝐵)∨(𝐴∧𝐶); 2. 𝐴∨(𝐵∧𝐶)=(𝐴∨𝐵)∧(𝐴∨𝐶) Given this, ortholattices seem to cope with what needs quantum logic, however, the fact that a weaker form of the modular law hold in general, leads to a more appropriate algebraic structure - that of a orthomodular lattices (definition 5.1.7) - which, arguably, seems to be the right structure for quantum propositions [ 217 ]. 92 5.2. Dynamic aspects in Quantum Logic 93 Definition 5.1.7. (Orthomodular lattice) An orthomodular lattice is an ortholattice ℒ=(∼,∧,∨,0,1) , where the orthomodular law (eq (139)) holds: If 𝐴≤𝐵then 𝐴∨(𝐴∧∼𝐴)(Weak modularity) .(140) Yet, while orthomodular lattices capture accurately the structure of quantum tests represented in Hilbert spaces , there is still a major issue preventing them to be equivalent to Hilbert spaces as a foundational structure of quantum mechanics: the inexistence of a tensor product [ 301 ]. This led to extensive research work to find the ”right” logical structure of quantum mechanics, from which relevant lines of work have arisen, as for instance orthoalgebras , introduced by Randall and Foulis [ 159 ], for which a tensor structure exists [ 160 ], which, however, possess other issues [ 173 ]. Relevant lines of work are given, for instance, by effect algebras [158,123], and partial Boolean algebras, introduced by Kochen-Speckter [232,231]. Excellent reviews of these developments are available, for instance, in [ 157 , 124 ], but so far no algebraic structure, based on the algebraic properties of quantum propositions, is able to cope completely with all the features of quantum mechanics, obtained, for instance, in Hilbert spaces. One of the applications of quantum logic was on the axiomatization of quantum mechanics, from which a better characterization of the Hilbert spaces suitable for quantum mechanics was obtained. The work started by Piron in 1964 [ 289 ], where five axioms of quantum mechanics in Hilbert spaces were established and was completed many years later thanks to the work of Mayan and Soler [334,15]. Further, there is also some work attempting to follow a similar approach to find the quantum theory of gravity out of logical principles see, in particular, work reported by Isham [204], or Hartle [166]. 5.2 Dynamic aspects in Quantum Logic The logical apparatus discussed in the previous sections aims exclusively at reasoning over the static perspective of quantum systems. However, to reason about quantum evolution, which possess quantum programming as a subcase, one is mostly interested in the dynamic perspective. To the best of our knowledge, no dynamical logical system based on the notion of logic given by observable properties ,is able to deal with quantum systems of arbitrary dimension, in a complete way. The reasons for this may have to do exactly with the issues raised in previous section: the lack of a satisfactory notion of tensor for orthomodular lattices and the issues existent in the structures that do possess tensors. However, there are complete reasoning systems, particularly those akin to the formalisms of quantum mechanics, Hilbert spaces and density operators, where the notions of tensor and compositionality come naturally, as it happens for instance in the extensive field of categorical quantum mechanics (CQM). Such formalism is focused on the abstract algebraic properties of such spaces and offer a wide range of tools to validate quantum programs and protocols [11,110]. 93 5.3. A dynamic logic for QASM programming language (LQASM) 100 quantum amplitude of a proposition on a state, i.e. the result of the internal product operator in a state ,i.e. ⟨𝜑|𝑠⟩ ,where 𝑠 is a state. The [𝜋] has the usual meaning of ”the proposition 𝜑 necessarily holds upon the execution of program 𝜋 , program 𝜋 halts” and the usual minimal set of Boolean connectives is included. Finally, in table 10 some abbreviations are defined. ⊥∶∶=𝜑∧¬𝜑 ⊥∶=¬⊤ ⟨𝜋⟩𝜑∶=¬[𝜋]¬𝜑 3𝜑∶=⟨𝜑?⟩⊤ ⇤𝜑∶=¬3¬𝜑 𝐸𝜑∶=33𝜑 𝐴𝜑∶=¬𝐸¬𝜑 𝜑∨𝜓∶=¬(¬𝜑∧¬𝜓) 𝜑→𝜓∶=¬(𝜑∧¬𝜓) 𝑝<𝑅𝜑∶=¬𝑝≥𝑟𝜑 𝑝≥𝑟𝜑∶=¬𝑝≤𝑅𝜑 Table 10:Allowed abbreviations 5.3.3 Discussion The logic presented in this chapter (LQASM) targets the QASM language, which to the best of our knowledge, has not been addressed directly in literature before. The challenge offered by the QASM language revolve around the need for the coexistence of classical and quantum information, so as of purely unitary programs and classical ones. More precisely, the challenges of the design of LQASM translate into the following concrete requirements: 1. Existence of classical and purely unitary operations, which must behave as expected when inciding over quantum bits; 2. Coexistence of classical and quantum tests of bits and qubits, respectively, where the former ones conserve the state of the bit being tested, while the latter yield a collapse effect; 3. Existence of quantum measurements, which are interpreted as a classical probabilistic combination of the effects of two complementary quantum tests, hence preserving the probabilistic nature of the measurement results; 4. Existence of if statements with probabilistic control variables, as a consequence of requirement 3). 5. More generally, existence of two types of information, classical and quantum, where the latter can copied, but does not support quantum phenomena such as interference and entanglement , and the former behaves exactly as opposite. From a semantic perspective these requirements can naturally be accommodated in a density operator setting, which supports, by definition, all possible types of physically sound operators, which includes unitary operators and all sorts of measurements. A Floyd-Hoare logic for quantum programs based on this semantics 100 5.3. A dynamic logic for QASM programming language (LQASM) 101 has been already developed (see Ying [ 380 ]), however, there is a slight difference between the such logic and LQASM, which has to do with requirement 2), as non-destructive tests are not directly supported in a density operator setting, and also, in the logic of Ying [380]. However, the logic under development here is closer to the quantum dynamic logic for quantum programs developed in Baltag et al. [ 38 , 44 ]. The semantic models presented in such logics, do not support naturally the requirements 1) to 5), as both the states and transitions are purely quantum, however as quantum information can be used to simulate the classical one, it provides an excellent starting point. The contribution of this chapter goes along these lines, i.e. of extending the model introduced in [ 38 ], to support requirements 1) to 5). In terms of expressibility the advantages of this logic are to preserve the probabilistic nature of quantum results, which can be useful in a wide range of quantum protocols, such as the leader election, and further it provides a more flexible model to accommodate logics involving non-trivial classical programs, rather than simple if statements. Along the next few sections the solutions for these problems are discussed. 5.3.4 Semantics The semantics of this logic is given in terms of a labelled transition system [198], defined by a tuple : 𝑀=(𝑆,[[.]]𝑝∶𝒜𝑝→2𝑆,[[.]]𝜋∶𝒜𝜋→2𝑆×𝑆)(143) where 𝑆 is a set of states and [[.]]𝑝 and [[.]]𝜋 are meaning functions. The former function gives meaning to propositions, i.e. it is typed as a function from the set of well-formed syntactic expressions of propositions ( 𝒜𝑝 )tothe powerset of states, and the latter one does the same for programs, typing as a function from the set of well-formed syntactic expressions of programs ( 𝒜𝜋 ), to the powerset of the pairs of sets of states. Hence programs are deterministic. For simplification reasons we omit the identifiers of meaning functions, 𝑝and 𝜋, which shall be infered from context. 5.3.5 The state space A state of a program in the QASM language is defined by its classical and quantum components. Each such component is divided into one or many independent registers, each one composed of a set of quantum or classical bits. The set of possible states for a quantum bit is given, as described in section 2.4, by all the normalized states in a Hilbert space of dimension 2, denoted here as ℋ2 𝑖 where 𝑖 is the qubit index, but the actual state space of 𝑛 qubits is given by all normalized states of ℋ2𝑛 , which encompass, all non-separable states existent in the 𝑛 qubit space. Normalization of quantum states comes from the Born rule and the space state can be expressed as: 101 5.3. A dynamic logic for QASM programming language (LQASM) 102 ℋ2𝑛 ≡∑ 𝑖∈{0,1}𝑛𝜆𝑖|𝑖⟩where ∑ 𝑖𝜆𝑖∗𝜆† 𝑖=1. (144) Due to the existence of stochastic instructions, i.e. measurements , we provide a classical probabilistic semantics to classical bits .AccordingtoKozenetal.[ 235 ], the semantics of probabilistic programs is founded in the realm of measurable functions, where, for instance, the states of such programs are given by a measurable function, on the possible tests 1 over the program variables. In the case of a probabilistic bit , the state 𝑠is defined by a function typed as 𝜇𝑠∶{0,1}→[0,1]. Here and in an equivalent way, we represent a stochastic bit by an Hilbert space of dimension two over complex numbers, of basis {0,1} ,where (0)=⎛ ⎜ ⎝1 0⎞ ⎟ ⎠ and (1)=⎛ ⎜ ⎝1 0⎞ ⎟ ⎠ . Valid vectors are normalized linear combinations 𝛼(0)+𝛽(1) with 𝛼,𝛽∈ℂ𝟚 ,i.e.elementsoftheform ⎛ ⎜ ⎝𝛼 𝛽⎞ ⎟ ⎠ , where the condition 𝛼2+𝛽2=1 holds, which we denote as 𝒞2 𝑖 . This results in the following global state space, gathering several quantum and classical registers: ℋ2𝑛 ×ℋ2𝑛 ⏟⏟⏟⏟⏟ quantum registers ×…×𝒞2 𝑖×…×𝒞2 𝑖 ⏟⏟⏟⏟⏟⏟⏟ classical register ×… ⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟ 𝑆 .(145) It is pretty straightforward that Cartesian product in classical registers, guarantee that states are always separable (convex), contrary to what happens in qubits. In conclusion the state space of a QASM program is given by the Cartesian product of the possible states of the independent quantum and classical registers, called Registers, where in the former the set of states is given by the tensor product of quantum bits, and in the latter by the possible distributions definable over the configurations of the classical bits . The number of qubits and bits available in each register is defined by reg_size. More concretely, the state space can be written as 𝑆≡ ∏ quantum register∈𝑅𝑒𝑔𝑖𝑠𝑡𝑒𝑟𝑠 ℋ2∗𝑟𝑒𝑔_𝑠𝑖𝑧𝑒 ×∏ classical register∈𝑅𝑒𝑔𝑖𝑠𝑡𝑒𝑟𝑠 ∏ 𝑖∈reg_size 𝒞2 𝑖 For expressability purposes, the state space is represented by two families of functions 𝜋𝑞 𝑟𝑖1,𝑟𝑖2,…,𝑟𝑖𝑛∶𝑆→ ℋ2𝑛 , which yield the current state of the list of qubits given by 𝑟𝑞 𝑖1,𝑟𝑞 𝑖2,…,𝑟𝑞 𝑖𝑛 and 𝜋𝑐 𝑟𝑖1,𝑟𝑖2,…,𝑟𝑖𝑛∶𝑆→ 1 Tests correspond to the 𝜎-algebra over the valuation set 𝒞 = {0,1} of a single classical bit, the set of possible states corresponds to the distributions definable on the tests. For valuations with a discrete domain, it corresponds to the powerset 2𝒞. Tests form a Boolean algebra. 102 5.3. A dynamic logic for QASM programming language (LQASM) 103 ∏𝑛 𝑖𝒞𝑖 2 , which behaves similarly for the classical bits. A particular application of this are the functions 𝜋𝑞 𝑟𝑖∶𝑆→ℋ2and 𝜋𝑐 𝑟𝑖∶𝑆→𝐶2, which yield the state of a particular quantum and classical bits. 5.3.6 Propositions The approach proposed in this work, based on keeping two different types of information, classical and quantum in the logical system, may be slightly problematic in what concerns the semantics of propositions. As usual, the semantics of a proposition corresponds to the set of states where it holds, hence 𝑝∶2𝑆. However, the different types of information influence the way propositions are interpreted. Definition 5.3.1. Semantics for proposition constructors. The definition of the primitive connectives is similar to the one used in modal logics, corresponding to set operations as follows: 1. [[𝑝]]⊆2𝑆 2. [[⊤]]=𝑆 3. [[𝑖𝑞 𝑟𝑖]] with 𝑖∈{0,1}={𝑠∈𝑆|𝜋𝑞 𝑟𝑖(𝑠)=|𝑖⟩} 4. [[0𝑐 𝑟𝑖]] = {𝑠 ∈ 𝑆|𝜋𝑐 𝑟𝑖(𝑠) = (0)} ,i.e. theclassical 0 is a distribution, where 0 has probability 1. 5. [[1𝑐 𝑟𝑖]] = {𝑠 ∈ 𝑆|𝜋𝑐 𝑟𝑖(𝑠) = (1)} ,i.e. theclassical 1 is a distribution, where 1 has probability 1. 6. [[𝜑1∧𝜑2]]=[[𝜑1]]∩[[𝜑2]] 7. [[¬𝜑]]={𝑠|𝑠∉[[𝜑]]}=𝑆−[[𝜑]] where 𝑆−[[𝜑]]stands for 𝑆except [[𝜑]],i.e.thecomplementof[[𝜑]]in S. 8. [[[𝜋]𝜑]]={𝑠|∀𝑢∶(𝑠,𝑢)∈[[𝜋]]⇒𝑢∈[[𝜑]]} The set of states where the proposition 𝜑 holds upon the execution of program 𝜋 (The semantics of programs 𝜋is given in section 5.3.7). 9. [[𝑃≥𝑟𝜑]]={𝑠|⟨𝑠∣𝜑⟩⟨𝜑∣𝑠⟩≥𝑟}. The set of states where quantum proposition component 𝜑 holds with probability greater than r. 103 5.3. A dynamic logic for QASM programming language (LQASM) 104 10. [[𝒜=𝜆𝜑]]={𝑠|⟨𝜑∣𝑠⟩=𝜆} . The states where the amplitude of a certain proposition is equal to a given constant 𝜆. 5.3.7 Program semantics The semantics of programs is given by a function from the set of well-formed programs to the power set of pairs of states, which entails the accessibility relation , i.e. the set of valid transitions between pairs of states (source to target) under the action of programs: [[.]]∶𝒜𝜋→2𝑆×𝑆 .(146) A particular type of programs of this language are unitary programs, 𝑢, whose meaning reads as •[[𝑢]]={(𝑠,𝑡)∈𝑆×𝑆|𝑡∈[[𝑢(𝑠)]]∧𝑠∈[[𝑢−1(𝑡)]]} where 𝑢(𝑠) , is the application of the unitary operator 𝑢 to a state 𝑠 , for instance, the Hadamard gate acting over state |0⟩ ,i.e. 𝐻.|0⟩ . These rules apply to unitary operators ℎ𝑖 , 𝑧𝑖 , 𝑥𝑖 or 𝑐𝑛𝑜𝑡𝑖𝑗 which correspond to the quantum gates 𝐻 , 𝑍 , 𝑋 ,and 𝐶𝑁𝑂𝑇 , whose meaning was discussed in section 2.4.2.Indexes 𝑖,𝑗 correspond to the qubit indexes in the qubit array. It can be assumed that the unitary operator can be extended to the unaffected qubits by tensoring it with the unity operators, e.g. the semantics of a ℎ0 operator just affecting the first qubit in a system of two qubits, 0and 1, reads as: 𝐻⊗𝐼. The language also allows the existence of non-unitary operations, such as the creation of registers, classical and quantum, measurements of qubits, as well as if statements. Consider first the definition of quantum and classical registers, whose semantics read as follows: •[[creg r [size]]]={(𝑠,𝑡)∈𝑆×𝑆|𝑡∈[[⋀𝑖∈size 0𝑐 𝑟𝑖]]}(Classical registry creation) •[[qreg r [size]]]={(𝑠,𝑡)∈𝑆×𝑆|𝑡∈[[⋀𝑖∈size 0𝑞 𝑟𝑖]]}(Quantum registry creation) Tests , both quantum and classical , possess a significant diference between each other: the former has a destructive effect on the state (the quantum bit it incides), while the latter conserves the state (the classical bit it insides). Their semantics reads as follows: •[[𝑖𝑑𝑞 𝑖== 𝑎]]={(𝑠,𝑡)∈𝑆×𝑆|𝑡∈||𝑎𝑞 𝑖𝑑𝑖⟩⟨𝑎𝑞 𝑖𝑑𝑖|(𝑠)/⟨𝑠|𝑎𝑞 𝑖𝑑𝑖⟩⟨𝑎𝑞 𝑖𝑑𝑖|𝑠⟩}(quantum test) •[[𝑖𝑑𝑐 𝑖== 𝑎]]={(𝑠,𝑡)∈𝑆×𝑆|𝑠∈[[𝑃=𝑥𝑎𝑖𝑑𝑐 𝑖]]∧𝑡∈[[𝑃=𝑥𝑎𝑖𝑑𝑐 𝑖]]}(classical test) where 𝑎∈0,1 . The semantics of the measurement of quantum bit, can be understood as the branching of state into ”alternative worlds”, one where the test correspoding to 0 succeeded, with the probability of success of the test stored in the classical bit and the same for 1 , which is expressed as a union of two sets as follows: 104 5.4. Some valid rules and examples 105 •[[measure 𝑞𝑖→𝑐𝑖]]={(𝑠,𝑡)∈𝑆×𝑆|(𝑠,𝑡)∈[[𝑖𝑑𝑞 𝑖==0]]∧𝑡∈[[𝑃=𝑒10𝑐 𝑐𝑖]]where 𝑒1= ⟨𝑠|0𝑞 𝑖𝑑𝑖⟩⟨0𝑞 𝑖𝑑𝑖|𝑠⟩}∪{(𝑠,𝑡)∈[[𝑞𝑞 𝑖==1]]∧[[𝑃=𝑒21𝑐 𝑐𝑖]]where 𝑒2=⟨𝑠|1𝑞 𝑖𝑑𝑖⟩⟨1𝑞 𝑖𝑑𝑖|𝑠⟩} (Measurement) If statements also consist of two alternative programs: one where, simultaneously, the classical test and the program effect holds, and the one where the classical test does not hold and the state remains unaltered, as follows: •[[if 𝑖𝑑𝑐 𝑖== b 𝜋]]={(𝑠,𝑡)∈𝑆×𝑆|(𝑠,𝑡)∈[[∣𝑏⟩𝑖𝑑𝑐 𝑖⟨𝑏∣𝑖𝑑𝑐 𝑖;𝜋]]∧(𝑠,𝑡)∈[[𝑖𝑑𝑐 𝑖==𝑏]]}∪ {(𝑠,𝑡)∈[[∣¬𝑏⟩𝑖𝑑𝑐 𝑖⟨¬𝑏∣𝑖𝑑𝑐 𝑖;𝑠𝑘𝑖𝑝]]∧(𝑠,𝑡)∉[[𝑖𝑑𝑐 𝑖==𝑏]]} ,where 𝑏∈{0,1} and skip is the identity operator. Finally, the language also allows the sequencing (composition) of programs, for that the accessibility relationship , reads as follows: •[[𝜋1;𝜋2]]={(𝑠,𝑢)∈𝑆×𝑆|∃𝑡∈𝑆∶(𝑠,𝑡)∈[[𝜋1]]𝑡∧(𝑡,𝑢)∈[[𝜋2]]} 5.4 Some valid rules and examples In this section, we illustrate the semantics defined in the previous sections, by the proof of soundness of several rules and validities, as well as the correctness of both a coin tossing program and the teleportation protocol, expressed in the fragment of the QASM programming language. The proof strategy of showing the validity of a formula 𝜑 consists showing it holds in every possible state, in a state-based model as proposed in previous section, denoted as 𝑀 : ∀𝑠∈𝑆∶𝑀,𝑠⊧𝜑 ( ⊧ means that property 𝜑 is true in state s), or, equivalently, [[𝜑]]=[[⊤]]. 5.4.1 States, amplitudes and probabilities States can be defined by the amplitude operator for all elements of the basis of a quantum state, for instance, for a single qubit, [[𝒜𝜆10𝑞 𝑟𝑖∧𝒜𝜆21𝑞 𝑟𝑖]]={𝑠∈𝑆|𝜋𝑟𝑖(𝑠)=𝜆1|0⟩+𝜆2|1⟩}. The proof of this goes as follows, and makes use of the Born rule: Proof: [[𝒜𝜆10𝑞 𝑟𝑖∧𝒜𝜆21𝑞 𝑟𝑖]]={𝑠∈𝑆|𝜋𝑟𝑖(𝑠)=𝜆1|0⟩+𝜆2|1⟩} ⇔ [[𝒜𝜆10𝑞 𝑟𝑖]]∩[[𝒜𝜆21𝑞 𝑟𝑖]]={𝑠∈𝑆|𝜋𝑟𝑖(𝑠)=𝜆1|0⟩+𝜆2|1⟩} 105 5.4. Some valid rules and examples 106 ⇔(by the Born rule, see equation 144) {𝑠∈𝑆|𝜋𝑞 𝑟𝑖∑𝑖𝛼𝑖|𝑛⟩with ∑𝑖𝛼𝑖∗𝛼𝑖†=1}∩{𝑠∈𝑆|𝜋𝑞 𝑟𝑖(𝑠)=𝜆1|0⟩}∩{𝑠|𝜋𝑞 𝑟𝑖(𝑠)=𝜆2|1⟩}= {𝑠|𝜋𝑟𝑖(𝑠)=𝜆1|0⟩+𝜆2|1⟩} ⇔ {𝑠∈𝑆|𝜋𝑟𝑖(𝑠)=𝜆1|0⟩+𝜆2|1⟩}={𝑠∈𝑆|𝜋𝑟𝑖(𝑠)=𝜆1|0⟩+𝜆2|1⟩} ⇤ This fact can also be generalized to systems of arbitrary dimension. Also an interesting observation that can be, comes from the need of normalization of bits/qubits: 𝑃=𝑥𝑎𝑟𝑖→𝑃=1−𝑥¬𝑎𝑟𝑖,where 𝑎∈{0,1}. (147) This also leads to the conclusion that 𝑃=𝑥𝑎𝑟𝑖∨𝑃=1−𝑥¬𝑎𝑟𝑖=𝑃=𝑥𝑎𝑟𝑖∧𝑃=1−𝑥¬𝑎𝑟𝑖(148) ,and the proof reads as follows: Proof: 𝑃=𝑥𝑎𝑟𝑖∨𝑃=𝑥𝑎𝑟𝑖=𝑃=𝑥𝑎𝑟𝑖∧𝑃=1−𝑥¬𝑎𝑟𝑖 ⇔(by the condition of equation (147)) 𝑃=𝑥𝑎𝑟𝑖∧𝑃=1−𝑥¬𝑎𝑟𝑖∨𝑃=1−𝑥¬𝑎𝑟𝑖∧𝑃=𝑥𝑎𝑟𝑖=𝑃=𝑥𝑎𝑟𝑖∧𝑃=1−𝑥¬𝑎𝑟𝑖 ⇔ 𝑃=𝑥𝑎𝑟𝑖∧𝑃=1−𝑥¬𝑎𝑟𝑖=𝑃=𝑥𝑎𝑟𝑖∧𝑃=1−𝑥¬𝑎𝑟𝑖⇤ Furthermore, the probability of a test inciding over a classical variable can be applied to the whole state: (𝑃=𝑥𝑎𝑐 𝑟𝑖∧𝜑)→𝑃=𝑥(𝑎𝑐 𝑟𝑖∧𝜑) (149) The veracity of this statement comes from the fact that the tests over a classical variable are always compatible with any other test that can be made in the system and hence the normal classical probability laws apply in these cases. 5.4.2 Creation of registers The creation of registers, quantum or classical, is one of the possible actions of the QASM language, which sets them immediately to 0in both cases. Therefore, the following rules hold: •[creg r [size]](⋀𝑖∈size 0𝑐 𝑟𝑖) •[qreg r [size]](⋀𝑖∈size 0𝑞 𝑟𝑖) 106 5.4. Some valid rules and examples 107 In both cases 𝑟 corresponds to an arbitrary register description. We now give the proof of these rules, which are quite similar from the semantics defined in previous section. Proof: Proof of rule creg [[[creg r [size]](⋀𝑖∈size 0𝑐 𝑟𝑖)]] =(by the definition of the dynamic operator [𝜋]𝜙) {𝑠∈𝑆|∀𝑡∶(𝑠,𝑡)∈[[creg r [size]]]⇒𝑡∈[[(⋀𝑖∈size 0𝑐 𝑟𝑖)]]} =(by the definition of the creation of classical register) {𝑠∈𝑆|∀𝑡∶𝑡∈[[(⋀𝑖∈size 0𝑐 𝑟𝑖)]](1) ⇒𝑡∈[[(⋀𝑖∈size 0𝑐 𝑟𝑖)]](2)} =(it can be easily verified that sets referred by (1),(2) are non-empty) {𝑠∈𝑆|𝑡𝑟𝑢𝑒}=𝑆=[[⊤]] ⇤ Proof of rule qreg is exactly the same of creg , it is just necessary to use the definition of the creation of quantum register rather than classical register. 5.4.3 Unitary gates In essence quantum programs are unitary gates, which, however while involving most of the times, one or two qubits. The proofs for these instructions are made in the semantic setting. More a demonstrative example we show the following validity 0𝑞0→[ℎ𝑞0](𝒜1 √20𝑞0∧𝒜1 √21𝑞0), which we denote h0. Proof: Proof of h0 [[0𝑞 𝑞0→[ℎ𝑞0](𝒜=1 √20𝑞 𝑞0∧𝒜=1 √21𝑞 𝑞0)]] =(by the definition of implication) [[¬(0𝑞 𝑞0∧¬([ℎ𝑞0](𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0)))]] =(by the modal negation ¬[𝜋]𝜙=¬(¬⟨𝜋⟩¬𝜙)) [[¬(0𝑞 𝑞0∧(⟨ℎ𝑞0⟩¬(𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0)))]] =(by the definition of the dynamic operator ⟨𝜋⟩𝜙) 𝑆−([[0𝑞 𝑞0]]∩{𝑠∈𝑆|∃𝑡∶(𝑠,𝑡)∈[[h𝑞0]]⇒𝑡∉[[(𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0)]]) = 𝑆−{𝑠∈𝑆|∃𝑡∶𝑠∈[[0𝑞 𝑞0]]∧(𝑠,𝑡)∈[[h𝑞0]]⇒𝑡∉[[(𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0)]]} =(by the definition of the h instruction and the semantics of state s) 𝑆−{𝑠∈𝑆|∃𝑡∶𝜋𝑞0(𝑠)=|0⟩∧𝜋𝑞0(𝑡)=𝐻|0⟩⇒𝑡∉[[(𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0)]]} =(the action of the h instruction results in the state |+⟩) 107 5.4. Some valid rules and examples 108 𝑆−{𝑠∈𝑆|∃𝑡∶𝑠∈𝜋𝑞0(𝑠)=|0⟩∧𝜋𝑞0(𝑡)=𝒜1 √2(|0⟩+|1⟩)⇒𝑡∉[[(𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0)]]} =(by the definition of the amplitude operator on the |+⟩state) 𝑆−{𝑠∈𝑆|∃𝑡∶𝑠∈[[0𝑞 𝑞0]](1) ∧𝑡∈[[(𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0]](2) ⇒𝑡∉[[𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0]](2)} =(it can be easily verified that sets referred by (1),(2) are non-empty) [[¬⊥]]=[[⊤]] ⇤ 5.4.4 Measurements Measurements are also an important part, and in this sequel, only single qubit measurements are allowed, causing the ramification of into two consistent worlds each with the probability of obtaining one and zero, causing the transference of probability distribution from the qubit to the classical bit. An example of this is given by the validity (𝒜1 √20𝑞0∧𝒜1 √21𝑞0)→[meas 𝑞0to 𝑐0](𝑃=0.50𝑐0∧𝑃=0.51𝑐0) , which we denote m1. Proof: Proof of validity m1 [[(𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0)→[meas 𝑞0to 𝑐0](𝑃=0.50𝑐 𝑐0∧𝑃=0.51𝑐 𝑐0)]] =(by the definition of implication) 𝑆−([[(𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0)]]∩[[¬[meas 𝑞0to 𝑐0](𝑃=0.50𝑐 𝑐0∧𝑃=0.51𝑐 𝑐0)]]) =(by the modal negation ¬[𝜋]𝜙=¬(¬⟨𝜋⟩¬𝜙)) 𝑆−([[(𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0)]]∩[[⟨meas 𝑞0to 𝑐0⟩¬(𝑃=0.50𝑐 𝑐0∧𝑃=0.51𝑐 𝑐0)]]) =(by the definition of the dynamic operator ⟨𝜋⟩𝜙) 𝑆−{𝑠∈𝑆|∃𝑡∶𝑠∈[[(𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0)]]∧(𝑠,𝑡)∈[[[meas 𝑞0to 𝑐0]]]⇒𝑡∉[[(𝑃=0.50𝑐 𝑐0∧ 𝑃=0.51𝑐 𝑐0)]]} =(by the definition of measurement) 𝑆−({𝑠 ∈ 𝑆|∃𝑡 ∶ 𝑠 ∈ [[(𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0)]]∧(𝑠,𝑡) ∈ ({(𝑠,𝑡)|𝑡 ∈ [[𝑞𝑞 0== 0]]∧𝑡 ∈ [[𝑃=0.50𝑐 𝑐0]]}∪{(𝑠,𝑡)|𝑡∈[[𝑞𝑞 0==1]]∧𝑡∈[[𝑃0.51𝑐 𝑐0]]})⇒𝑡∉[[(𝑃=0.50𝑐 𝑐0∧𝑃=0.51𝑐 𝑐0)]]}) = 𝑆−({𝑠∈𝑆|∃𝑡∶𝑠∈[[(𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0)]]∧𝑡∈[[𝑃=0.50𝑐 𝑐0∨𝑃=0.51𝑐 𝑐0]]⇒𝑡∉[[(𝑃=0.50𝑐 𝑐0∧ 𝑃=0.51𝑐 𝑐0)]]}) =(as exposed in equation (148)) 𝑆−({𝑠 ∈ 𝑆|∃𝑡 ∶ 𝑠 ∈ [[(𝒜1 √20𝑞 𝑞0∧𝒜1 √21𝑞 𝑞0)]](1) ∧𝑡 ∈ [[𝑃=0.50𝑐 𝑐0∧𝑃=0.51𝑐 𝑐0]](2) ⇒𝑡∉ [[(𝑃=0.50𝑐 𝑐0∧𝑃=0.51𝑐 𝑐0)]](2)}) =(it can be easily verified that sets referred by (1),(2) are non-empty) [[¬⊥]] 108 5.4. Some valid rules and examples 109 = [[⊤]] ⇤ 5.4.5 A Hoare style sequence rule Hoare logic is a formal system to deal with simple while languages, introduced by Hoare in 1969 [ 200 ], which constitutes an important landmark in computer science. One of the central rules of such logic is the sequence rule, which reads as {𝑃}𝜋1{𝐼} {𝐼}𝜋2{𝑅} {𝑃}𝜋1;𝜋2{𝑅} where 𝑃 and 𝑅 are pre and post conditions for programs, 𝜋1 and 𝜋2 are programs, and 𝜋1;𝜋2 is a sequence of programs 𝜋1 and 𝜋2 , i.e. the rule defines how programs compose, given the proofs of the individual programs. It is also well-known that Hoare logic can be retrieved from dynamic logic: the so-called Hoare triple {𝑃}𝜋{𝑅} , can expressed as an expression 𝑝→[𝜋]𝑟 , which has the interpretation 𝑝 being true implies that it is necessary that 𝑟 is true upon the execution of program 𝜋 . Given this, the sequence rule of Hoare can be translated into the following expression: 𝑃→[𝜋1]𝐼 𝐼→[𝜋2]𝑅 𝑃→[𝜋1;𝜋2]𝑅 which also corresponds to the following expression 𝑃→[𝜋1]𝐼∧𝐼→[𝜋2]𝑅↔𝑃→[𝜋1;𝜋2]𝑅 .We show this rule also holds here. Firstly, it can be easily shown that [𝜋1;𝜋2]𝜙↔[𝜋1][𝜋2]𝜙holds: Proof: [𝜋1;𝜋2]𝜙↔[𝜋1][𝜋2]𝜙 ≡ {𝑠∈𝑆|∀𝑢∶(𝑠,𝑢)∈[[𝜋1;𝜋2]]⇒𝑢∈[[𝜙]]}=[[[𝜋1][𝜋2]𝜙]] ≡(by definition of composition) {𝑠 ∈ 𝑆|∀𝑢 ∶ (𝑠,𝑢) ∈ {(𝑠,𝑢)|∃𝑡 ∶ (𝑠,𝑡) ∈ [[𝜋1]]∧(𝑡,𝑢) ∈ [[𝜋2]]} ⇒ 𝑢 ∈ [[𝜙]]} = [[[𝜋1][[𝜋2]𝜙]]] ≡ {𝑠∈𝑆|∀𝑢∀𝑡∶(𝑠,𝑡)∈[[𝜋1]]∧(𝑡,𝑢)∈[[𝜋2]]⇒𝑢∈[[𝜙]]}=[[[𝜋1][𝜋2]𝜙]] ≡ {𝑠∈𝑆|∀𝑡∶(𝑠,𝑡)∈[[𝜋1]]⇒𝑡∈{𝑡|∀(𝑡,𝑢)∈[[[𝜋2]]]⇒𝑢∈[[𝜙]]}}=[[[𝜋1][𝜋2]𝜙]] ≡ {𝑠∈𝑆|∀𝑡∶(𝑠,𝑡)∈[[𝜋1]]⇒𝑡∈[[[𝜋2]𝜙]]}=[[[𝜋1][𝜋2]𝜙]] 109 5.4. Some valid rules and examples 116 𝜋𝑞0,𝑞1,𝑞2(𝑡)=(𝐶𝑁𝑂𝑇⊗𝐼).𝜋𝑞0,𝑞1,𝑞2(𝑠)⇒𝑡∉[[𝑝]]} =(the action of the h instruction results in the state |+⟩) 𝑆−{𝑠|∃𝑡∶𝜋𝑞0,𝑞1,𝑞2(𝑠)=(𝜆1∗1 √2|000⟩+𝜆1∗1 √2|011⟩+𝜆2∗1 √2|100⟩+𝜆2∗1 √2|111⟩)∧ 𝜋𝑞1,𝑞2(𝑡)=(𝜆1∗1 √2|000⟩+𝜆1∗1 √2|011⟩+𝜆2∗1 √2|110⟩+𝜆2∗1 √2|101⟩)⇒𝑡∉[[𝑝]]} =(by the definition of the probabilistic operator on the |+⟩state) 𝑆−{𝑠|∃𝑡∶𝑠∈[[(𝒜=𝜆1(0𝑞 𝑞0)∧𝒜=(𝜆2)(1𝑞 𝑞0))∧(𝒜=1 √2(0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜1 √2(1𝑞 𝑞1∧1𝑞 𝑞2))]]1∧𝑡∈ [[𝑝]]2⇒𝑡∉[[𝑝]]2} =(it can be easily verified that sets referred by (1),(2) are non-empty) [[⊤]] ⇤ Measuring qubits and classical information The resulting state of program ENT holds a superposition of all the possible Bell states with the original amplitudes 𝜆1 and 𝜆2 . All that is necessary is to eliminate the Bell states from the global state, in order to retrieve back the original state on the third qubit. This is done by the program h 𝑞0 ;meas 𝑞𝑞 0 to 𝑐𝑐 0 ;meas 𝑞𝑞 1 to 𝑐𝑐 1 ;if(c[0]==1)x 𝑞2 ;if(c[1]==1)z 𝑞2 , which measures the first two qubits, in two different axis each (two measures are enough to identify the Bell state) and uses the results of the measurements in two independent if statements to eliminate the Bell states. The first step of the measurement is the application is the application of the operator 𝐻 over qubit 0, in order to be able to measure in Hadamard basis ,i.e. |+⟩,|−⟩rather than |0⟩,|1⟩(see proof h3), leading to: (v) (𝒜=( 1 √2∗𝜆1)(0𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=( 1 √2∗(𝜆2)(1𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2) ∧𝒜=( 1 √2∗𝜆1)(0𝑞 𝑞0∧1𝑞 𝑞1∧1𝑞 𝑞2)∧𝒜=1 √2∗(𝜆2)(1𝑞 𝑞0∧0𝑞 𝑞1∧1𝑞 𝑞2)) →[ℎ𝑞0]𝒜=(1 2∗𝜆1)(0𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(1 2∗𝜆2)(0𝑞 𝑞0∧0𝑞 𝑞1∧1𝑞 𝑞2) ∧𝒜=(1 2∗𝜆2)(0𝑞 𝑞0∧1𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(1 2∗𝜆1)(0𝑞 𝑞0∧1𝑞 𝑞1∧1𝑞 𝑞2) ∧𝒜=(1 2∗𝜆1)(1𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(−1 2∗𝜆2)(1𝑞 𝑞0∧0𝑞 𝑞1∧1𝑞 𝑞2) ∧𝒜=(−1 2∗𝜆2)(1𝑞 𝑞0∧1𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(1 2∗𝜆1)(1𝑞 𝑞0∧1𝑞 𝑞1∧1𝑞 𝑞2) ⊤→[ENT;h 𝑞0] 𝒜=(1 2∗𝜆1)(0𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(1 2∗𝜆2)(0𝑞 𝑞0∧0𝑞 𝑞1∧1𝑞 𝑞2) ∧𝒜=(1 2∗𝜆2)(0𝑞 𝑞0∧1𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(1 2∗𝜆1)(0𝑞 𝑞0∧1𝑞 𝑞1∧1𝑞 𝑞2) ∧𝒜=(1 2∗𝜆1)(1𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(−1 2∗𝜆2)(1𝑞 𝑞0∧0𝑞 𝑞1∧1𝑞 𝑞2) ∧𝒜=(−1 2∗𝜆2)(1𝑞 𝑞0∧1𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(−1 2∗𝜆1)(1𝑞 𝑞0∧1𝑞 𝑞1∧1𝑞 𝑞2) (𝑣𝑖) 116 5.4. Some valid rules and examples 117 The following step is the actual measurement of qubits 0 and 1 , storing the results in the classical bits. This can be done by programs meas 𝑞𝑞 0 to 𝑐𝑐 0 and meas 𝑞𝑞 1 to 𝑐𝑐 1 , which we denote as M1 and M2, respectively. The effect of the measurements gives origin to the following inference (see proof meast): (vi) 𝒜=(1 2∗𝜆1)(0𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(1 2∗𝜆2)(0𝑞 𝑞0∧0𝑞 𝑞1∨1𝑞 𝑞2) ∧𝒜=(1 2∗𝜆2)(0𝑞 𝑞0∧1𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(1 2∗𝜆1)(0𝑞 𝑞0∧1𝑞 𝑞1∨1𝑞 𝑞2) ∧𝒜=(1 2∗𝜆1)(1𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(−1 2∗𝜆2)(1𝑞 𝑞0∧0𝑞 𝑞1∨1𝑞 𝑞2) ∧𝒜=(−1 2∗𝜆2)(1𝑞 𝑞0∧1𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(−1 2∗𝜆1)(1𝑞 𝑞0∧1𝑞 𝑞1∧1𝑞 𝑞2) →[𝑀1;𝑀2] 𝑃=0.25(0𝑐 𝑐0∧0𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∨𝒜=(𝜆2)(1𝑞 𝑞2))∨ 𝑃=0.25(0𝑐 𝑐0∧0𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∨𝒜=(𝜆1)(1𝑞 𝑞2))∨ 𝑃=0.25(1𝑐 𝑐0∧1𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∨𝒜=(−𝜆2)(1𝑞 𝑞2))∨ 𝑃=0.25(1𝑐 𝑐0∧1𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∨𝒜=(−𝜆1)(1𝑞 𝑞2)) [ENT;h 𝑞0;M1;M2] 𝑃=0.25(0𝑐 𝑐0∧0𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=(𝜆2)(1𝑞 𝑞2))∨ 𝑃=0.25(0𝑐 𝑐0∧0𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(𝜆1)(1𝑞 𝑞2))∨ 𝑃=0.25(1𝑐 𝑐0∧1𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=−𝜆2(1𝑞 𝑞2))∨ 𝑃=0.25(1𝑐 𝑐0∧1𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(−𝜆1)(1𝑞 𝑞2)) (𝑣𝑖𝑖) Finally, following the measurements of the first qubits, all that remains is to apply the error corrections, which come from the programs if (c [0] == 1) z 𝑞2 and if (c [0] == 1) z 𝑞2 ,whichwenameasIF1andIF2, respectively. The following inference is possible upon the execution of program IF1 (see proof if1), (vii) 𝑃=0.25(0𝑐 𝑐0∧0𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∨𝒜=(𝜆2)(1𝑞 𝑞2))∨ 𝑃=0.25(0𝑐 𝑐0∧0𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∨𝒜=(𝜆1)(1𝑞 𝑞2))∨ 𝑃=0.25(1𝑐 𝑐0∧1𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∨𝒜=−𝜆2(1𝑞 𝑞2))∨ 𝑃=0.25(1𝑐 𝑐0∧1𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∨𝒜=(−𝜆1)(1𝑞 𝑞2)) →[𝐼𝐹1]𝑃=0.5((0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=(𝜆2)(1𝑞 𝑞2))∨ 𝑃=0.5(1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(𝜆1)(1𝑞 𝑞2)) [ENT;h 𝑞0;M1;M2;IF1] 𝑃=0.5(0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=(𝜆2)(1𝑞 𝑞2))∨ 𝑃=0.5(1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(𝜆1)(1𝑞 𝑞2)) (𝑣𝑖𝑖𝑖) and after the program IF2 the following post-condition holds (see proof if2) (viii) 𝑃=0.5(0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=(𝜆2)(1𝑞 𝑞2))∨ 𝑃=0.5(1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(𝜆1)(1𝑞 𝑞2)) →[𝐼𝐹2](𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=(𝜆2)(1𝑞 𝑞2)) [ENT;h 𝑞0;M1;M2;IF1;IF2] (𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=(𝜆2)(1𝑞 𝑞2)) (𝑖𝑥) 117 5.4. Some valid rules and examples 118 . which due to the assertion of (150) , results in [ENT;h 𝑞0 ;M1;M2;IF1;IF2]( 𝑃=𝛼(0𝑞 𝑞2)∧𝑃=1−𝛼(1𝑞 𝑞2) ) being true, completing the proof. Proofs of the measurement and post-error correction Proof: (h3) Let 𝑝,𝑞denote the following expressions 𝑝=((𝒜=( 1 √2∗𝜆1)(0𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=( 1 √2∗(𝜆2)(1𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2) ∧𝒜=( 1 √2∗𝜆1)(0𝑞 𝑞0∧1𝑞 𝑞1∧1𝑞 𝑞2)∧𝒜=1 √2∗(𝜆2)(1𝑞 𝑞0∧0𝑞 𝑞1∧1𝑞 𝑞2)), and 𝑞=𝒜=(1 2∗𝜆1)(0𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(1 2∗𝜆2)(0𝑞 𝑞0∧0𝑞 𝑞1∧1𝑞 𝑞2) ∧𝒜=(1 2∗𝜆2)(0𝑞 𝑞0∧1𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(1 2∗𝜆1)(0𝑞 𝑞0∧1𝑞 𝑞1∧1𝑞 𝑞2) ∧𝒜=(1 2∗𝜆1)(1𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(−1 2∗𝜆2)(1𝑞 𝑞0∧0𝑞 𝑞1∧1𝑞 𝑞2) ∧𝒜=(−1 2∗𝜆2)(1𝑞 𝑞0∧1𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(−1 2∗𝜆1)(1𝑞 𝑞0∧1𝑞 𝑞1∧1𝑞 𝑞2). The proof of the expression 𝑝→[𝐻]𝑞goes as follows: [[𝑝→[𝐻]𝑞]] =(by the definition of the h instruction and the semantics of state s) 𝑆−{𝑠|∃𝑡∶𝜋𝑞0,𝑞1,𝑞2(𝑠)=(𝜆1∗1 √2|000⟩+𝜆1∗1 √2|011⟩+𝜆2∗1 √2|110⟩+𝜆2∗1 √2|101⟩)∧ 𝜋𝑞0,𝑞1,𝑞2(𝑡)=(𝐻⊗𝐼⊗𝐼).𝜋𝑞0,𝑞1,𝑞2(𝑠)⇒𝑡∉[[𝑞]]} =(the action of the h instruction results in the state 𝑆−{𝑠|∃𝑡∶𝜋𝑞0,𝑞1,𝑞2(𝑠)=(𝜆1∗1 √2|000⟩+𝜆1∗1 √2|011⟩+𝜆2∗1 √2|110⟩+𝜆2∗1 √2|101⟩)∧ 𝜋𝑞0,𝑞1,𝑞2(𝑡)=(𝜆1∗1 2|000⟩+𝜆2∗1 2|001⟩+𝜆2∗1 2|010⟩+𝜆1∗1 2|100⟩+−𝜆2∗1 2|101⟩+−𝜆2∗ 1 2|110⟩+𝜆1∗1 2|111⟩)⇒𝑡∉[[𝑝]]} =(by the definition of the amplitude operator on the state) 𝑆−{𝑠|∃𝑡∶𝑠∈[[(𝒜=𝜆1(0𝑞 𝑞0)∧𝒜=(𝜆2)(1𝑞 𝑞0))∧(𝒜=1 √2(0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜1 √2(1𝑞 𝑞1∧1𝑞 𝑞2))]](1) ∧𝑡∈ [[𝑝]](2) ⇒𝑡∉[[𝑝]](2)} =(it can be easily verified that sets referred by (1),(2) are non-empty) [[⊤]] ⇤ 118 5.4. Some valid rules and examples 119 Proof: (meast) Let 𝑝and 𝑞denote the following expressions: 𝑝=𝒜=(1 2∗𝜆1)(0𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(1 2∗𝜆2)(0𝑞 𝑞0∧0𝑞 𝑞1∧1𝑞 𝑞2) ∧𝒜=(1 2∗𝜆2)(0𝑞 𝑞0∧1𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(1 2∗𝜆1)(0𝑞 𝑞0∧1𝑞 𝑞1∧1𝑞 𝑞2) ∧𝒜=(1 2∗𝜆1)(1𝑞 𝑞0∧0𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(−1 2∗𝜆2)(1𝑞 𝑞0∧0𝑞 𝑞1∧1𝑞 𝑞2) ∧𝒜=(−1 2∗𝜆2)(1𝑞 𝑞0∧1𝑞 𝑞1∧0𝑞 𝑞2)∧𝒜=(−1 2∗𝜆1)(1𝑞 𝑞0∧1𝑞 𝑞1∧1𝑞 𝑞2), 𝑞=𝑃=0.25(0𝑐 𝑐0∧0𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=(𝜆2)(1𝑞 𝑞2))∨ 𝑃=0.25(0𝑐 𝑐0∧0𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(𝜆1)(1𝑞 𝑞2))∨ 𝑃=0.25(1𝑐 𝑐0∧1𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=(−𝜆2)(1𝑞 𝑞2))∨ 𝑃=0.25(1𝑐 𝑐0∧1𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(−𝜆1)(1𝑞 𝑞2)). The proof of the expression 𝑝→[𝑀1;𝑀2]𝑞reads as: [[𝑝→[𝑀1;𝑀2]𝑞]] =(by the definition of the dynamic operator ⟨𝜋⟩𝜙) 𝑆−{𝑠|∃𝑡∶𝑠∈[[𝑝]]∧(𝑠,𝑡)∈[[[meas 𝑞0to 𝑐0;meas 𝑞1to 𝑐1]]]⇒𝑡∉[[𝑞]]} ≡(by the definition of measurement) 𝑆−{𝑠|∃𝑢∃𝑡∶𝑠∈[[𝑝]]∧(𝑠,𝑢)∈({(𝑠,𝑢)|𝑢∈[[𝑞𝑞 0==0]](𝑠)∧𝑢∈[[𝑃𝑒10𝑐 𝑐0]]where 𝑒1= ⟨𝑠∣0𝑞 𝑞0⟩⟨0𝑞 𝑞0∣𝑠⟩}∪{(𝑠,𝑢)|𝑢 ∈ [[𝑞𝑞 0== 1]]∧𝑢 ∈ [[𝑃𝑒21𝑐 𝑐0]]where 𝑒2= ⟨𝑠∣1𝑞 𝑞0⟩⟨1𝑞 𝑞0∣𝑠⟩})∧ (𝑢,𝑡)∈[[meas 𝑞1to 𝑐1]]⇒𝑡∉[[𝑞]]} =(by the definItion of measurement and combination) 𝑆−{𝑠|∃𝑡∶𝑠∈[[𝑝]]∧ (𝑠,𝑡)∈({(𝑠,𝑡)|𝑡∈[[𝑞𝑞 1==0]]∧𝑡∈[[0𝑞 𝑞0∧𝑃=𝑒10𝑐 𝑐0∧𝑃=𝑒20𝑐 𝑐1]]}∪ {(𝑠,𝑡)|𝑡∈[[𝑞𝑞 1==1]]∧𝑡∈[[0𝑞 𝑞0∧𝑃=𝑒10𝑐 𝑐0∧𝑃=𝑒31𝑐 𝑐1]]}∪ {(𝑠,𝑡)|𝑡∈[[𝑞𝑞 1==0]]∧𝑡∈[[1𝑞 𝑞0∧𝑃=𝑒41𝑐 𝑐0∧𝑃=𝑒20𝑐 𝑐1]]}∪ {(𝑠,𝑡)|𝑡∈[[𝑞𝑞 1==1]]∧𝑡∈[[1𝑞 𝑞0∧𝑃=𝑒41𝑐 𝑐0∧𝑃=𝑒31𝑐 𝑐1]]}⇒𝑡∉[[𝑞]]} where 𝑒1=⟨𝑠∣0𝑞 𝑞0⟩⟨0𝑞 𝑞0∣𝑠⟩,𝑒2=⟨𝑠∣0𝑞 𝑞1⟩⟨0𝑞 𝑞1∣𝑠⟩,𝑒3=⟨𝑠∣1𝑞 𝑞1⟩⟨1𝑞 𝑞1∣𝑠⟩and 𝑒4=⟨𝑠∣1𝑞 𝑞0⟩⟨1𝑞 𝑞0∣𝑠⟩) 119 5.4. Some valid rules and examples 120 =(the actual application of quantum tests, lead to the following state) 𝑆−{𝑠|∃𝑡∶𝑠∈[[𝑝]](1)∧ (𝑠,𝑡)∈({(𝑠,𝑡)|𝑡∈[[(0𝑞 𝑞1∧0𝑞 𝑞0∧0𝑐 𝑐0∧0𝑐 𝑐1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=(𝜆2)(1𝑞 𝑞2))]]}∪ {(𝑠,𝑡)|𝑡∈[[𝑃=0.5∗0.5(1𝑞 𝑞1∧0𝑞 𝑞0∧0𝑐 𝑐0∧1𝑐 𝑐1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(𝜆1)(1𝑞 𝑞2))]]}∪ {(𝑠,𝑡)|𝑡∈[[𝑃=0.5∗0.5(0𝑞 𝑞1∧1𝑞 𝑞0∧1𝑐 𝑐0∧0𝑐 𝑐1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=−𝜆2(1𝑞 𝑞2))]]}∪ {(𝑠,𝑡)|𝑡∈[[𝑃=0.5∗0.5(1𝑞 𝑞1∧1𝑞 𝑞0∧1𝑐 𝑐0∧1𝑐 𝑐1]]∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(−𝜆1)(1𝑞 𝑞2))]]})(2) ⇒𝑡∉[[𝑞]](2)} = 𝑆−{𝑠|∃𝑡∶𝑠∈[[𝑝]](1) ∧𝑡∈[[𝑞]](2) ⇒ 𝑡∉[[𝑞]](2)} =(it can be easily verified that sets referred by (1),(2) are non-empty) [[¬⊥]] = [[⊤]] ⇤ Proof: (if1)Let𝑝,𝑞denote the following expressions: 𝑝=(𝑃=0.25(0𝑐 𝑐0∧0𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=(𝜆2)(1𝑞 𝑞2))∨ 𝑃=0.25(0𝑐 𝑐0∧0𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(𝜆1)(1𝑞 𝑞2))∨ 𝑃=0.25(1𝑐 𝑐0∧1𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=−𝜆2(1𝑞 𝑞2))∨ 𝑃=0.25(1𝑐 𝑐0∧1𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(−𝜆1)(1𝑞 𝑞2)), 𝑞=𝑃=0.5((0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=(𝜆2)(1𝑞 𝑞2))∧ 𝑃=0.5(1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(𝜆1)(1𝑞 𝑞2)). The proof of statement 𝑝→[𝐼𝐹1]𝑞reads as: [[𝑝→[𝐼𝐹1]𝑞]] =(by the definition of the dynamic operator ⟨𝜋⟩𝜙) 𝑆−{𝑠|∃𝑡∶𝑠∈[[𝑝]]∧(𝑠,𝑡)∈{[[[if (𝑐0== 1) z 𝑞3]]]}⇒𝑡∉[[𝑞]]} =(by the semantics of the if statement) 𝑆−{𝑠|∃𝑡∶𝑠∈[[𝑝]]∧(𝑠,𝑡)∈([[𝑐0== 1]]∩[[|1𝑐0⟩⟨1𝑐0|;z𝑞3]]}∪{[[𝑐0== 0]]∩[[|0𝑐0⟩⟨0𝑐0|;skip]])⇒ 𝑡∉[[𝑞]]} 120 5.4. Some valid rules and examples 121 = (by the definition of the if statement, only two worlds, the ones where test 𝑐0 == 1 holds, will be affected by the phase flip operator) 𝑆−{𝑠|∃𝑡∶𝑠∈[[𝑝]]∧𝑡∈([[𝑃=0.25(0𝑐 𝑐0∧0𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=(𝜆2)(1𝑞 𝑞2))]]∪ [[𝑃=0.25(0𝑐 𝑐0∧0𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(𝜆1)(1𝑞 𝑞2))]]∪ [[𝑃=0.25(1𝑐 𝑐0∧1𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=𝜆2(1𝑞 𝑞2))]]∪ [[𝑃=0.25(1𝑐 𝑐0∧1𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(𝜆1)(1𝑞 𝑞2))]])⇒𝑡∉[[𝑞]]} = (upon the application of the phase flip correction, the two pairs of possible worlds become equivalent, hence the possible worlds are narrowed to 2) 𝑆−{𝑠|∃𝑡∶𝑠∈[[𝑝]](1) ∧𝑡∈([[𝑃=0.5(1𝑐 𝑐0∧1𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=𝜆2(1𝑞 𝑞2))]]∪ [[𝑃=0.5(1𝑐 𝑐0∧1𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(𝜆1)(1𝑞 𝑞2))]])(2) ⇒𝑡∉[[𝑞]](2)} =(it can be easily verified that sets referred by (1),(2) are non-empty) [[¬⊥]] = [[⊤]] ⇤ Proof: (if2)Let𝑝,𝑞denote the following expressions: 𝑝=𝑃=0.5(0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=(𝜆2)(1𝑞 𝑞2))∧𝑃=0.5(1𝑐 𝑐1∧1𝑞 𝑞1∧𝒜=𝜆2(0𝑞 𝑞2)∧𝒜=(𝜆1)(1𝑞 𝑞2)), 𝑞=(𝑃=𝛼(0𝑞 𝑞2)∧𝑃=1−𝛼(1𝑞 𝑞2)). The proof of the statement 𝑝→[𝐼𝐹2]𝑞,readas [[𝑝→[𝐼𝐹2]𝑞]] =(by the definition of the dynamic operator ⟨𝜋⟩𝜙) 𝑆−{𝑠|∃𝑡∶𝑠∈[[𝑝]]∧(𝑠,𝑡)∈([[𝑐1== 1]]∩[[|1𝑐1⟩⟨1𝑐1|;x𝑞3]]}∪{[[𝑐1== 0]]∩[[|1𝑐0⟩⟨1𝑐1|;skip]])⇒ 𝑡∉[[𝑞]]} = (by the semantics of the if statement, i.e. one possible world is affected by operator X, and the other is not) 𝑆−{𝑠|∃𝑡∶𝑠∈[[𝑝]]∧𝑡∈([[𝑃=0.5(1𝑐 𝑐0∧1𝑞 𝑞0∧0𝑐 𝑐1∧0𝑞 𝑞1∧𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=𝜆2(1𝑞 𝑞2))]]∪ [[𝑃=0.5(1𝑐 𝑐0∧1𝑞 𝑞0∧1𝑐 𝑐1∧1𝑞 𝑞1∧𝐴=(𝜆1)(0𝑞 𝑞2)∧𝒜=𝜆2(1𝑞 𝑞2))]])⇒𝑡∉[[𝑞]]} =(the two resulting worlds are equivalent and hence, merge into one) 𝑆−{𝑠|∃𝑡∶𝑠∈[[𝑝]]∧𝑡∈([[(𝒜=𝜆1(0𝑞 𝑞2)∧𝒜=𝜆2(1𝑞 𝑞2))]]⇒𝑡∉[[𝑞]]} 121 5.4. Some valid rules and examples 122 =(by assumption of equation 150) 𝑆−{𝑠|∃𝑡∶𝑠∈[[𝑝]](1)∧𝑡∈([[𝑃=𝛼0𝑞 𝑞2∧𝑃=1−𝛼1𝑞 𝑞2]](2) ⇒𝑡∉[[(𝑃=𝛼(0𝑞 𝑞2)∧𝑃=1−𝛼(1𝑞 𝑞2))]](2)} =(it can be easily verified that sets referred by (1),(2) are non-empty) [[¬⊥]]=[[⊤]] ⇤ 122 5.5. Proof of decidability 123 5.5 Proof of decidability In this section we show that the logic presented in this chapter is decidable. The method for this is based on the reduction of the logic to the theory of the first order language of complex numbers, i.e. first order theory of the algebraically closed fields2, known to be decidable by an important result of Tarski [342]. Definition 5.5.1. The first order theory of complex numbers, denoted by 𝒯ℒℂ ,isthetheory of ℂ in the language ℒℂ , which corresponds to (ℂ,∗,+,.,0,1) , where ∗ is the conjugate transpose operation. This strategy of proving the decidability of quantum logic has been defined for the standard quantum finite dimensional logic by Dunn et al. [ 140 ], and a more general recipe for a wide range of quantum logics, including modal and dynamic ones, has been discussed in Baltag et al. in [ 44 ]. The latter work is the main inspiration for this section, from which the main ideas and notation were borrowed. We revisit the main ingredients of the proof recipe through the next sections and the decidability is stated and proved in theorem 5.5.2. 5.5.1 The main idea of the proof The cornerstone of the proof presented in [ 140 ] is based on the equivalence between quantum propositions, closed linear sub-spaces of an Hilbert space, and kernels of matrices, i.e. [[𝑝]]⇔[[𝑝]]⇔{𝑣| 𝑝.𝑣=0}, (151) where 𝑝 is a proposition, [[𝑝]] is a closed linear subspace of an Hilbert space, and 𝑝 ∈ ℂ 𝑛×𝑛 is a matrix and {𝑣| 𝑝.𝑣=0} corresponds to its kernel. This equivalence makes possible the entire translation of standard quantum logic into closed statements of the first order theory of complex numbers, as the kernel of the matrix 𝑝=(𝑝11,…,𝑝𝑖𝑗,…,𝑝𝑛𝑛), can efficiently be reduced to an expression of this theory as ℂ⊧∀𝑣 𝑝.𝑣=0⇔𝐶⊧𝑝11.𝑣1+𝑝12.𝑣2+…+𝑝1𝑛.𝑣𝑛=0∧ 𝑝21.𝑣1+𝑝22.𝑣2+…+𝑝2𝑛.𝑣𝑛=0∧ …∧ 𝑝𝑛1.𝑣1+𝑝𝑛2.𝑣2+…+𝑝𝑛𝑛.𝑣𝑛=0. where 𝑝11 to 𝑝𝑛𝑛 are a set of variables with valuations in ℂ . From here one can extract useful notions of logic: 𝑣∈[[𝑝]]as ℂ⊧ 𝑝.𝑣=0 (152) 2 Theory composed of axioms of algebraically closed fields, equality operators, and first order quantifiers. 123 5.5. Proof of decidability 124 and the notion of satisfaction ℋ⊧𝑝 , meaning that 𝑝 is true independently of the matrixial representation, 𝑝 , chosen: ℋ⊧𝑝⇔ℂ⊧∀ 𝑝∀𝑣 𝑝.𝑣=0. (153) Furthermore, it is also possible to express unitary operators with an additional condition enforcing their unitarity, ℋ⊧[𝑢]𝑝⇔ℂ⊧∀ 𝑢 𝑝𝑈𝑛( 𝑢)→∀𝑣 𝑝( 𝑢𝑣)=0,where 𝑈𝑛( 𝑢)= 𝑢. 𝑢∗=𝐼, completing the necessary machinery to capture the static and dynamic aspects of quantum logic. In a more general way every quantum dynamic logic expression can be translated into expressions of type ℋ⊧𝜑⇔ℂ⊧∀ 𝑥(𝜑𝑝( 𝑥)→∀𝑣.𝜑𝛿(𝑣, 𝑥)), (154) where both 𝜑𝛿(𝑣, 𝑥) and 𝜑𝑝(𝑥) are functions, 𝑣 is a vector space, and 𝑥 are lists of variables, with valuations in ℂ , which corresponds to the matrixial representation of 𝜑 , 𝜑 . The former function defines [[𝜑]]∈ℋ , i.e. by making the 𝑥 correspond to the assignment [[.]] , and the latter, 𝜑𝑝(𝑥) , defines the range of good values for 𝑥 . Hence, as all the statements falling into this type of expressions are inherently well-formed in the first order theory of complex numbers, and hence implicitly decidable, and the proof of decidability somehow reduces to showing that such functions can be obtained by an effective method. 5.5.2 Application to the Probabilistic logic of quantum programs These ideas are applicable to the probabilistic logic of quantum programs (PLQP), introduced in [ 44 ]. Recalling, its syntax reads as: 𝜙∶∶=𝑝|𝜙∧𝜙|¬𝜙|[𝜋]𝜙|𝑃≥𝑟𝜙 𝜋∶∶=𝑢|𝜙?|𝜋;𝜋|𝜋∪𝜋 The first element of the proof of decidability of the logic comes from the fact that all models over a Hilbert space of this logic, (Σ,[[.]]) , are isomorphic to a ℂ𝑛 -interpretation (see definition 5.5.2), ℋ≅ℂ𝑛 ,i.e. an interpretation over the closed subspaces of an Hilbert space. Definition 5.5.2. Given a language ℒ ,bya ℂ𝑛 -interpretation we mean a map [[.]] ,that assigns to each sentence of ℒ a subspace of ℂ𝑛 .Alsogivenanyclass ℱ of ℂ𝑛 interpretations of ℒ ,wesaythatasentence 𝜑 is ℱ -valued and write ℱ⊧𝜑 ,if [[𝜑]]=ℂ𝑛 for all [[.]]∈ℱ 124 5.5. Proof of decidability 125 Based on the equivalence of equation (153) and (154) , one can conclude that for each assignment [[.]] , there must be a function 𝛼∶𝑣𝑎𝑟(ℒℂ)→ℂ ,where 𝑣𝑎𝑟(ℒℂ) corresponds to a list of variables 𝑥 ,i.e. one that makes 𝜑𝛿(𝑣, 𝑥)) be equivalent to some [[.]] . For instance, In the case of the PLQP language, to an atomic proposition 𝑝 , defined by a tuple 𝑥=(𝑥11,…,𝑥𝑛𝑛) of 𝑛×𝑛 variables, the function 𝛼 , given by 𝛼( 𝑥)=(𝛼(𝑥11),…,𝛼(𝑥𝑛𝑛)) , is such that 𝜑𝛿(𝑣,𝛼( 𝑥))) is equivalent to [[𝑝]] . There is a wide range of functions 𝛼 for each assignment [[.]] , however not all them are valid. In the case of the PLQP language, such pairs, i.e. valid pairs, must respect the following conditions ( 𝒜𝒰 is the set of well-formed unitary operators): •for each 𝑢∈𝒜𝒰,ℂ⊧𝑈𝑛[𝛼( 𝑢)], that is 𝛼( 𝑢)is an unitary matrix; •for each 𝑝∈𝒜ℱ,[[𝑝]]is the kernel of the matrix (𝛼( 𝑝)and •for each 𝑢∈𝒜𝒰,[[𝑢]]is the unitary transformation, given by the unitary matrix 𝛼( 𝑢). The structure that maps the valid assignments, [[.]] and 𝛼 -functions is denominated a ℂ -coding (see definition 5.5.3), which is nothing more than a relational structure, containing all [[.]]−𝛼function pairs. Definition 5.5.3. Given any class ℱ of ℂ𝑛 -interpretations, a ℂ coding of ℱ is a partial function R from ℂ𝑣𝑎𝑟(ℒℂ) onto ℱ such that, for every finite list of variables 𝑥=(𝑥1,…,𝑥𝑚)⊆ 𝑣𝑎𝑟(ℒℂ) of ℒℂ there is an 𝑚− ary formula 𝑝𝑥 (𝑦) of ℒℂ defining the set {𝛼( 𝑥)∈ℂ𝑚|𝑎∈ 𝑑𝑜𝑚(𝑅))} . Moreover, we say that a ℂ -coding is effective if there is an effective procedure of computing such 𝑝𝑥 (𝑦)for any given finite 𝑥 . An effective ℂ− coding is one where the function 𝑝𝑥 (𝑦) , which determines the valid assignments for the lists 𝑥 , can be determined effectively . There is a close relationship between ℂ -codings and function pairs (𝜑𝑝(𝑥)and 𝜑𝛿(𝑣, 𝑥)), which translates as follows: 𝑅(𝛼,[[.]])entails [[𝜑]]=𝜑𝛿(ℂ,𝛼( 𝑥)), 𝜑𝑝(ℂ)=𝑝𝑥 (ℂ). (155) Hence, the decidability of a logic, which corresponds to the existence of an effective method to the generation of functions 𝜑𝛿(𝑣, 𝑐) and 𝜑𝑝(𝑥) , can also be reduced to the r-translatability (see definition 5.5.4) of expressions in an effective ℂ-coding, as stated in theorem 5.5.1. Definition 5.5.4. ([ 44 ]) Fix a finite-dimensional Hilbert space ℋ≅ℂ 𝑛 ,anyclass ℱ of ℂ𝑛− interpretation of a language ℒ , and any effective ℂ− coding R of ℱ . Then for any sentence 𝜑 of ℒ ,wesaythataformula 𝜑𝛿(𝑣1,…,𝑣𝑛,𝑥) of ℒℂ (with a specific tuple of variables 𝑥 )translates𝜑in R, or is an R-translation of 𝜑,ifconditionsofequation(155) Theorem 5.5.1. ([ 44 ]) Fix a finite-dimensional Hilbert space ℋ≅ℂ𝑛 ,anyclass ℱ of ℂ𝑛 - interpretations of language ℒ , and any effective ℂ -coding R of ℱ .Supposeasentence 𝜑 of ℒhas an 𝑅-translation. Then it is decidable whether ℱ⊧𝜑or not. 125 132 From this analysis, it was also proposed a digital simulation of the non-radiative energy transfer taking place in photosynthesis, which involves the weak simulation of a local Hamiltonian, along with environmental interaction. This way it was possible to evaluate the importance of the environmental effects in photosynthesis and obtain further insight about quantum mechanics in an open regime. Chapter 4aimed at exploring problems that have no quantum efficient algorithm, but for which a polynomial advantage is expected, once regarding them as optimization problems. There is a natural relationship between some processes in physics, such as the convergence to equilibrium of certain physical systems, and optimization problems, which make the former a good model to the latter. This idea is the basis of quantum annealing and adiabatic optimization, where a quantum advantage is expected in a wide range of problems, across a wide range of fields. Furthermore, in the so-called short-term devices method a mention should be made to the Variational method, an hybrid classical-quantum method, which possess a lot of applications. One of those applications is on the field of quantum chemistry, and we explore a case study of the application of the method to find the total ground-state energy of the 𝐻2 and 𝐿𝑖𝐻 molecules, subject to a stationary electric field in a quantum computer. This is a non-trivial process, and we particularly explored: • The fermionic formulation of quantum chemistry systems; • The connection between fermionic Hamiltonians and the quantum circuits; • The state preparation, running of the algorithm and the evaluation of the results. The calculated results comprise the total energy as a function of bond length (i.e. the dissociation curve), also under an applied stationary electric field. We also evaluated the shift of the molecule’s energy at a fixed 𝑑 (equal to the equilibrium interatomic distance) with the electric field, i.e. the stationary electronic Stark effect. In total, our case study seems to provide evidence for the feasibility of the use of this quantum computer for small molecules, with a reasonable number of iterations performed. In chapter 5, we briefly explore the logic induced by quantum mechanics in Hilbert spaces, i.e. the so-called quantum logic, and the path from there to logics able to deal with quantum programs, and the issues involved, particularly the inexistence of a tensor operator, focusing on the work on quantum dynamic logics introduced by Baltag and Smets. We proposed a logic able to deal with classical and quantum information simultaneously, and that, furthermore, involves measurements, to which a stochastic semantics is provided. We provide some valid rules for the logic, based on such semantics, and provide proof for a quantum coin toss program. 132 6.1. Future work 133 6.1 Future work This work, in its course of the understanding of the sources of quantum advantage and how to use them to obtain new algorithms and applications of quantum computation, ended touching many different fields related to quantum computation. Many state-of the-art problems and lines of research to pursue were identified and explored. On the other hand, some of the ideas explored during the course of this work, were abandoned. On the field of efficient algorithms, progress has been slow, with no big advancements in the last few years, worth of notice. In the early 2000’s a huge research effort has been done on trying to extend the algorithm for the hidden subgroup problem (HSP), maintaining the exponential advantage, from Abelian groups to non-Abelian ones, such as the dihedral or the symmetric group . Efficient algorithms for the HSP in these groups would have important industrial impact, such as breaking lattice-based cryptography ,the cornerstone of post-quantum cryptography , or solving the graph isomorphism problem, however, the efforts to build efficient algorithms to do so, have fallen short. However, while solving the HSP for non-Abelian groups seems to be a hard computational task, an interesting line of research is to explore applications where the exponential advantage of quantum Fourier transforms can be relevant, which may the case, for instance, in fields such as computer vision, statistics or machine learning. Furthermore, the exploration of problems that can expressed as simulations of local, or sparse, Hamiltonians can very fruitful in finding new applications for quantum algorithms. On the side of quantum optimization, there is an infinitude of possible industrial and academic applications that can be explored with the current short-term devices. A particular important branch of optimization problems is the one of mixed-integer, for which the first quantum techniques are starting to appear, mostly, resorting to interaction between classical and quantum solvers. An example of these problems is the unit commitment , i.e. the optimization of the production schedule of individual energy stations in power grids, a problem that usually involves a large set of variables, discrete and continuous, which constitutes a completely unexplored realm for quantum computation. On the logical side the major development would be the improvement of the calculus for the logic and the proof of its completeness. Furthermore, it would be also be useful to explore the formalization of the logic in a proof system, or alternatively, by the conception of a model checker. The approach taken in the work, specially in the algorithmic part, was somehow pragmatical, however, the interest on pursuing a unified mathematical theory to deal with both complexity and correctness remains. Research paths on this direction can be given by the study of compositional mathematical theories behind the advantage in quantum algorithms, as well as of characteristic quantum programming languages of complexity classes. Concerning the former, a particular interesting line of research is one the application of finite model theory to quantum algorithms, where models are given by combinatory structures, rather than algebraic ones, and may possess interesting notions of logic. 133 BIBLIOGRAPHY [1] Open quantum systems. 22.51 course notes, chapter 8, 2012. URL https://ocw.mit.edu/courses/ nuclear-engineering/22-51-quantum-theory-of-radiation-interactions-fall-2012/lecture-notes/MIT22_ 51F12_Ch8.pdf. MIT OpenCourseWare. [2] Ibm q - quantum computing, Jun 2018. Available in: https://www.research.ibm.com/ibm-q/. [3] Scott Aaronson. Guest column: Np-complete problems and physical reality. ACM Sigact News ,36 (1):30–52, 2005. [4] Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , 461(2063):3473–3482, 2005. [5] Scott Aaronson. Why philosophers should care about computational complexity. In In Computability: Gödel, Turing, Church, and beyond (eds . Citeseer, 2012. [6] Scott Aaronson. The equivalence of sampling and searching. Theory of Computing Systems , 55(2): 281–298, 2014. [7] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A , 70(5):052328, 2004. [8] Scott Aaronson and John Watrous. Closed timelike curves make quantum and classical computing equivalent. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , 465(2102):631–647, 2008. [9] Daniel S Abrams and Seth Lloyd. Nonlinear quantum mechanics implies polynomial-time solution for np-complete and# p problems. Physical Review Letters , 81(18):3992, 1998. [10] Daniel S Abrams and Seth Lloyd. Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors. Physical Review Letters , 83(24):5162, 1999. [11] Samson Abramsky and Bob Coecke. Categorical quantum mechanics. Handbook of quantum logic and quantum structures: quantum logic , pages 261–324, 2009. 134 bibliography 135 [12] R Adams, G Alpàr, JM Balasch Masoliver, Lejla Batina, Łukasz Chmielewski, Louiza Papachristodoulou, Peter Schwabe, Michael Tunstall, Lejla Batina, Jens Hermans, et al. Qpel: Quantum program and effect language. In QPL 2014: Proceedings 11th workshop on Quantum Physics and Logic , volume 1, pages 236–252. EPTCS, 2014. [13] Julia Adolphs and Thomas Renger. How proteins trigger excitation energy transfer in the fmo complex of green sulfur bacteria. Biophysical Journal , 91(8):2778–2797, 2006. [14] Diederik Aerts. Quantum axiomatics. Handbook of quantum logic and quantum structures quantum logic , page 79, 2009. [15] Diederik Aerts and Bart Van Steirteghem. Quantum axiomatics and a theorem of mp soler. International Journal of Theoretical Physics , 39(3):497–502, 2000. [16] Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing ,pages 20–29, 2003. [17] Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. Adiabatic quantum computation is equivalent to standard quantum computation. SIAM review , 50(4):755–787, 2008. [18] Yakir Aharonov, Eliahu Cohen, Fabrizio Colombo, Tomer Landsberger, Irene Sabadini, Daniele C Struppa, and Jeff Tollaksen. Finally making sense of the double-slit experiment. Proceedings of the National Academy of Sciences , 114(25):6480–6485, 2017. [19] Qing Ai, Tzu-Chi Yen, Bih-Yaw Jin, and Yuan-Chung Cheng. Clustered geometries exploiting quantum coherence effects for efficient energy transfer in light harvesting. The Journal of Physical Chemistry Letters , 4(15):2577–2584, 2013. [20] Tameem Albash and Daniel A Lidar. Adiabatic quantum computation. Reviews of Modern Physics , 90(1):015002, 2018. [21] Thorsten Altenkirch, Jonathan Grattage, Juliana K Vizzotto, and Amr Sabry. An algebra of pure quantum programming. Electronic Notes in Theoretical Computer Science , 170:23–47, 2007. [22] Luigi Amico, Rosario Fazio, Andreas Osterloh, and Vlatko Vedral. Entanglement in many-body systems. Reviews of modern physics , 80(2):517, 2008. [23] Matthew Amy, Andrew N Glaudell, and Neil J Ross. Number-theoretic characterizations of some restricted clifford+ t circuits. Quantum , 4:252, 2020. 135 bibliography 136 [24] Hajnal Andréka, István Németi, and Gergely Székely. Closed timelike curves in relativistic computation. Parallel Processing Letters , 22(03):1240010, 2012. [25] Eric Anschuetz, Jonathan Olson, Alán Aspuru-Guzik, and Yudong Cao. Variational quantum factoring. In International Workshop on Quantum Technology and Optimization Problems , pages 74–85. Springer, 2019. [26] Bruno Apolloni, C Carvalho, and Diego De Falco. Quantum stochastic optimization. Stochastic Processes and their Applications , 33(2):233–244, 1989. [27] Mateus Araújo, Philippe Allard Guérin, and Ämin Baumeler. Quantum computation with indefinite causal structures. Physical Review A , 96(5):052315, 2017. [28] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach . Cambridge University Press, 2009. [29] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature , 574(7779):505–510, 2019. [30] Alain Aspect, Philippe Grangier, and Gérard Roger. Experimental tests of realistic local theories via bell’s theorem. Physical review letters , 47(7):460, 1981. [31] Alán Aspuru-Guzik, Anthony D Dutoi, Peter J Love, and Martin Head-Gordon. Simulated quantum computation of molecular energies. Science , 309(5741):1704–1707, 2005. [32] Ryan Babbush, Jarrod McClean, Dave Wecker, Alán Aspuru-Guzik, and Nathan Wiebe. Chemical basis of trotter-suzuki errors in quantum chemistry simulation. Physical Review A , 91(2):022311, 2015. [33] Ryan Babbush, Dominic W Berry, Ian D Kivlichan, Annie Y Wei, Peter J Love, and Alán Aspuru-Guzik. Exponentially more precise quantum simulation of fermions in second quantization. New Journal of Physics , 18(3):033032, 2016. [34] Ryan Babbush, Dominic W Berry, Yuval R Sanders, Ian D Kivlichan, Artur Scherer, Annie Y Wei, Peter J Love, and Alán Aspuru-Guzik. Exponentially more precise quantum simulation of fermions in the configuration interaction representation. Quantum Science and Technology , 3(1):015006, 2017. [35] Dave Bacon. Quantum computational complexity in the presence of closed timelike curves. Physical Review A , 70(3):032309, 2004. 136 bibliography 137 [36] Dave Bacon, Andrew M Childs, and Wim van Dam. From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on , pages 469–478. IEEE, 2005. [37] Costin Ba�descu and Prakash Panangaden. Quantum alternation: Prospects and problems. arXiv preprint arXiv:1511.01567 , 2015. [38] Alexandru Baltag and Sonja Smets. The logic of quantum programs. Proc. QPL , pages 39–56, 2004. [39] Alexandru Baltag and Sonja Smets. Complete axiomatizations for quantum actions. International Journal of Theoretical Physics , 44(12):2267–2282, 2005. [40] Alexandru Baltag and Sonja Smets. Correlated information: a logic for multi-partite quantum systems. Electronic Notes in Theoretical Computer Science , 270(2):3–14, 2011. [41] Alexandru Baltag and Sonja Smets. Quantum logic as a dynamic logic. Synthese , 179(2):285–306, 2011. [42] Alexandru Baltag and Sonja Smets. The dynamic turn in quantum logic. Synthese , 186(3):753–773, 2012. [43] Alexandru Baltag, Jort M Bergfeld, Kohei Kishida, Joshua Sack, Sonja JL Smets, and Shengyang Zhong. Quantum probabilistic dyadic second-order logic. In International Workshop on Logic, Language, Information, and Computation , pages 64–80. Springer, 2013. [44] Alexandru Baltag, Jort Bergfeld, Kohei Kishida, Joshua Sack, Sonja Smets, and Shengyang Zhong. Plqp & company: Decidable logics for quantum algorithms. International Journal of Theoretical Physics , 53(10):3628–3647, 2014. [45] Francisco Barahona. On the computational complexity of ising spin glass models. Journal of Physics A: Mathematical and General , 15(10):3241, 1982. [46] Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical review A , 52(5):3457, 1995. [47] William P Baritompa, David W Bulger, and Graham R Wood. Grover’s quantum algorithm applied to global optimization. SIAM Journal on Optimization , 15(4):1170–1184, 2005. 137 bibliography 138 [48] Panagiotis Kl Barkoutsos, Jerome F Gonthier, Igor Sokolov, Nikolaj Moll, Gian Salis, Andreas Fuhrer, Marc Ganzhorn, Daniel J Egger, Matthias Troyer, Antonio Mezzacapo, et al. Quantum algorithms for electronic structure calculations: Particle-hole hamiltonian and optimized wave-function expansions. Physical Review A , 98(2):022322, 2018. [49] Robert Beals. Quantum computation of fourier transforms over symmetric groups. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing , pages 48–53. ACM, 1997. [50] Salman Beigi. Np vs qma_log (2). arXiv preprint arXiv:0810.5109 , 2008. [51] John S Bell. On the einstein podolsky rosen paradox. Physics Physique Fizika , 1(3):195, 1964. [52] John S Bell. On the problem of hidden variables in quantum mechanics. Reviews of Modern Physics , 38(3):447, 1966. [53] Paul Benioff. Quantum mechanical hamiltonian models of turing machines. Journal of Statistical Physics , 29(3):515–546, 1982. [54] Paul Benioff. Quantum mechanical models of turing machines that dissipate no energy. Physical Review Letters , 48(23):1581, 1982. [55] Charles H Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K Wootters. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physical review letters , 70(13):1895, 1993. [56] Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM journal on Computing , 26(5):1510–1523, 1997. [57] Jort Martinus Bergfeld and Joshua Sack. Deriving the correctness of quantum protocols in the probabilistic logic for quantum programs. Soft Computing , 21(6):1421–1441, 2017. [58] Jort Martinus Bergfeld et al. Quantum logics for expressing and proving the correctness of quantum programs. 2019. [59] Dominic W Berry. High-order quantum algorithm for solving linear differential equations. Journal of Physics A: Mathematical and Theoretical , 47(10):105301, 2014. [60] Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D Somma. Simulating hamiltonian dynamics with a truncated taylor series. Physical review letters , 114(9):090502, 2015. [61] Dominic W Berry, Andrew M Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages 792–809. IEEE, 2015. 138 bibliography 139 [62] Dominic W Berry, Andrew M Childs, Aaron Ostrander, and Guoming Wang. Quantum algorithm for linear differential equations with exponentially improved dependence on precision. Communications in Mathematical Physics , 356(3):1057–1081, 2017. [63] Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society , 48(3): 334–334, 1997. [64] Shalabh Bhatnagar, HL Prasad, and LA Prashanth. Stochastic recursive algorithms for optimization: simultaneous perturbation methods , volume 434. Springer, 2012. [65] Iwo Bialynicki-Birula and Jerzy Mycielski. Nonlinear wave mechanics. Annals of Physics , 100(1-2): 62–93, 1976. [66] Garrett Birkhoff and John Von Neumann. The logic of quantum mechanics. Annals of mathematics , pages 823–843, 1936. [67] Lennart Bittel and Martin Kliesch. Training variational quantum algorithms is np-hard. Physical Review Letters , 127(12):120502, 2021. [68] Patrick Blackburn, Johan FAK van Benthem, and Frank Wolter. Handbook of modal logic . Elsevier, 2006. [69] Hugue Blier and Alain Tapp. A quantum characterization of np. computational complexity , 21(3): 499–510, 2012. [70] Immanuel Bloch, Jean Dalibard, and Wilhelm Zwerger. Many-body physics with ultracold gases. Reviews of modern physics , 80(3):885, 2008. [71] David Bohm. A suggested interpretation of the quantum theory in terms of” hidden” variables. i. Physical Review , 85(2):166, 1952. [72] Niels Bohr. I. on the constitution of atoms and molecules. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science , 26(151):1–25, 1913. [73] Niels Bohr. The quantum postulate and the recent development of atomic theory 1, 1928. [74] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. Nature Physics , 14(6):595–600, 2018. [75] Dan Boneh and Richard J Lipton. Quantum cryptanalysis of hidden linear functions. In Advances in Cryptology—CRYPT0’95 , pages 424–437. Springer, 1995. 139 bibliography 140 [76] Dan Boneh et al. Twenty years of attacks on the rsa cryptosystem. Notices of the AMS , 46(2): 203–213, 1999. [77] Adam D Bookatz. Qma-complete problems. arXiv preprint arXiv:1212.6312 , 2012. [78] Adam D Bookatz. Qma-complete problems. Quantum Information & Computation , 14(5&6):361–383, 2014. [79] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization . Cambridge university press, 2004. [80] Fernando GSL Brandao and Krysta M Svore. Quantum speed-ups for solving semidefinite programs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 415–426. IEEE, 2017. [81] Daniel Braun and Bertrand Georgeot. Quantitative measure of interference. Physical Review A ,73 (2):022314, 2006. [82] Samuel L Braunstein and Hoi-Kwong Lo. Scalable quantum computers: Paving the way to realization . 2001. [83] Heinz-Peter Breuer, Francesco Petruccione, et al. The theory of open quantum systems . Oxford University Press on Demand, 2002. [84] HJ Briegel, DE Browne, W Dür, R Raussendorf, and Maarten Van den Nest. Measurement-based quantum computation. Nature Physics , 5(1):19–26, 2009. [85] Todd A Brun, Jim Harrington, and Mark M Wilde. Localized closed timelike curves can perfectly distinguish quantum states. Physical Review Letters , 102(21):210402, 2009. [86] Olivier Brunet and Philippe Jorrand. Dynamic quantum logic for quantum programs. International Journal of Quantum Information , 2(01):45–54, 2004. [87] Iulia Buluta and Franco Nori. Quantum simulators. Science , 326(5949):108–111, 2009. [88] Cristian S Calude and Elena Calude. The road to quantum computational supremacy. In Jonathan M. Borwein Commemorative Conference , pages 349–367. Springer, 2017. [89] Y. Cao, J. Romero, J. P. Olson, M. Degroote, P. D. Johnson, M. Kieferová, I. D. Kivlichan, T. Menke, B. Peropadre, N. P. D. Sawaya, S. Sim, L. Veis, and A. Aspuru-Guzik. Quantum chemistry in the age of quantum computing. Chemical Reviews , 119(19):10856 – 10915, 2019. 140 bibliography 141 [90] Yudong Cao, Jonathan Romero, Jonathan P Olson, Matthias Degroote, Peter D Johnson, Mária Kieferová, Ian D Kivlichan, Tim Menke, Borja Peropadre, Nicolas PD Sawaya, et al. Quantum chemistry in the age of quantum computing. Chemical reviews , 119(19):10856–10915, 2019. [91] Davide Castelvecchi. Quantum computers ready to leap out of the lab in 2017. Nature News ,541 (7635):9, 2017. [92] Rohit Chadha, Paulo Mateus, and Amílcar Sernadas. Reasoning about imperative quantum programs. Electronic Notes in Theoretical Computer Science , 158:19–39, 2006. [93] Shouvanik Chakrabarti, Andrew M Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. Quantum , 4:221, 2020. [94] YC Cheng and Robert J Silbey. Coherence in the b800 ring of purple bacteria lh2. Physical Review Letters , 96(2):028103, 2006. [95] Yuan-Chung Cheng, Gregory S Engel, and Graham R Fleming. Elucidation of population and coherence dynamics using cross-peaks in two-dimensional electronic spectroscopy. Chemical Physics , 341(1-3): 285–295, 2007. [96] Andrew M Childs. On the relationship between continuous-and discrete-time quantum walk. Communications in Mathematical Physics , 294(2):581–603, 2010. [97] Andrew M Childs and Jeffrey Goldstone. Spatial search by quantum walk. Physical Review A , 70(2): 022314, 2004. [98] Andrew M Childs and Robin Kothari. Limitations on the simulation of non-sparse hamiltonians. arXiv preprint arXiv:0908.4398 , 2009. [99] Andrew M Childs and Wim van Dam. Quantum algorithm for a generalized hidden shift problem. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms ,pages 1225–1232. Society for Industrial and Applied Mathematics, 2007. [100] Andrew M Childs and Wim Van Dam. Quantum algorithms for algebraic problems. Reviews of Modern Physics , 82(1):1, 2010. [101] Andrew M Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A Spielman. Exponential algorithmic speedup by a quantum walk. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing , pages 59–68, 2003. [102] Andrew M Childs, Richard Cleve, Stephen P Jordan, and David Yonge-Mallo. Discrete-query quantum algorithm for nand trees. arXiv preprint quant-ph/0702160 , 2007. 141