Search results for "computational complexity"
showing 10 items of 249 documents
Quantum lower bound for inverting a permutation with advice
2014
Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input $y$. Classically, there is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help of the data structure, given $f(x)$, can invert $f$ in time $\tilde{O}(T)$, for every choice of parameters $S$, $T$, such that $S\cdot T \ge N$. We prove a quantum lower bound of $T^2\cdot S \ge \tilde{\Omega}(\epsilon N)$ for quantum algorithms that invert a random permutation $f$ on an $\epsilon$ fraction of…
Classical and Quantum Annealing in the Median of Three Satisfiability
2011
We determine the classical and quantum complexities of a specific ensemble of three-satisfiability problems with a unique satisfying assignment for up to N = 100 and 80 variables, respectively. In the classical limit, we employ generalized ensemble techniques and measure the time that a Markovian Monte Carlo process spends in searching classical ground states. In the quantum limit, we determine the maximum finite correlation length along a quantum adiabatic trajectory determined by the linear sweep of the adiabatic control parameter in the Hamiltonian composed of the problem Hamiltonian and the constant transverse field Hamiltonian. In the median of our ensemble, both complexities diverge e…
Search by quantum walks on two-dimensional grid without amplitude amplification
2011
We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh (quant-ph/0402107) takes O(\sqrt{N log N}) steps and finds a marked location with probability O(1/log N) for grid of size \sqrt{N} * \sqrt{N}. This probability is small, thus amplitude amplification is needed to achieve \Theta(1) success probability. The amplitude amplification adds an additional O(\sqrt{log N}) factor to the number of steps, making it O(\sqrt{N} log N). In this paper, we show that despite a small probability to find a marked location, the probability to be within an O(\sqrt{N}) neighbourhood (at an O(\sqrt[4]{N}) distance) of the marked location is \Theta(1). This all…
Quantum-over-classical Advantage in Solving Multiplayer Games
2020
We study the applicability of quantum algorithms in computational game theory and generalize some results related to Subtraction games, which are sometimes referred to as one-heap Nim games. In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum combinatorial games with provable separation between quantum and classical complexity of solving them. For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms for finding solutions with probability $1$. Typically, both Nim and Subtraction games are defined for only two players. We extend some known results to games for t…
Parameterized Quantum Query Complexity of Graph Collision
2013
We present three new quantum algorithms in the quantum query model for \textsc{graph-collision} problem: \begin{itemize} \item an algorithm based on tree decomposition that uses $O\left(\sqrt{n}t^{\sfrac{1}{6}}\right)$ queries where $t$ is the treewidth of the graph; \item an algorithm constructed on a span program that improves a result by Gavinsky and Ito. The algorithm uses $O(\sqrt{n}+\sqrt{\alpha^{**}})$ queries, where $\alpha^{**}(G)$ is a graph parameter defined by \[\alpha^{**}(G):=\min_{VC\text{-- vertex cover of}G}{\max_{\substack{I\subseteq VC\\I\text{-- independent set}}}{\sum_{v\in I}{\deg{v}}}};\] \item an algorithm for a subclass of circulant graphs that uses $O(\sqrt{n})$ qu…
New Developments in Quantum Algorithms
2010
In this survey, we describe two recent developments in quantum algorithms. The first new development is a quantum algorithm for evaluating a Boolean formula consisting of AND and OR gates of size N in time O(\sqrt{N}). This provides quantum speedups for any problem that can be expressed via Boolean formulas. This result can be also extended to span problems, a generalization of Boolean formulas. This provides an optimal quantum algorithm for any Boolean function in the black-box query model. The second new development is a quantum algorithm for solving systems of linear equations. In contrast with traditional algorithms that run in time O(N^{2.37...}) where N is the size of the system, the …
Quantum property testing for bounded-degree graphs
2010
We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound. For testing expansion, we also prove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph s…
The Need for Structure in Quantum Speedups
2009
Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate. First, we show that for any problem that is invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 7th root of the classical randomized query complexity. (An earlier version of this paper gave the 9th root.) This resolves a conjecture of Watrous from 2002. Second, inspired by recent work of O'Donnell et al. (2005) and Dinur et al. (2006), we conjecture t…
Exact quantum query complexity of $\rm{EXACT}_{k,l}^n$
2016
In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly $k$ or $l$ of the $n$ input bits given by an oracle are 1. We find an optimal algorithm (for some cases), and a nontrivial general lower and upper bound on the minimum number of queries to the black box.
Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size
2009
This paper considers the query complexity of the functions in the family F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of inputs for which the function value is 1, where 1<= M <= 2^{N}/2 is assumed without loss of generality because of the symmetry of function values, 0 and 1. Our main results are as follows: (1) There is a super-linear gap between the average-case and worst-case quantum query complexities over F_{N,M} for a certain range of M. (2) There is no super-linear gap between the average-case and worst-case randomized query complexities over F_{N,M} for every M. (3) For every M bounded by a polynomial in N, any function in F_{N,M} has quantum que…