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
- Efficient Implementation of a Quantum Search Algorithm for Arbitrary N [0.0]
This paper presents an enhancement to Grover's search algorithm for instances where $N$ is not a power of 2.
By employing an efficient algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, we demonstrate that a considerable reduction in the number of oracle calls (and Grover's iterations) can be achieved in many cases.
arXiv Detail & Related papers (2024-06-19T19:16:40Z) - Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling [33.04597339860113]
We study a job shop scheduling problem for an automatized robot and a travelling salesperson problem.
In DCQO, we find the solution of an optimization problem via an adiabatic quantum dynamics.
We experimentally implement our algorithms on superconducting and trapped-ion quantum processors.
arXiv Detail & Related papers (2024-05-24T16:53:30Z) - 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) - Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
We provide efficient algorithms for the problem of learning large-margin halfspaces.
Our results improve upon the algorithms provided by Impagliazzo, Lei, Pitassi, and Sorrell [STOC 2022]
arXiv Detail & Related papers (2024-02-21T15:06:51Z) - 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) - A single $T$-gate makes distribution learning hard [56.045224655472865]
This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits.
We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
arXiv Detail & Related papers (2022-07-07T08:04:15Z) - 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)
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.