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"”.

  1. 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 …

    waterloo Repository record for Efficient algorithms in quantum query complexity (opens in a new tab)

  2. 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 …

    toronto-retro Repository record for Communication Lower Bounds via Query Complexity (opens in a new tab)

  3. 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 …

    waterloo Repository record for Query Complexity of Recursively Composed Functions (opens in a new tab)

  4. 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 …

    lethbridge Repository record for Parameterized query complexity in quantum computation (opens in a new tab)

  5. 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 …

    waterloo Repository record for Quantum Query Complexity of Hypergraph Search Problems (opens in a new tab)

  6. 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 …

    waterloo Repository record for Some Upper and Lower Bounds regarding Query Complexity (opens in a new tab)

  7. 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 …

    waterloo Repository record for A Generalized Adversary Method for Quantum Query Complexity (opens in a new tab)

  8. 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 …

    maryland Repository record for SYMMETRIC-KEY CRYPTOGRAPHY AND QUERY COMPLEXITY IN THE QUANTUM WORLD (opens in a new tab)

  9. 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 …

    waterloo Repository record for On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach (opens in a new tab)

  10. 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 …

    washington Repository record for Time-Space Tradeoffs and Query Complexity in Statistics, Coding Theory, and Quantum Computing (opens in a new tab)

  11. 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 …

    waterloo Repository record for The non-injective hidden shift problem (opens in a new tab)

  12. 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 …

    texas Repository record for Inherently quantum lower bounds on computational complexity (opens in a new tab)

  13. 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 …

    nus Repository record for DIRECT PRODUCT, FUNCTION COMPOSITION AND DEVICE-INDEPENDENT CRYPTOGRAPHY (opens in a new tab) Download file for DIRECT PRODUCT, FUNCTION COMPOSITION AND DEVICE-INDEPENDENT CRYPTOGRAPHY (opens in a new tab)

  14. 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.

    waterloo Repository record for Monotonicity Testing for Boolean Functions over Graph Products (opens in a new tab)

  15. 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 …

    bristol Repository record for Quantum Algorithms and Complexity in Non-standard Models (opens in a new tab) Download PDF for Quantum Algorithms and Complexity in Non-standard Models (opens in a new tab)

  16. 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 …

    oxford Repository record for Equilibrium computation in games and strategic aspects of bitcoin mining (opens in a new tab)

  17. 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 …

    regina Repository record for Learning hypertrees with shortest path queries (opens in a new tab)

  18. 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 …

    waterloo Repository record for Frameworks for Quantum Algorithms (opens in a new tab)

Page 1 of 4