This thesis focuses on two different aspects of quantum computation: quantum complexity and quantum semantics. In the first part, I study the quantum complexity mainly within the quantum query model. Together with my colleagues, I introduce a new framework for quantum query complexity, phrased in terms of the minimal oracle and analyse limits and strengths of this new model in comparison to their classical and quantum counterparts. Working within the query model I study quantum one-way functions. I show that in the quantum setting, the problem of the existence of a quantum one-way permutation can be reduced to the problem of constructing polynomial size networks for performing the specific task of the reflection about a sequence of states. Furthermore, I extend these results to the domain of the state and operator complexity. I show that if a quantum one-way function exists, then we can construct a sequence of so called “hard” states with the property that the reflection operators about those states are efficiently implementable. In the second part, I study the extension of domain theory to the quantum setting and develop the semantics of quantum computation. By defining a quantum domain I introduce a rigourous definition of quantum computability for quantum states and operators. Furthermore I show that the denotational semantics of quantum computation has the same semantical structure as the denotational semantics of classical probabilistic computation introduced by Kozen. This could be considered as a foundation for designing functional programming languages for quantum computation. Finally, I continue with an abstract mathematical approach to study a general formalism for describing entanglement manipulation and introduce a new approach to derive a unique measure of entanglement for bipartite quantum pure states.
This thesis focuses on two different aspects of quantum computation: quantum complexity and quantum semantics. In the first part, I study the quantum complexity mainly within the quantum query model. Together with my colleagues, I introduce a new framework for quantum query complexity, phrased in terms of the minimal oracle and analyse limits and strengths of this new model in comparison to their classical and quantum counterparts. Working within the query model I study quantum one-way functions. I show that in the quantum setting, the problem of the existence of a quantum one-way permutation can be reduced to the problem of constructing polynomial size networks for performing the specific task of the reflection about a sequence of states. Furthermore, I extend these results to the domain of the state and operator complexity. I show that if a quantum one-way function exists, then we can construct a sequence of so called “hard” states with the property that the reflection operators about those states are efficiently implementable. In the second part, I study the extension of domain theory to the quantum setting and develop the semantics of quantum computation. By defining a quantum domain I introduce a rigourous definition of quantum computability for quantum states and operators. Furthermore I show that the denotational semantics of quantum computation has the same semantical structure as the denotational semantics of classical probabilistic computation introduced by Kozen. This could be considered as a foundation for designing functional programming languages for quantum computation. Finally, I continue with an abstract mathematical approach to study a general formalism for describing entanglement manipulation and introduce a new approach to derive a unique measure of entanglement for bipartite quantum pure states.
The last decade witnessed a great surge of fruitful studies in the new paradigm of quantum computing. Remarkable progress has been made in all the areas including quantum algorithms, quantum complexity theory, quantum error-correcting code, quantum information theory, quantum cryptography and physical implementations of quantum computers. However, quantum algorithm design, probably the most important task in quantum computing, did not make as much progress as people expected. This thesis aims at both designing new quantum algorithms and studying why efficient quantum algorithms are so hard to design by proving many lower bounds on quantum query complexity for various problems.
We first review (and generalize) known techniques for designing quantum algorithms and for proving quantum lower bounds. Using these techniques, we then study the quantum query complexity for many problems, including some specific problems such as Graph Matching and other natural graph properties, the general tuple search, and local search. We also study the lowest possible quantum query complexity for a class of functions as a whole, such as graph properties, circular functions, and functions invariant of a transitive permutation group, where tight results are given in all these cases.
Finally for the quantum lower bounds techniques themselves, we study the main two techniques and show that they are incomparable in power. For the most widely used one, which has a lot of parameters to choose, we show limitations for it in terms of certificate complexity. This implies that we cannot use the method to prove better lower bounds for almost all known open problems in this area.
In this thesis, Quantum computing, norms, and polynomials, we investigate the interplay between quantum mechanics, complexity theory, and functional analysis, three central areas of physics, computer science, and mathematics, respectively. The unifying theme throughout the thesis is the dynamic exchange between quantum computing and functional analysis: we explore new applications of functional inequalities in quantum computing, and, in the process, establish novel results in functional analysis itself. In the first part, we study quantum query algorithms through their correspondence with completely bounded polynomials, as established in earlier work. We begin by revisiting this correspondence, extending it, and presenting it in a new form. Building on this foundation, we draw an analogy between quantum query algorithms and the Grothendieck inequality. Finally, we conclude this part by employing completely bounded polynomials to solve a special case of one of the main open problems in quantum query complexity, the Aaronson–Ambainis conjecture. In the second part, we turn to quantum learning theory, which seeks to determine how much information must be extracted from a quantum system to fully characterize it. We begin by applying existing versions of the Bohnenblust–Hille inequalities and deriving new ones to obtain results in the learning of low-degree quantum objects. We conclude by presenting some of the first results in the emerging area of Hamiltonian testing and learning. We also include a third part, as a bonus, where we gather three new proofs, that we find elegant and concise, of known results related to the analysis of Boolean functions.
This dissertation studies the interplay between quantum and classical computational resources through the lens of computational complexity theory. Part I considers low-energy states of quantum systems. We study the complexity of estimating ground- and excited-state energies of local Hamiltonians, given access to a guiding state promised to have non-negligible overlap with the relevant eigenspace. We formalise access models for such guiding states, examine their properties and relations, and study the problem for physically motivated Hamiltonians. We also study the task of obtaining approximate descriptions of ground states, given QMA-oracle access, in the setting of low-locality reduced density matrices. Part II focuses on quantum probabilistically checkable proof systems (QPCPs). We define a general class of QPCPs that allows adaptivity and multiple unentangled provers, and study its relationship to constant-gap local Hamiltonian problems via quantum reductions. Additionally, we investigate quantum–classical PCPs (QCPCPs), where a quantum verifier has either classical or quantum query access to a classical proof. Part III explores alternative complexity measures: unitary query complexity and sample complexity. For unitary query complexity, we develop a lower-bound technique based on unitary channel discrimination. In the context of sample complexity, we introduce and analyse a new sample-to-sample task, called complement sampling, and study the power of quantum computation with quantum samples over their classical counterparts.
In this thesis, we study quantum programming languages, and focus on the quantum lambda-calculus, a paradigmatic language defined by Selinger and Valiron, which mixes a rich classical control flow (higher order functions, etc.) and quantum data (qubit creation, measure, and unitary operations). In this thesis, we search for a denotational semantics of this language, in other words, we extract the meaning and behaviour of programs by interpreting them in an adequately chosen mathematical universe. In order to model the quantum lambda-calculus, one must adapt the traditional denotational models to the mathematics of quantum computation (Hilbert spaces, density matrices, etc.). We have three main contributions:Firstly, we extend game semantics to the quantum case. Game semantics is a dynamic approach to denotational semantics, which focuses on the sequence of interactions between a program and its environment. We obtain the first denotational model of the full quantum lambda-calculus which is both compositional and interactive, meaning that it represents the dynamic of the execution. Our model generalise the recently developed model for the probabilistic case.Secondly, we formally link our model to the only pre-existing denotational model of the full lambda-calculus, the quantum relational model of Pagani, Selinger and Valiron.Lastly, we prove that our game model is fully abstract, the gold standard of denotational semantics, which ensures a total correspondence between the programming language and the model. We deduce that the quantum relational model was also fully abstract, which was an open problem.This thesis is constituted of three parts. The first part details some preliminaries on category theory, used for defining a formal framework including both the quantum game model and the quantum relational model, some preliminaries on the mathematics of quantum computation, and then some preliminaries on quantum programming and its models. The second part starts with some preliminaries on game semantics and defines our quantum game model in the simplified case of the linear quantum lambda-calculus. The third part builds on the second part to define the full quantum game model, prove its full abstraction, and deduce that the quantum relational model is fully abstract too.
Quantum computing represents a transformative approach to computation that exploits the principles of quantum mechanics to process information in fundamentally different ways from classical computers. Over the past few decades, the field has evolved from a primarily theoretical discipline into an active area of research spanning computer science, mathematics, physics, information theory, and engineering. As quantum technologies continue to develop, understanding the fundamental computational principles underlying quantum algorithms has become increasingly important. Foundations of Quantum Computing: The Query Model Perspective presents a systematic introduction to quantum computing with particular emphasis on the query model, a powerful framework for studying the computational complexity of quantum algorithms. The query model provides a clean and mathematically tractable setting in which the number of queries made to an unknown function or oracle can be used as the primary measure of computational cost. This perspective offers valuable insights into the capabilities and limitations of quantum computation and provides a natural foundation for understanding quantum speedups. The book introduces the fundamental concepts required to study quantum computation, including quantum states, quantum gates, quantum circuits, measurement, superposition, entanglement, and quantum algorithms. These concepts are developed alongside the query-complexity framework, enabling readers to understand how quantum algorithms exploit interference and other quantum phenomena to reduce the number of queries required to solve computational problems. Particular attention is given to important quantum query algorithms and complexity results. Classical and quantum query complexities are discussed comparatively to illustrate the sources and significance of quantum advantages. Well-known examples such as the Deutsch–Jozsa algorithm, Grover's search algorithm, and related oracle-based problems provide concrete illustrations of how quantum procedures can outperform their classical counterparts. The discussion also introduces lower-bound techniques and fundamental principles that help establish the limitations of quantum query algorithms. The query model is not only useful for understanding individual algorithms but also serves as an important bridge between quantum algorithms and computational complexity theory. By focusing on query complexity, many problems can be examined independently of the details of a particular physical implementation. This abstraction makes the framework especially useful for developing rigorous proofs, comparing computational resources, and identifying the fundamental sources of quantum advantage. This book is intended for students, researchers, educators, and professionals interested in quantum computing and theoretical computer science. It can serve as an introductory reference for readers with a background in discrete mathematics, linear algebra, algorithms, or theoretical computer science, while also providing a foundation for readers who wish to pursue more advanced studies in quantum complexity theory and quantum algorithms. The chapters have been organized to progress from foundational concepts toward more advanced aspects of the quantum query model. Mathematical formulations are accompanied by explanations and examples to help readers connect abstract theoretical ideas with computational intuition. The broader objective is to provide readers with the tools necessary not only to understand existing quantum algorithms but also to reason about new problems from a query-complexity perspective. As quantum computing continues to mature, the ability to distinguish genuine computational advantages from implementation-specific effects will become increasingly significant. The query model provides one of the clearest theoretical environments for making this distinction. By studying quantum computation through this lens, readers can develop a deeper appreciation of both the power and the limitations of quantum algorithms It is hoped that Foundations of Quantum Computing: The Query Model Perspective will serve as a useful resource for learning, teaching, and research, and will encourage further exploration into the rapidly evolving landscape of quantum computation and quantum complexity theory.
Query complexity provides a basic framework to quantify the inherent computational cost of functions in the model where access to the input is limited to oracle queries. In this paper, we provide a detailed discussion of classical and quantum models of inquiry, emphasizing the structural differences and the common mathematical basis. We consider deterministic, randomized and quantum query complexities and highlight key techniques to prove lower bounds such as adversarial techniques, polynomial approximations and hybrid arguments . The main theme of this paper is the polynomial-spectral relation which underlies both the classical and the quantum models. In the classical setting, the decision tree complexity is closely related to the degree of real polynomials representing Boolean functions. In the quantum setting, the relation involves the spectral properties of the operators controlling quantum query algorithms, and gives deep insights into quantum accelerations. We study tight bounds for basic problems such as search and element distinctness, proving separations between classical and quantum query complexity. The present study uses methods from approximation theory, linear algebra and spectrum analysis to build a foundation for a complete understanding of the power and limitations of query-based computation.