Distributed Grover's algorithm

DOI10.1016/J.TCS.2024.114461MaRDI QIDQ6196832zbMATH OpenOpenAlexFDO

Authors Daowen Qiu, Le Luo, Ligang Xiao

Publication date 15 March 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.10487

zbMATH Keywords

Grover's algorithmquantum countingquantum amplitude estimationdistributed quantum computing

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Let Boolean function $f:{0,1}^{n}longrightarrow0,1$ where $|xin{0,1}^n|f(x)=1|=ageq1$. To search for an $xin{0,1}^n$ with $f(x)=1$, by Grover's algorithm we can get the objective with query times $lfloorfracpi4sqrtfrac{2}^{n}afloor$. 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>kgeq1$, we can decompose $f$ into $2^k$ 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 $su{m}_{i=1}^{r_i}lfloorfracpi4sqrtfrac{2}^{n-k}{b}_{i}floor+lceilsqrt{2}^{n-k}ceil+2t_a+1$ for some $1leq{b}_{i}leqa$ and $r_{i}leq2t_a+1$, where $t_a=lceil2pisqrta+11ceil$. In particular, if $a=1$, then our distributed Grover's algorithm only needs $lfloorfracpi4sqrt{2}^{n-k}floor$ queries, versus $lfloorfracpi4sqrt{2}^{n}floor$ 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).

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 5076264 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• Application of distributed semi-quantum computing model in phase estimation
• Efficient distributed quantum computing
• Optimal separation in exact query complexities for Simon's problem
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Complexity Theory
• Quantum algorithms revisited
• Quantum computational networks
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Rapid solution of problems by quantum computation
• Revisiting Deutsch-Jozsa algorithm
• Revisiting the simulation of quantum Turing machines by quantum circuits
• Strengths and Weaknesses of Quantum Computing
• The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines

Cited in

(2)

• Breaking permutation-based pseudorandom cryptographic schemes using distributed exact quantum algorithms
• Exact distributed quantum algorithm for generalized Simon's problem

This page was built for publication: Distributed Grover's algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6196832)