Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Comparison of Quantum Oracles
96
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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.
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.
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.
This paper describes a novel approach to solving unstructured search problems using a classical, signal-based emulation of a quantum computer. The classical nature of the representation allows one to perform subspace projections in addition to the usual unitary gate operations. Although bandwidth requirements will limit the scale of problems that can be solved by this method, it can nevertheless provide a significant computational advantage for problems of limited size. In particular, we find that, for the same number of noisy oracle calls, the proposed subspace projection method provides a higher probability of success for finding a solution than does an single application of Grovers algorithm on the same device.
This paper explores two circuit approaches for quantum walks: the first consists of generalised controlled
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
