Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOracles with Costs
293
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grovers algorithm, that our algorithm is exactly optimal.
rate research
Read More
Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactly and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations is considered through a bit-complexity analysis. Yet in practice, implementations typically use limited-precision arithmetic. In this paper we introduce the idea of a limited-precision LP oracle and study how such an oracle could be used within a larger framework to compute exact precision solutions to LPs. Under mild assumptions, it is shown that a polynomial number of calls to such an oracle and a polynomial number of bit operations, is sufficient to compute an exact solution to an LP. This work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly.
We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracles, and we examine the efficiency of reductions between the different oracles. In particular, we show how a separation oracle can be implemented using $tilde{O}(1)$ quantum queries to a membership oracle, which is an exponential quantum speed-up over the $Omega(n)$ membership queries that are needed classically. We show that a quantum computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with a simplification of recent classical work of Lee, Sidford, and Vempala gives our efficient separation oracle. This in turn implies, via a known algorithm, that $tilde{O}(n)$ quantum queries to a membership oracle suffice to implement an optimization oracle (the best known classical upper bound on the number of membership queries is quadratic). We also prove several lower bounds: $Omega(sqrt{n})$ quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and $Omega(n)$ quantum separation queries are needed if it does not.
Selecting a set of basis states is a common task in quantum computing, in order to increase and/or evaluate their probabilities. This is similar to designing WHERE clauses in classical database queries. Even though one can find heuristic methods to achieve this, it is desirable to automate the process. A common, but inefficient automation approach is to use oracles with classical evaluation of all the states at circuit design time. In this paper, we present a novel, canonical way to produce a quantum oracle from an algebraic expression (in particular, an Ising model), that maps a set of selected states to the same value, coupled with a simple oracle that matches that particular value. We also introduce a general form of the Grover iterate that standardizes this type of oracle. We then apply this new methodology to particular cases of Ising Hamiltonians that model the zero-sum subset problem and the computation of Fibonacci numbers. In addition, this paper presents experimental results obtained on real quantum hardware, the new Honeywell computer based on trapped-ion technology with quantum volume 64.
A standard quantum oracle $S_f$ for a general function $f: Z_N to Z_N $ is defined to act on two input states and return two outputs, with inputs $ket{i}$ and $ket{j}$ ($i,j in Z_N $) returning outputs $ket{i}$ and $ket{j oplus f(i)}$. However, if $f$ is known to be a one-to-one function, a simpler oracle, $M_f$, which returns $ket{f(i)}$ given $ket{i}$, can also be defined. We consider the relative strengths of these oracles. We define a simple promise problem which minimal quantum oracles can solve exponentially faster than classical oracles, via an algorithm which cannot be naively adapted to standard quantum oracles. We show that $S_f$ can be constructed by invoking $M_f$ and $(M_f)^{-1}$ once each, while $Theta(sqrt{N})$ invocations of $S_f$ and/or $(S_f)^{-1}$ are required to construct $M_f$.
We consider the problem of choosing the best of $n$ samples, out of a large random pool, when the sampling of each member is associated with a certain cost. The quality (worth) of the best sample clearly increases with $n$, but so do the sampling costs, and one important question is how many to sample for optimal gain (worth minus costs). If, in addition, the assessment of worth for each sample is associated with some measurement error, the perceived best out of $n$ might not be the actual best, complicating the issue. Situations like this are typical in mate selection, job hiring, and food foraging, to name just a few. We tackle the problem by standard order statistics, yielding suggestions for optimal strategies, as well as some unexpected insights.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
