Distributed exact quantum algorithms for Bernstein-Vazirani and search problems

• URL: http://arxiv.org/abs/2303.10670v1
• Date: Sun, 19 Mar 2023 14:18:49 GMT
• Title: Distributed exact quantum algorithms for Bernstein-Vazirani and search problems
• Authors: Xu Zhou, Daowen Qiu, Le Lou
• Abstract summary: We give a distributed Bernstein-Vazirani algorithm (DBVA) with $t$ computing nodes, and a distributed exact Grover's algorithm (DEGA) that solve the search problem with only one target item in the unordered databases. We provide situations of our DBVA and DEGA on MindQuantum (a quantum software) to validate the correctness and practicability of our methods.
• Score: 9.146620606615889
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Distributed quantum computation has gained extensive attention since small-qubit quantum computers seem to be built more practically in the noisy intermediate-scale quantum (NISQ) era. In this paper, we give a distributed Bernstein-Vazirani algorithm (DBVA) with $t$ computing nodes, and a distributed exact Grover's algorithm (DEGA) that solve the search problem with only one target item in the unordered databases. Though the designing techniques are simple in the light of BV algorithm, Grover's algorithm, the improved Grover's algorithm by Long, and the distributed Grover's algorithm by Qiu et al, in comparison to BV algorithm, the circuit depth of DBVA is not greater than $2^{\text{max}(n_0, n_1, \cdots, n_{t-1})}+3$ instead of $2^{n}+3$, and the circuit depth of DEGA is $8(n~\text{mod}~2)+9$, which is less than the circuit depth of Grover's algorithm, $1 + 8\left\lfloor \frac{\pi}{4}\sqrt{2^n} \right\rfloor$. In particular, we provide situations of our DBVA and DEGA on MindQuantum (a quantum software) to validate the correctness and practicability of our methods. By simulating the algorithms running in the depolarized channel, it further illustrates that distributed quantum algorithm has superiority of resisting noise.

Related papers

• On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
  lattice-based cryptography is one of the main candidates of post-quantum cryptography. cryptographic security against quantum attackers is based on lattice problems like the shortest vector problem (SVP) Asymptotic quantum speedups for solving SVP are known and rely on Grover's search.
  arXiv  Detail & Related papers  (2024-10-17T16:54:41Z)
• Distributed Exact Generalized Grover's Algorithm [9.675088142486729]
  We propose a distributed Exactized Grover's Algorithm (DEGGA) to solve a generalized search problem. Our algorithm ensures accuracy, with a theoretical probability of identifying the target states at $100%$. Our method requires a total of $n$ qubits, eliminating the need for auxiliary qubits.
  arXiv  Detail & Related papers  (2024-05-11T09:17:11Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• A Bi-directional Quantum Search Algorithm [30.62704006898929]
  This paper combines Partial Grover's search algorithm and Bi-directional Search to create a fast Grover's quantum search algorithm. We incorporated a bi-directional search tactic with a partial Grover search, starting from an initial state and a single marked state in parallel. The proposed BDGS algorithm is benchmarked against the state-of-the-art Depth-First Grover's Search (DFGS) and generic Grover's Search (GS) implementations for $2$ to $20$ qubits.
  arXiv  Detail & Related papers  (2024-04-24T03:11:10Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Quantum Advantage of Noisy Grover's Algorithm [3.803244458097104]
  Grover's search algorithm is the only quantum algorithm with proven advantage to any possible classical search algorithm. We present a noise-tolerant method that exponentially improves the noise threshold of Grover's algorithm.
  arXiv  Detail & Related papers  (2023-06-19T11:17:32Z)
• Distributed Quantum-classical Hybrid Shor's Algorithm [1.7396274240172125]
  Shor's algorithm is considered as one of the most significant quantum algorithms of the Noisy Intermediate Quantum era. To reduce the resources required for Shor's algorithm, we propose a new distributed quantum-classical hybrid order-finding algorithm.
  arXiv  Detail & Related papers  (2023-04-24T13:52:05Z)
• Opening the Black Box Inside Grover's Algorithm [0.0]
  Grover's algorithm is a primary algorithm offered as evidence that quantum computers can provide an advantage over classical computers. We construct a quantum-inspired algorithm, executable on a classical computer, that performs Grover's task in a linear number of calls to (simulations of) the oracle.
  arXiv  Detail & Related papers  (2023-03-20T17:56:20Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Lattice sieving via quantum random walks [0.0]
  lattice-based cryptography is one of the leading proposals for post-quantum cryptography. Shortest Vector Problem (SVP) is arguably the most important problem for the cryptanalysis of lattice-based cryptography. We present an algorithm that has a (heuristic) running time of $20.2570 d + o(d)$ where $d$ is the lattice dimension.
  arXiv  Detail & Related papers  (2021-05-12T11:59:30Z)
• Simulation of Quantum Computing on Classical Supercomputers [23.350853237013578]
  We propose a scheme based on cutting edges of undirected graphs. This scheme cuts edges of undirected graphs with large tree width to obtain many undirected subgraphs. It can simulate 120-qubit 3-regular QAOA algorithm on 4096-core supercomputer.
  arXiv  Detail & Related papers  (2020-10-28T13:26:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.