Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 13 of 13 for “"quantum query complexity"”.
-
Efficient algorithms in quantum query complexity
… we provide new upper and lower bounds on the quantum query complexity of a diverse set of problems. Specifically, we study quantum algorithms for Hamiltonian simulation, matrix multiplication, oracle identification, and graph-property recognition. For the Hamiltonian simulation problem, we …
-
Quantum Query Complexity of Hypergraph Search Problems
In the study of quantum query complexity, it is natural to study the problems of finding triangles and spanning trees in a simple graph. Over the past decades, many techniques are developed for finding the upper and lower quantum query bounds of these graph problems. We can generalize these …
-
A Generalized Adversary Method for Quantum Query Complexity
Quantum query complexity measures the minimum number of queries a quantum algorithm needs to make to some input string to compute a function of that input. Query complexity models are widely used throughout quantum computing, from setting limits on quantum algorithms to analyzing post-quantum …
-
Inherently quantum lower bounds on computational complexity
Computational complexity theory is usually phrased in terms of decision problems and Boolean functions, whose inputs and outputs are purely classical. However, many quantum computational tasks motivated by physics, machine learning, and cryptography involve operation on quantum information in a …
-
Frameworks for Quantum Algorithms
Due to the difficulty of constructing new quantum algorithms, frameworks that facilitate this construction are of great importance in quantum computing. These frameworks reduce the problem of coming up with a quantum algorithm to that of constructing some combinatorial object that is often much …
-
Quantum Algorithms for Memoryless Search and Perfect Matching
In this thesis, we present two new quantum algorithms for graph problems. The first algorithm we give is a memoryless walk that can find a unique marked vertex on a two-dimensional grid. Our walk is based on a construction proposed by Falk, which tessellates the grid with squares of size 2 × 2. Our …
-
Quantum Query Algorithms: Design, Optimality, Complexity
In this thesis we investigate quantum query algorithms from three perspectives: design paradigms, optimality, and complexity. First, we study how the divide and conquer paradigm---widely used in classical algorithm design---can be adapted to quantum algorithms. We leverage the quantum adversary …
-
Lower Bounds on Average-Case and Non-Local Quantum Computation
… limitations in both classical and quantum models of computation. It is organized into two parts, each addressing a different aspect of computational hardness. Despite their differences, both parts share a common goal: understanding how structural and physical constraints shape what …
-
Lower Bounds on Quantum Query and Learning Graph Complexities
In this thesis we study the power of quantum query algorithms and learning graphs; the latter essentially being very specialized quantum query algorithms themselves. We almost exclusively focus on proving lower bounds for these computational models. First, we study lower bounds on learning graph …
-
Variants of Pseudo-deterministic Algorithms and Duality in TFNP
… algorithms for search problems in query complexity. Roughly, for a search problem $\cS$, a faux-deterministic algorithm is a probability distribution $\mathcal{A}$ over deterministic algorithms $A\in \mathcal{A}$ such that no computationally bounded adversary making black-box …
-
Quantum Computation and Isomorphism Testing
In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our …