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 20 of 79 for “"query complexity"”.
-
Efficient algorithms in quantum query complexity
… 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 provide a …
-
Communication Lower Bounds via Query Complexity
… thesis is to prove lower bounds in communication complexity by exploiting new connections to query complexity. Our basic strategy is to first prove a general theorem stating that for a large class of communication problems F, any protocol for F can be efficiently simulated by a decision tree …
-
Query Complexity of Recursively Composed Functions
… explore two well-studied notions of randomized query complexity; bounded-error randomized ($\R(f)$), and zero-error randomized ($\R_0(f)$). These have their natural analogues from the classical model of computation, $\R$ corresponding to BPP or ``Monte Carlo" algorithms and $\R_0$ to ZPP or …
-
Parameterized query complexity in quantum computation
… nor balanced. Our proposal is to analyze the query complexity of two such functions as a function of some parameter. We apply the methodology to two different problems. We parameterize the degree of imbalance for an arbitrarily chosen function. The same parameterization is used for 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 …
-
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 …
-
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 …
-
SYMMETRIC-KEY CRYPTOGRAPHY AND QUERY COMPLEXITY IN THE QUANTUM WORLD
… permutation inversion problem in the quantum query model. In this problem, given an image y and quantum oracle access to a permutation P (and its inverse oracle), the goal is to find its pre-image x such that P(x)=y. We prove an optimal lower bound \Omega(\sqrt{2^n}) for this problem against …
-
On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach
… data mining. We establish the first Statistical Query hardness result for semiautomata under the uniform distribution over input words and initial states. We show that Statistical Query hardness can be established when both the alphabet size and input length are polynomial in the number of …
-
Time-Space Tradeoffs and Query Complexity in Statistics, Coding Theory, and Quantum Computing
Computational complexity is the field that studies the computational resources needed by algorithms to correctly solve computational problems. In this thesis, we derive lower bounds on the computational complexity of different problems for different classes of algorithms. The computational …
-
The non-injective hidden shift problem
… functions. It is worthwhile to know that the query complexity of the non-injective hidden shift problem is exponential in the worst case by the well known bounds on the unstructured search problem. Hence, we can make this problem more tractable by imposing additional constraints on the …
-
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 …
-
DIRECT PRODUCT, FUNCTION COMPOSITION AND DEVICE-INDEPENDENT CRYPTOGRAPHY
… study direct product and composition theorems in query complexity, communication complexity and non-local games, and show applications of these results in device-independent cryptography. The first part of the thesis deals with direct product and composition theorems. Our first result in this part …
-
Monotonicity Testing for Boolean Functions over Graph Products
… use this inequality to obtain new bounds on the query complexity for testing monotonicity of Boolean-valued functions over products of general posets.
-
Quantum Algorithms and Complexity in Non-standard Models
… ingredients.<br/>The quantum computational complexity of estimating a natural mathematical quantity, the Schatten p-norm of a matrix, is studied and found to be closely related to the one clean qubit model – a restricted model of quantum computing inspired by NMR. It is shown that this …
-
Equilibrium computation in games and strategic aspects of bitcoin mining
… this thesis is twofold: on one hand we study the query complexity of equilibrium computation in games, and on the other hand, we use equilibrium concepts from game theory as a tool to understand miner incentives in Bitcoin. In terms of query complexity, we mostly focus on algorithms that have …
-
Learning hypertrees with shortest path queries
… using shortest path (SP) queries. An SP query specifies two vertices and asks for their distance in the target hypergraph. For various classes H of hypertrees, we present bounds on the number of queries required to learn an unknown hypertree from H. Matching upper and lower asymptotic …
-
Frameworks for Quantum Algorithms
… a corresponding quantum algorithm with better complexity immediately follows. In this framework, a generic algorithm is constructed from several subroutines for which implementations must be given for each application. One of these subroutines, a checking subroutine, is run many times …
Page 1 of 4