caa a22 4500 445886803 CHVBK 20180317145602.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s11128-010-0187-9 doi (NATIONALLICENCE)springer-10.1007/s11128-010-0187-9 Quantum algorithm for the asymmetric weight decision problem and its generalization to multiple weights [Elektronische Daten] [Byung-Soo Choi, Samuel Braunstein] As one of the applications of Grover search, an exact quantum algorithm for the symmetric weight decision problem of a Boolean function has been proposed recently. Although the proposed method shows a quadratic speedup over the classical approach, it only applies to the symmetric case of a Boolean function whose weight is one of the pair {0<w 1<w 2<1, w 1+w 2=1}. In this article, we generalize this algorithm in two ways. Firstly, we propose a quantum algorithm for the more general asymmetric case where {0<w 1<w 2<1}. This algorithm is exact and computationally optimal. Secondly, we build on this to exactly solve the multiple weight decision problem for a Boolean function whose weight as one of {0<w 1<w 2<· · ·<w m<1}. This extended algorithm continues to show a quantum advantage over classical methods. Thirdly, we compare the proposed algorithm with the quantum counting method. For the case with two weights, the proposed algorithm shows slightly lower complexity. For the multiple weight case, the two approaches show different performance depending on the number of weights and the number of solutions. For smaller number of weights and larger number of solutions, the weight decision algorithm can show better performance than the quantum counting method. Finally, we discuss the relationship between the weight decision problem and the quantum state discrimination problem. Springer Science+Business Media, LLC, 2010 Quantum algorithm nationallicence Generalized weight decision problem nationallicence Query complexity nationallicence Choi Byung-Soo Department of Electronics Engineering, Ewha Womans University, Seoul, Republic of Korea (South Korea) aut Braunstein Samuel Department of Computer Science, University of York, YO10 5DD, York, United Kingdom aut Quantum Information Processing Springer US; http://www.springer-ny.com 10/2(2011-04-01), 177-188 1570-0755 10:2<177 2011 10 11128 https://doi.org/10.1007/s11128-010-0187-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11128-010-0187-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Choi Byung-Soo Department of Electronics Engineering, Ewha Womans University, Seoul, Republic of Korea (South Korea) aut NATIONALLICENCE 700 1- Braunstein Samuel Department of Computer Science, University of York, YO10 5DD, York, United Kingdom aut NATIONALLICENCE 773 0- Quantum Information Processing Springer US; http://www.springer-ny.com 10/2(2011-04-01), 177-188 1570-0755 10:2<177 2011 10 11128 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer