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

Quantum Algorithms Are Determining the Property of a Certain Function

Koji Nagata, Tadao Nakamura, Han J.F. Geurdes, Ahmed Farouk, Josep Amengual i Batle, S. Abdalla

Published Mar 1, 2017• 0 citations
OpenAlex

Abstract

We discuss a character of quantum algorithms. In fact, all of them determine the property of a certain function. The function under study must have the property $f(x) = f(-x)$ when $f(x)\neq 0$.

Related papers

Quantum tests for the linearity and permutation invariance of Boolean functions

Mark S. Hillery, Erika Andersson

The goal in function property testing is to determine whether a black-box Boolean function has a certain property or is $\ensuremath{\epsilon}$-far from having that property. The performance of the algorithm is judged by how many calls need to be made to the black box in order to determine, with high probability, which of the two alternatives is the case. Here we present two quantum algorithms, the first to determine whether the function is linear and the second to determine whether it is symmetric (invariant under permutations of the arguments). Both require order ${\ensuremath{\epsilon}}^{\ensuremath{-}2/3}$ calls to the oracle, which is better than known classical algorithms. In addition, in the case of linearity testing, if the function is linear, the quantum algorithm identifies which linear function it is. The linearity test combines the Bernstein-Vazirani algorithm and amplitude amplification, while the test to determine whether a function is symmetric uses projective measurements and amplitude amplification.

arXiv:1106.4831•Physical Review A•Dec 28, 2011•19 citations

Quantum algorithms

Bilha Segev

I review a few of the most famous quantum algorithms, and discuss them from a practical perspective. What should a quantum system be able to do, in principle, to qualify as a quantum computer for which these algorithms work? The role of superposition, parallelism, and entanglement is discussed.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Jul 31, 2002•0 citations

Standard quantum algorithms and the property of a certain function

Koji Nagata, Tadao Nakamura

\n\tWe discuss a new mathematical structure for standard quantum algorithms. It says a certain property in case of a special function f that the relation f(x)=f(-x) holds. That is, the particular mathematical structure of the special function is that f(x) should be even if we assume -x=-x.

Physics & Astronomy International Journal•Jan 1, 2018•0 citations

Recent progress in quantum algorithms

Dave Bacon, Wim van Dam

What quantum algorithms outperform classical computation and how do they do it?

Communications of the ACM•Jan 26, 2010•95 citations

EXTRACTION OF VALUE OF FUNCTION f(x) IN DEUTSCH ALGORITHM AND DEUTSCH–JOZSA ALGORITHM

Li Fei Deng, Ai-Xi Chen, Xu Yan-Qiu +1 more

Deutsch algorithm or Deutsch–Jozsa algorithm only needs one query to determine whether the function f(x) is constant or balanced. That is, the global property of the function f(x) is rapidly known. But these algorithms do not give the concrete value of function f(x). For the f(x), its value is also of interest. Here we propose a scheme in which the value of function f(x) can be determined. We use an entangled state as the input state and send it into quantum black box. Through performing measurement on the output state, we can exactly determine the value of f(x). Its value plus its global property enables us to thoroughly understand elementary information of f(x). Based on these informations, we can determine unitary transformations on the input state walking through quantum black box. The quantum black box becomes quantum white box to a certain extent.

International Journal of Quantum Information•Apr 1, 2009•0 citations

Quantum Algorithms

Seyed Massoud Amini

We give a short overview of quantum algorithms. Some famous algorithms such as Deutsch-Jozsa and Simon are covered with more details. The directions for further development are addressed,

•Jun 1, 2009•0 citations
We discuss a character of quantum algorithms. In fact, all of them determine the property of a certain function. The function under study must have the property f(x)=f(−x)f(x) = f(-x)f(x)=f(−x) when f(x)≠0f(x)\neq 0f(x)=0.
The goal in function property testing is to determine whether a black-box Boolean function has a certain property or is $\ensuremath{\epsilon}$-far from having that property. The performance of the algorithm is judged by how many calls need to be made to the black box in order to determine, with high probability, which of the two alternatives is the case. Here we present two quantum algorithms, the first to determine whether the function is linear and the second to determine whether it is symmetric (invariant under permutations of the arguments). Both require order ${\ensuremath{\epsilon}}^{\ensuremath{-}2/3}$ calls to the oracle, which is better than known classical algorithms. In addition, in the case of linearity testing, if the function is linear, the quantum algorithm identifies which linear function it is. The linearity test combines the Bernstein-Vazirani algorithm and amplitude amplification, while the test to determine whether a function is symmetric uses projective measurements and amplitude amplification.
Deutsch algorithm or Deutsch–Jozsa algorithm only needs one query to determine whether the function f(x) is constant or balanced. That is, the global property of the function f(x) is rapidly known. But these algorithms do not give the concrete value of function f(x). For the f(x), its value is also of interest. Here we propose a scheme in which the value of function f(x) can be determined. We use an entangled state as the input state and send it into quantum black box. Through performing measurement on the output state, we can exactly determine the value of f(x). Its value plus its global property enables us to thoroughly understand elementary information of f(x). Based on these informations, we can determine unitary transformations on the input state walking through quantum black box. The quantum black box becomes quantum white box to a certain extent.