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 12 of 12 for “"Quantum Complexity Theory"”.
-
Combinatorial algorithms for perturbation theory and application on quantum computing
Quantum computing is an emerging area between computer science and physics. Numerous problems in quantum computing involve quantum many-body interactions. This dissertation concerns the problem of simulating arbitrary quantum many-body interactions using realistic two-body interactions. To address …
-
Lee-Yang Tensors in Quantum Information and Algorithms for Local Hamiltonian Problems
Local Hamiltonian problems are central to both quantum complexity theory and quantum many-body physics: ground state problems are the natural quantum constraint satisfaction problems, and computing the partition function reveals thermal equilibrium properties. A turning point in the theory of local …
-
Quantum meets optimization and machine learning
With the advent of the quantum era, what role the quantum computer will play in optimization and machine learning becomes a natural and salient question. The development of novel quantum computing techniques is essential to showcase the quantum advantage in these fields. At the same time, new …
-
Cryptographic Applications of the Quantum No-Cloning Principle for Messages, Programs, and Advice
… to perfectly replicate the state of an arbitrary quantum system. From its early beginnings with Wiesner, Bennett, and Brassard, quantum cryptography has often relied, either implicitly or explicitly, on this principle to achieve security properties beyond the reach of classical cryptography. We …
-
Some Upper and Lower Bounds regarding Query Complexity
Query complexity is one of the several notions of complexity de ned to measure the cost of algorithms. It plays an important role in demonstrating the quantum advantage, that quantum computing is faster than classical computation in solving some problems. Kempe showed that a discrete time quantum …
-
Extended Nonlocal Games
… are among the most striking ingredients found in quantum information theory. One tool to better understand these notions is the model of nonlocal games; a mathematical framework that abstractly models a physical system. The simplest instance of a nonlocal game involves two players, Alice and Bob, …
-
Algebraic Methods in Query and Proof Complexity
… have become a powerful tool for analyzing the complexity of various computational models, including low-depth circuits, algebraic proofs, and quantum query algorithms. In particular, the complexity of computing a function in these models is related to whether or not the function admits a …
-
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 …
-
Distinguishability, Symmetry, and Energy Estimation: Quantum Algorithms and Complexity
Quantum computing is a relatively new computing paradigm that seeks to use quantum resources, like superposition and entanglement, to process information in a significantly new way. These resources allow quantum computers to solve certain problems more efficiently than their classical counterparts, …
-
Quantum complexity of physically inspired problems and computational resources
… presents results on the computational complexity of problems and resources inspired by quantum physics. These contributions sharpen the computational challenges posed by quantum systems and clarify the physical limits of computation in a quantum world. The first part studies the …
-
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 …
-
QUANTUM COMBINATORIAL OPTIMIZATION ALGORITHMS FOR PACKING PROBLEMS IN CLASSICAL COMPUTING AND NETWORKING
… find good solutions. With recent developments in quantum meta-heuristic methods and promising results in experimental quantum computing systems, quantum computing is rapidly becoming more and more relevant for complex real-world combinatorial optimization tasks. This thesis is about applications …