2022/04/22 by Daowen Qiu, Qiu, Daowen, Le Luo +2 · 7 citations
Computer Science · #Computability, Logic, AI Algorithms #Quantum Computing Algorithms and Architecture #Cryptography and Data Security
paper · pdf · doi:10.48550/arxiv.2204.10487
Let Boolean function f:\0,1\n\longrightarrow \0,1\ where |\x∈\0,1\n| f(x)=1\|=a≥ 1. To search for an x∈\0,1\n with f(x)=1, by Grover's algorithm we can get the objective with query times \lfloor \fracπ4√((2n)/(a)) \rfloor. In this paper, we propose a distributed Grover's algorithm for computing f with lower query times and smaller number of input bits. More exactly, for any k with n>k≥ 1, we can decompose f into 2k subfunctions, each which has n-k input bits, and then the objective can be found out by computing these subfunctions with query times at most ∑i=1ri \lfloor \fracπ4√\frac2n-kbi \rfloor+\lceil√2n-k\rceil+2ta+1 for some 1≤ bi≤ a and ri≤ 2ta+1, where ta=\lceil 2π√(a)+11\rceil. In particular, if a=1, then our distributed Grover's algorithm only needs \lfloor \fracπ4√2n-k \rfloor queries, versus \lfloor \fracπ4√2n \rfloor queries of Grover's algorithm. %When n qubits belong to middle scale but still are a bit difficult to be processed in practice, n-k qubits are likely feasible for appropriate k in physical realizability. Finally, we propose an efficient algorithm of constructing quantum circuits for realizing the oracle corresponding to any Boolean function with conjunctive normal form (CNF).