In the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set C of size M and our task is to identify x. We present a quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm considerably simplifies and improves the previous best algorithm due to Ambainis et al. Our algorithm also has applications in quantum learning theory, where it improves the complexity of exact learning with membership queries, resolving a conjecture of Hunziker et al. The algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered $γ_2$ -norm semidefinite program, which characterizes quantum query complexity. Our composition theorem is quite general and allows us to compose quantum algorithms with input-dependent query complexities without incurring a logarithmic overhead for error reduction. As an application of the composition theorem, we remove all log factors from the best known quantum algorithm for Boolean matrix multiplication.In the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set C of size M and our task is to identify x. We present a quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm considerably simplifies and improves the previous best algorithm due to Ambainis et al. Our algorithm also has applications in quantum learning theory, where it improves the complexity of exact learning with membership queries, resolving a conjecture of Hunziker et al. The algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered $γ_2$-norm semidefinite program, which characterizes quantum query complexity. Our composition theorem is quite general and allows us to compose quantum algorithms with input-dependent query complexities without incurring a logarithmic overhead for error reduction. As an application of the composition theorem, we remove all log factors from the best known quantum algorithm for Boolean matrix multiplication.

arXiv:1311.7685Leibniz international proceedings in informaticsNov 29, 201320 citations

Improved Bounds on Quantum Learning Algorithms

Alp Atıcı, Rocco A. Servedio

arXiv:quant-ph/0411140Quantum Information ProcessingOct 18, 200567 citations

Quantum learning algorithms for quantum measurements

Alessandro Bisio, Giacomo Mauro D’Ariano, Paolo Perinotti +1 more

arXiv:1103.0480Physics Letters AAug 15, 201128 citations

Learning-Graph-Based Quantum Algorithm for k-distinctness

Aleksandrs Belovs

We present a quantum algorithm solving the $k$ -distinctness problem in $O(n^{1-2^{k-2}/(2^k-1)})$ queries with a bounded error. This improves the previous $O(n^{k/(k+1)})$ -query algorithm by Ambainis. The construction uses a modified learning graph approach. Compared to the recent paper by Belovs and Lee arXiv:1108.3022, the algorithm doesn't require any prior information on the input, and the complexity analysis is much simpler. Additionally, we introduce an $O(\sqrt{n}α^{1/6})$ algorithm for the graph collision problem where $α$ is the independence number of the graph.We present a quantum algorithm solving the $k$-distinctness problem in $O(n^{1-2^{k-2}/(2^k-1)})$ queries with a bounded error. This improves the previous $O(n^{k/(k+1)})$-query algorithm by Ambainis. The construction uses a modified learning graph approach. Compared to the recent paper by Belovs and Lee arXiv:1108.3022, the algorithm doesn't require any prior information on the input, and the complexity analysis is much simpler. Additionally, we introduce an $O(\sqrt{n}α^{1/6})$ algorithm for the graph collision problem where $α$ is the independence number of the graph.

arXiv:1205.1534May 7, 201228 citations

Assessing the feasibility of quantum learning algorithms for noisy linear problems

Minkyu Kim, Panjin Kim

Quantum algorithms for solving noisy linear problems are reexamined, under the same assumptions taken from the existing literature. The findings of this work include on the one hand extended applicability of the quantum Fourier transform to the ring learning with errors problem which has been left open by Grilo et al., who first devised a polynomial-time quantum algorithm for solving noisy linear problems with quantum samples. On the other hand, this paper also shows there exist efficient classical algorithms for short integer solution and size-reduced learning with errors problems if the quantum samples used by the previous studies are given.Quantum algorithms for solving noisy linear problems are reexamined, under the same assumptions taken from the existing literature. The findings of this work include on the one hand extended applicability of the quantum Fourier transform to the ring learning with errors problem which has been left open by Grilo et al., who first devised a polynomial-time quantum algorithm for solving noisy linear problems with quantum samples. On the other hand, this paper also shows there exist efficient classical algorithms for short integer solution and size-reduced learning with errors problems if the quantum samples used by the previous studies are given.

arXiv:2404.03932Scientific ReportsNov 25, 20240 citations

Quantum Error Correction and Detection for Quantum Machine Learning

Eromanga Adermann, Haiyue Kang, Martin Sevior +1 more

Quantum science and technologyJan 1, 20260 citations

γ_2

-norm semidefinite program, which characterizes quantum query complexity. Our composition theorem is quite general and allows us to compose quantum algorithms with input-dependent query complexities without incurring a logarithmic overhead for error reduction. As an application of the composition theorem, we remove all log factors from the best known quantum algorithm for Boolean matrix multiplication.

We present a quantum algorithm solving the

k

-distinctness problem in

O(n^{1-2^{k-2}/(2^k-1)})

queries with a bounded error. This improves the previous

O(n^{k/(k+1)})

-query algorithm by Ambainis. The construction uses a modified learning graph approach. Compared to the recent paper by Belovs and Lee arXiv:1108.3022, the algorithm doesn't require any prior information on the input, and the complexity analysis is much simpler. Additionally, we introduce an

O(\sqrt{n}α^{1/6})

algorithm for the graph collision problem where

α

is the independence number of the graph.