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

distributed quantum computingGrover's algorithmquantum amplitude estimationquantum counting

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

• Application of distributed semi-quantum computing model in phase estimation
• Efficient distributed quantum computing
• 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?)
• Optimal separation in exact query complexities for Simon's problem
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithms revisited
• Quantum Complexity Theory
• 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

(5)

• Exact distributed quantum algorithm for generalized Simon's problem
• Breaking permutation-based pseudorandom cryptographic schemes using distributed exact quantum algorithms
• Full-phase distributed quantum impossible differential cryptanalysis
• Distributed generalized Deutsch-Jozsa algorithm
• Full-phase distributed quantum differential cryptanalysis and its variants on block ciphers

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)