Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Institute of Physics eBooks

Efficient exact quantum algorithm for the parity problem of a function

Koji Nagata, Do Ngoc Diep, Ahmed Farouk, Tadao Nakamura

Published Jul 1, 2022• 0 citations
Publisher
DOI
10.1088/978-0-7503-4700-6ch16

Related papers

Efficient Quantum Algorithm for the Parity Problem of a Certain Function

Koji Nagata, Tadao Nakamura, Josep Amengual i Batle +1 more

International Journal of Theoretical Physics•Jul 16, 2018•2 citations

Quantum algorithms for learning graphs and beyond.

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 vertices contains any edges. In the second (parity queries), the oracle returns the parity of the number of edges in a subset. In the third model, we are given copies of the graph state corresponding to the graph. We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models, for some families of graphs, and give quantum algorithms in the graph state model whose complexity is similar to the parity query model. For some parameter regimes, the speedups can be exponential in the parity query model. On the other hand, without any promise on the graph, no speedup is possible in the OR query model. A main technique we use is the quantum algorithm for solving the combinatorial group testing problem, for which a query-efficient quantum algorithm was given by Belovs. Here we additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al. for a gapped version of the group testing problem. We also give simple time-efficient quantum algorithms based on Fourier sampling and amplitude amplification for learning the exact-half and majority functions, which almost match the optimal complexity of Belovs' algorithms.

•Nov 17, 2020•1 citation

Quantum algorithms for learning a hidden graph and beyond

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 vertices contains any edges. In the second ("parity queries"), the oracle returns the parity of the number of edges in a subset. In the third model, we are given copies of the graph state corresponding to the graph. We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models, for some families of graphs, and give quantum algorithms in the graph state model whose complexity is similar to the parity query model. For some parameter regimes, the speedups can be exponential in the parity query model. On the other hand, without any promise on the graph, no speedup is possible in the OR query model. A main technique we use is the quantum algorithm for solving the combinatorial group testing problem, for which a query-efficient quantum algorithm was given by Belovs. Here we additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al.\ for a "gapped" version of the group testing problem. We also give simple time-efficient quantum algorithms based on Fourier sampling and amplitude amplification for learning the exact-half and majority functions, which almost match the optimal complexity of Belovs' algorithms.

arXiv:2011.08611•Nov 17, 2020•1 citation

Progress in Quantum Algorithms

Peter W. Shor

Springer eBooks•Apr 2, 2007•2 citations

Progress in Quantum Algorithms

Peter W. Shor

Quantum Information Processing•Oct 1, 2004•61 citations

Quantum Query Algorithms for Automorphisms of Galois Groups

Agnis Škuškovniks, Freivalds Rusinš

In this paper we study quantum query complexity of exactly (with probability 1) deciding the parity of npermutations of numbers (from 0 to n-1).We show that for this non-Boolean problem use of quantum complexity techniques gives quite strong results as it does for other, but Boolean problems.We use Galois Theory to find new problems where quantum query algorithms are more efficient than deterministic ones.

Advances in intelligent systems research/Advances in Intelligent Systems Research•Jan 1, 2013•1 citation
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 vertices contains any edges. In the second (parity queries), the oracle returns the parity of the number of edges in a subset. In the third model, we are given copies of the graph state corresponding to the graph. We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models, for some families of graphs, and give quantum algorithms in the graph state model whose complexity is similar to the parity query model. For some parameter regimes, the speedups can be exponential in the parity query model. On the other hand, without any promise on the graph, no speedup is possible in the OR query model. A main technique we use is the quantum algorithm for solving the combinatorial group testing problem, for which a query-efficient quantum algorithm was given by Belovs. Here we additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al. for a gapped version of the group testing problem. We also give simple time-efficient quantum algorithms based on Fourier sampling and amplitude amplification for learning the exact-half and majority functions, which almost match the optimal complexity of Belovs' algorithms.
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 vertices contains any edges. In the second ("parity queries"), the oracle returns the parity of the number of edges in a subset. In the third model, we are given copies of the graph state corresponding to the graph. We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models, for some families of graphs, and give quantum algorithms in the graph state model whose complexity is similar to the parity query model. For some parameter regimes, the speedups can be exponential in the parity query model. On the other hand, without any promise on the graph, no speedup is possible in the OR query model. A main technique we use is the quantum algorithm for solving the combinatorial group testing problem, for which a query-efficient quantum algorithm was given by Belovs. Here we additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al.\ for a "gapped" version of the group testing problem. We also give simple time-efficient quantum algorithms based on Fourier sampling and amplitude amplification for learning the exact-half and majority functions, which almost match the optimal complexity of Belovs' algorithms.