This thesis explores the interplay between structure and randomness in quantum computation, with the goal being to characterise the types of structure that give quantum computers an advantage over classical computation. The thesis begins by giving a necessary and sufficient condition for one notion of a quantum walk to be defined on a directed graph, and goes on to derive conditions on the structure of graphs that allow a quantum advantage in a non-local graph colouring game. A lower bound on entanglement-assisted quantum communication complexity based on information-theoretic ideas is given, and applied to the communication complexity of random functions. New lower bounds on the probability of success of quantum state discrimination are derived, and are applied to the problem of distinguishing random quantum states. This result is used to show a quantum advantage in almost all instances of a bounded-error single-query oracle identification problem. Lower bounds, and almost optimal algorithms, are given for two models of quantum search of partially ordered sets. This leads to the development of an optimal quantum algorithm to find the intersection of two sorted lists.
This thesis explores the interplay between structure and randomness in quantum computation, with the goal being to characterise the types of structure that give quantum computers an advantage over classical computation. The thesis begins by giving a necessary and sufficient condition for one notion of a quantum walk to be defined on a directed graph, and goes on to derive conditions on the structure of graphs that allow a quantum advantage in a non-local graph colouring game. A lower bound on entanglement-assisted quantum communication complexity based on information-theoretic ideas is given, and applied to the communication complexity of random functions. New lower bounds on the probability of success of quantum state discrimination are derived, and are applied to the problem of distinguishing random quantum states. This result is used to show a quantum advantage in almost all instances of a bounded-error single-query oracle identification problem. Lower bounds, and almost optimal algorithms, are given for two models of quantum search of partially ordered sets. This leads to the development of an optimal quantum algorithm to find the intersection of two sorted lists.
This thesis establishes a number of connections between foundational issues in quantum theory, and some quantum information applications. It starts with a review of quantum contextuality and non-locality, multipartite entanglement characterisation, and of a few quantum information protocols. Quantum non-locality and contextuality are shown to be essential for different implementations of quantum information protocols known as quantum random access codes and quantum communication complexity protocols. I derive sufficient experimental conditions for tests of these quantum properties. I also discuss how the distribution of quantum information through quantum cloning processes can be useful in quantum computing. Regarding entanglement characterisation, some results are obtained relating two problems, that of additivity of the relative entropy of entanglement, and that of identifying different types of tripartite entanglement in the asymptotic regime of manipulations of many copies of a given state. The thesis ends with a description of an information processing task in which a single qubit substitutes for an arbitrarily large amount of classical communication. This result is interpreted in different ways: as a gap between quantum and classical computation space complexity; as a bound on the amount of classical communication necessary to simulate entanglement; and as a basic result on hidden-variable theories for quantum mechanics. I also show that the advantage of quantum over classical communication can be established in a feasible experiment.
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.
What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.
We provide a rigorous theoretical analysis of quantum algorithms for shortest path problems in weighted graphs, establishing complexity-theoretic foundations for quantum acceleration in this fundamental computational domain. Building upon recent quantum adaptations of classical graph algorithms, we develop a unified framework that characterizes when and why quantum approaches offer computational advantages for single-source and all-pairs shortest path computations. Our analysis encompasses both positive-weight and negative-weight scenarios, deriving conditional speedup theorems that depend on graph structure, weight distribution, and oracle access models. We prove that quantum amplitude amplification and quantum walks can provide polynomial to exponential speedups under specific structural assumptions, while establishing hardness results that identify problem instances where quantum advantage is provably absent. The theoretical framework introduces novel complexity measures that capture graph-theoretic properties relevant to quantum algorithm performance, including quantum diameter, entanglement capacity, and interference efficiency. We extend our analysis to dynamic graph scenarios where edge weights evolve over time, establishing bounds on quantum advantage preservation under graph modifications. This work contributes fundamental insights into quantum algorithmic graph theory, clarifying the boundaries of quantum computational advantage and providing theoretical guidance for algorithm design in network optimization, routing, and graph analytics applications.
Quantum computing has attracted a lot of attention in different research fields, such as mathematics, physics and computer science. Quantum algorithms can solve certain problems significantly faster than classical algorithms. There are many numerical problems, especially those arising from quantum systems, which are notoriously difficult to solve using classical computers, since the computational time required often scales exponentially with the size of the problem. However, quantum computers have the potential to solve these problems efficiently, which is also one of the founding ideas of the field of quantum computing. In this thesis, we explore five computational problems, designing innovative quantum algorithms and studying their computational complexity. First, we design an adiabatic quantum algorithm based on the Berry phases for the counting problem. For the running time, it is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result should be robust to decoherence and resilient to certain kinds of noise. Since the counting problem is the foundation of many other numerical problems, such as high-dimensional integration and path integration, our adiabatic algorithms can be directly generalized to these kinds of problems. In addition, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. The lower bound is very close to the best lower bound on query complexity known for the classical PAC learning model. We also study the algorithms and the cost of simulating a system evolving under a given Hamiltonian. We consider high order splitting methods that are particularly applicable in quantum simulation and obtain bounds on the number of exponentials required. Moreover, we derive the optimal order of convergence given the required error bound. We compare our complexity estimates to previously known ones and show the resulting speedup. Furthermore, we consider randomized algorithms for Hamiltonian simulation. The evolution is simulated by a product of exponentials in a random sequence and random evolution times. Hence the final state of the system is approximated by a mixed quantum state. We provide a scheme to bound the error of the final quantum state in a randomized algorithm, and obtain randomized algorithms which have the same efficiency as certain deterministic algorithms but which are simpler to implement. We also apply Hamiltonian simulation in estimating the ground state energy of a multiparticle system, which is also known as the multivariate Sturm-Liouville eigenvalue problem. Since the cost of this problem grows exponentially with the number of particles using deterministic classical algorithms, it suffers from the curse of dimensionality. Quantum computers can vanquish the curse, and we exhibit a quantum algorithm whose total cost are linear in the number of particles.
In this thesis, I study how quantum computation and quantum communication can help large networks of computers to solve computational problems faster. I also connect the notion of locality between various models, including distributed quantum algorithms and online graph algorithms, and show that locality in online graph algorithms can be used to provide bounds for distributed quantum advantage. Towards proving distributed quantum advantage, I present the first family of LCL problems which shows a quantum advantage for distributed graph algorithms. Here LCLs, or Locally Checkable Labeling problems, are a family of graph problems described by a finite set of local constraints, and I mainly focus on them in this thesis. The models of distributed computing which this result separates are the classical LOCAL model and the quantum-LOCAL model. In both of these models, a network of computers exchanges messages in synchronous rounds, and the running time of the algorithm directly corresponds with locality, that is, how far the computers see in the network. In this thesis, I also introduce new models of computing that capture locality in stronger settings. Most notably, I introduce the online-LOCAL model which captures the locality of online graph algorithms, and show that it is, asymptotically, roughly as strong as the classical LOCAL model for solving LCL problems on rooted regular trees. I provide an online-LOCAL algorithm for finding a 3-coloring of a bipartite graph with lower locality than is possible in the classical LOCAL model, and show that the algorithm is tight. To draw things together, I show that quantum-LOCAL and online-LOCAL are indeed related to each other: any quantum-LOCAL algorithm can be simulated in the randomized online-LOCAL model. The converse does not hold in general, but an online-LOCAL algorithm solving an LCL problem in rooted, possibly non-regular, trees can be simulated in the classical LOCAL model—and thus in the quantum-LOCAL model—with an exponential cost in locality, putting indirectly a bound on the maximum possible attainable quantum advantage. Finally, I consider the sinkless orientation problem, which holds a central role in our understanding of the locality of LCL problems in the classical LOCAL model, and provide a simpler and more direct proof for its hardness using the supported LOCAL model. I also provide a simpler algorithm solving sinkless orientation in the SLOCAL model, which is a sequential version of the LOCAL model.