A Comparison of Quantum Oracles

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 $|i⟩$ and $|j⟩$ ($i,j\in Z_N$) returning outputs $|i⟩$ and $|j\oplus f(i)⟩$. However, if $f$ is known to be a one-to-one function, a simpler oracle, $M_f$, which returns $|f(i)⟩$ given $|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$.

4 pages, 1 figure; Final version, with an extended discussion of oracle inverses. To appear in Phys Rev A

References in corpus (1)

• Quantum fingerprinting

Cited by in corpus (16)

• Quantum walks: a comprehensive review
• Exploiting entanglement in communication channels with correlated noise
• Quantum boolean functions
• Nonlinear Quantum Neuron: A Fundamental Building Block for Quantum Neural Networks
• Semantic Security and Indistinguishability in the Quantum World
• Unambiguous discrimination among oracle operators
• Strategy for quantum algorithm design assisted by machine learning
• Limits on Efficient Computation in the Physical World
• A genetic-algorithm-based method to find the unitary transformations for any de- sired quantum computation and application to a one-bit oracle decision problem
• Framework for learning agents in quantum environments
• Comparison of mixed quantum states
• Optimal and asymptotically optimal NCT reversible circuits by the gate types
• Distributed implementation of standard oracle operators
• Comparative Computational Strength of Quantum Oracles
• Modular quantum computing and quantum-like devices
• Quantum Indistinguishability for Public Key Encryption