Simplified Quantum Algorithm for the Oracle Identification Problem

2021-09-08 · Leila Taghavi

In the oracle identification problem we have oracle access to bits of an unknown string $x$ of length $n$, with the promise that it belongs to a known set $C\subseteq\{0,1\}^n$. The goal is to identify $x$ using as few queries to the oracle as possible. We develop a quantum query algorithm for this problem with query complexity $O\left(\sqrt{\frac{n\log M }{\log(n/\log M)+1}}\right)$, where $M$ is the size of $C$. This bound is already derived by Kothari in 2014, for which we provide a more elegant simpler proof.

📄 PDF Abstract BibTeX arXiv:2109.03902

Code (0)

등록된 구현이 없습니다.

Quantum oracles give an advantage for identifying classical counterfactuals

2025-12-15 · Ciarán M. Gilligan-Lee, Yìlè Yīng, Jonathan Richens, David Schmid arxiv

We show that quantum oracles provide an advantage over classical oracles for answering classical counterfactual questions in causal models, or equivalently, for identifying unknown causal parameters such as distributions…

Quantum algorithms for learning a hidden graph and beyond

2020-11-17 · Ashley Montanaro, Changpeng Shao

We study the problem of learning an unknown graph provided via an oracle using a quantum algorithm. We consider three query models. In the first model ("OR queries"), the oracle returns whether a given subset of the vert…

Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets

2022-05-30 · Zongqi Wan, Zhijie Zhang, Tongyang Li, Jialin Zhang 외

Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horizon $T$ suffer $\Omega(\sqrt{T})$ regret.…

Multi-Armed Bandits reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Quantum Machine Learning and Grover's Algorithm for Quantum Optimization of Robotic Manipulators

2025-09-08 · Hassen Nigatu, Shi Gaokun, Li Jituo, Wang Jin 외 arxiv

Optimizing high-degree of freedom robotic manipulators requires searching complex, high-dimensional configuration spaces, a task that is computationally challenging for classical methods. This paper introduces a quantum …

Quantum Machine Learning

Quantum algorithms for escaping from saddle points

2020-07-20 · Chenyi Zhang, Jiaqi Leng, Tongyang Li

We initiate the study of quantum algorithms for escaping from saddle points with provable guarantee. Given a function $f\colon\mathbb{R}^{n}\to\mathbb{R}$, our quantum algorithm outputs an $\epsilon$-approximate second-o…