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

• URL: http://arxiv.org/abs/2305.19614v3
• Date: Mon, 18 Nov 2024 12:38:52 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 analyze the application of the Multi-self-loop Lackadaisical Quantum Walk on the hypercube. We show that with the use of partial phase inversion, it is possible to amplify their probability amplitudes to values close to 1.
• Score: 3.8436076642278754
• License:
• Abstract: In this paper, we analyze the application of the Multi-self-loop Lackadaisical Quantum Walk on the hypercube that uses partial phase inversion to search for multiple adjacent marked vertices. We evaluate the influence of the relative position of non-adjacent marked vertices. The use of self-loops and the composition of their weights are an essential part of the construction process of new quantum search algorithms based on lackadaisical quantum walks, however, other aspects have been considered, such as, for example, the type of marked vertices. Part of the energy of a quantum system is retained in states adjacent to the target state. This behavior causes the probability amplitudes of these states to be amplified to values equivalent to those of the target state, reducing their chances of being observed. Here we show experimentally that with the use of partial phase inversion, it is possible to amplify their probability amplitudes to values close to 1 even in scenarios with adjacent marked vertices. We also show that the relative position of the non-adjacent marked vertices did not significantly influence the results. The lackadaisical quantum walk generalization to only a single self-loop and the ideal composition of a weight value was sufficient to obtain advances to quantum search algorithms based on quantum walks. However, the results show that many other aspects need to be taken into account for the construction of new quantum algorithms. It was possible to add gains in the maximum probabilities of success compared to other results found in the literature. In one of the most significant cases, the probability of success increased from $p \approx 0.38$ to $p > 0.99$. Therefore, the use of partial phase inversion brings new contributions to the development of new quantum search algorithms based on quantum walks and the use of multiple self-loops.

Related papers

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