Fetching the paper…

Reading the bibliography…

Improved quantum test for linearity of a Boolean function · Around

2013

Improved quantum test for linearity of a Boolean function

Chakraborty, Kaushik, Maitra, Subhamoy

Original
PDF
Post on X

Understand

Let a Boolean function be available as a black-box (oracle) and one likes to devise an algorithm to test whether it has certain property or it is $\epsilon$-far from having that property.

The efficiency of the algorithm is judged by the number of calls to the oracle so that one can decide, with high probability, between these two alternatives.
The best known quantum algorithm for testing whether a function is linear or $\epsilon$-far $(0 < \epsilon < \frac{1}{2})$ from linear functions requires $O(\epsilon^{-\frac{2}{3}})$ many calls [Hillery and Andersson, Physical Review A 84, 062329 (2011)].
We show that this can be improved to $O(\epsilon^{-\frac{1}{2}})$ by using the Deutsch-Jozsa and the Grover Algorithms.

Built on

D. Deutsch and R. Jozsa, Proceedings of Royal Society of London A, 439, 553–558 (1992)
1992
Earlier work this paper cites.
E. Bernstein and U. Vazirani, Proceedings of the 25th Annual ACM Symposium on Theory of Computing, (ACM Press, New York, 1993), pp. 11–20
1993
Earlier work this paper cites.
M. Blum, M. Luby and R. Rubinfeld, J. Comput. Syst. Sci. 47(3), 549 (1993)
1993
Earlier work this paper cites.
M. Bellare, D. Coppersmith, J. Hastad, M. Kiwi and M. Sudan, IEEE Trans. Inform. Theory, 42, 1781 (1996)
1996
Earlier work this paper cites.

Similar

L. K. Grover, Phys. Rev. Lett. 79, 325 (1997)
1997
Cited alongside, same era.
M. Boyer, G. Brassard, P. Hoeyer and A. Tapp, Fortsch. Phys. 46: 493–506 (1998)
1998
Cited alongside, same era.
S. Maitra and P. Mukhopadhyay, International Journal on Quantum Information, 3(2), 359 (2005)
Original
2005
Cited alongside, same era.
S. Kavut, S. Maitra and M. D. Yucel, IEEE Trans. Inform. Theory, 53(5), 1743 (2007)
2007
Cited alongside, same era.

Then

T. Kaufman, S. Litsyn and N. Xie, Siam J. Comput., 39(5), 1988 (2010)
2010
Later among the works it cites.
A. Ambainis, A. M. Childs, Y. -K. Liu, Proceedings of RANDOM 2011, Lecture Notes in Computer Science 6845, pp. 365-376, arXiv:1012.3174 [quant-ph]
Original
2011
Later among the works it cites.
M. Hillery and E. Andersson, Physical Review A 84, 062329 (2011)
2011
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…