Related papers: Hypercube Quantum Search: Exact Computation of the Probability of Success in Polynomial Time

Hypercube Quantum Search: Exact Computation of the Probability of Success in Polynomial Time

URL: http://arxiv.org/abs/2202.12973v1
Date: Fri, 25 Feb 2022 21:05:38 GMT
Title: Hypercube Quantum Search: Exact Computation of the Probability of Success in Polynomial Time
Authors: Hugo Pillin, Gilles Burel, Paul Baird, El-Houssa\"in Baghious and Roland Gautier
Abstract summary: Grover's quantum search is one of the most significant quantum algorithms. In this paper, we propose an in-depth study of the quantum search over a hypercube layout.
Score: 0.1957338076370071
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In the emerging domain of quantum algorithms, the Grover's quantum search is certainly one of the most significant. It is relatively simple, performs a useful task and more importantly, does it in an optimal way. However, due to the success of quantum walks in the field, it is logical to study quantum search variants over several kind of walks. In this paper, we propose an in-depth study of the quantum search over a hypercube layout. First, through the analysis of elementary walk operators restricted to suitable eigenspaces, we show that the acting component of the search algorithm takes place in a small subspace of the Hilbert workspace that grows linearly with the problem size. Subsequently, we exploit this property to predict the exact evolution of the probability of success of the quantum search in polynomial time.

Related papers

Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
Currently available quantum devices have only a limited amount of qubits and a high level of noise, limiting the size of problems that can be solved accurately with those devices. We propose a novel method that can improve variational quantum algorithms -- discretized quantum exhaustive search''
arXiv Detail & Related papers (2024-07-24T22:06:05Z)
Sample-size-reduction of quantum states for the noisy linear problem [0.0]
We show that it is possible to reduce a quantum sample size in a quantum random access memory (QRAM) to the linearithmic order. We achieve a shorter run-time for the noisy linear problem.
arXiv Detail & Related papers (2023-01-08T05:53:17Z)
Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
We present an approach where the quantum computation is supplemented by a classical result. Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative. In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
arXiv Detail & Related papers (2022-09-12T15:47:44Z)
Quantum computational intelligence for traveltime seismic inversion [0.0]
We implement an approach for traveltime seismic inversion through a near-term quantum algorithm based on gradient-free quantum circuit learning. We demonstrate that a quantum computer with thousands of qubits, even if noisy, can solve geophysical problems.
arXiv Detail & Related papers (2022-08-11T12:36:58Z)
Designing exceptional-point-based graphs yielding topologically guaranteed quantum search [0.0]
We show how to construct walks with the property that all the eigenvalues of the non-Hermitian survival operator, coalesce to zero. The resulting search is guaranteed to succeed in a bounded time for any initial condition.
arXiv Detail & Related papers (2022-02-08T04:30:24Z)
Depth-efficient proofs of quantumness [77.34726150561087]
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
arXiv Detail & Related papers (2021-07-05T17:45:41Z)
On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z)
Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task. Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate. The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
arXiv Detail & Related papers (2021-06-06T13:15:25Z)
Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems. We propose an algorithm to implement imaginary time propagation on a quantum computer.
arXiv Detail & Related papers (2021-02-24T12:48:00Z)
Quantum walk processes in quantum devices [55.41644538483948]
We study how to represent quantum walk on a graph as a quantum circuit. Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
arXiv Detail & Related papers (2020-12-28T18:04:16Z)
Transition Probabilities in Generalized Quantum Search Hamiltonian Evolutions [0.0]
We study the computational aspects necessary to calculate the transition probability from a source state to a target state in a continuous time quantum search problem. We find it is possible to outperform, in terms of minimum search time, the well-known Farhi-Gutmann analog quantum search algorithm.
arXiv Detail & Related papers (2020-02-06T13:16:37Z)

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