Search for Multiple Adjacent Marked Vertices on the Hypercube by a Quantum Walk with Partial Phase Inversion

• URL: http://arxiv.org/abs/2305.19614v2
• Date: Sat, 11 May 2024 23:32:56 GMT
• Title: Search for Multiple Adjacent Marked Vertices on the Hypercube by a Quantum Walk with Partial Phase Inversion
• Authors: Luciano S. de Souza, Jonathan H. A. de Carvalho, Henrique C. T. Santos, Tiago A. E. Ferreira,
• Abstract summary: We show that a quantum walk can amplify the probability amplitudes of the target states, reaching success probabilities of values close to $1$. Our results demonstrate that the partial phase inversion of target states is a promising alternative to search adjacent solutions with quantum walks.
• Score: 3.8436076642278754
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: There is a strong interest in quantum search algorithms, particularly in problems with multiple adjacent solutions. In the hypercube, part of the energy of the quantum system is retained in states adjacent to the target states, decreasing the chances of the target states being observed. This paper applies the Multiself-loop Lackadaisical Quantum Walk with Partial Phase Inversion to search for multiple adjacent marked vertices on the hypercube. Aspects like the type of marked vertices are considered in addition to using multiple self-loops and weight compositions. Two scenarios are analyzed. Firstly, the relative position of non-adjacent marked vertices together with adjacent marked vertices. Secondly, only adjacent marked vertices are analyzed. Here, we show experimentally that, with partial phase inversion, a quantum walk can amplify the probability amplitudes of the target states, reaching success probabilities of values close to $1$. We also show that the relative position of non-adjacent marked vertices does not significantly influence the search results. Our results demonstrate that the partial phase inversion of target states is a promising alternative to search adjacent solutions with quantum walks, which is a key capacity for real search applications.

Related papers

• Quantum-Centric Algorithm for Sample-Based Krylov Diagonalization [0.6512657417859998]
  We introduce a quantum diagonalization algorithm which combines two key ideas on quantum subspaces. We prove that our algorithm converges under working assumptions of Krylov quantum diagonalization and sparseness of ground state. We then show numerical investigations of lattice Hamiltonians, which indicate that our method can outperform existing Krylov quantum diagonalization in presence of shot noise.
  arXiv  Detail & Related papers  (2025-01-16T17:56:19Z)
• Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices [7.922488341886121]
  This paper examines the quantum walk search algorithm on complete multipartite graphs. We employ the coined quantum walk model and achieve quadratic speedup. We also provide the numerical simulation and circuit implementation of our quantum algorithm.
  arXiv  Detail & Related papers  (2024-10-07T11:13:41Z)
• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  In this paper, we give a short proof of the optimal linear hitting time for a welded tree problem by a discrete-time quantum walk. The same technique can be applied to other 1-dimensional hierarchical graphs.
  arXiv  Detail & Related papers  (2024-04-30T11:45:49Z)
• Multi-self-loop Lackadaisical Quantum Walk with Partial Phase Inversion [3.8436076642278754]
  This article proposes the quantum search algorithm Multi-self-loop Lackadaisical Quantum Walk with Partial Phase Inversion. The proposed algorithm is based on Grover's algorithm and acts partially, modifying the phase of a given quantity $s m$ of self-loops. It improves the maximum success probabilities to values close to $1$ in $O (sqrt(n+m)cdot N)$, where $n$ is the hypercube degree.
  arXiv  Detail & Related papers  (2023-05-01T23:18:22Z)
• 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)
• Variational Approach to Quantum State Tomography based on Maximal Entropy Formalism [3.6344381605841187]
  We employ the maximal entropy formalism to construct the least biased mixed quantum state that is consistent with the given set of expectation values. We employ a parameterized quantum circuit and a hybrid quantum-classical variational algorithm to obtain such a target state making our recipe easily implementable on a near-term quantum device.
  arXiv  Detail & Related papers  (2022-06-06T01:16:22Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Stochastic emulation of quantum algorithms [0.0]
  We introduce higher-order partial derivatives of a probability distribution of particle positions as a new object that shares basic properties of quantum mechanical states needed for a quantum algorithm. We prove that the propagation via the map built from those universal maps reproduces up to a prefactor exactly the evolution of the quantum mechanical state. We implement several well-known quantum algorithms, analyse the scaling of the needed number of realizations with the number of qubits, and highlight the role of destructive interference for the cost of emulation.
  arXiv  Detail & Related papers  (2021-09-16T07:54:31Z)
• 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)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)

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.