Distributed Grover's algorithm

DOI10.1016/J.TCS.2024.114461arXiv2204.10487OpenAlexW4392125446MaRDI QIDQ6196832FDOQ6196832

Authors: Daowen Qiu, Le Luo, Ligang Xiao 

Publication date: 15 March 2024

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

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).

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)

Cites Work

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

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)