Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLackadaisical quantum walk in the hypercube to search for multiple marked vertices
60
0
0.0
(
0
)
Added by
Luciano Serafim de Souza
Publication date
2021
fields
Physics
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Adding self-loops at each vertex of a graph improves the performance of quantum walks algorithms over loopless algorithms. Many works approach quantum walks to search for a single marked vertex. In this article, we experimentally address several problems related to quantum walk in the hypercube with self-loops to search for multiple marked vertices. We first investigate the quantum walk in the loopless hypercube. We saw that neighbor vertices are also amplified and that approximately $1/2$ of the system energy is concentrated in them. We show that the optimal value of $l$ for a single marked vertex is not optimal for multiple marked vertices. We define a new value of $l = (n/N)cdot k$ to search multiple marked vertices. Next, we use this new value of $l$ found to analyze the search for multiple marked vertices non-adjacent and show that the probability of success is close to $1$. We also use the new value of $l$ found to analyze the search for several marked vertices that are adjacent and show that the probability of success is directly proportional to the density of marked vertices in the neighborhood. We also show that, in the case where neighbors are marked, if there is at least one non-adjacent marked vertex, the probability of success increases to close to $1$. The results found show that the self-loop value for the quantum walk in the hypercube to search for several marked vertices is $l = (n / N) cdot k $.
rate research
Read More
Quantum computing holds the promise of improving the information processing power to levels unreachable by classical computation. Quantum walks are heading the development of quantum algorithms for searching information on graphs more efficiently than their classical counterparts. A quantum-walk-based algorithm that is standing out in the literature is the lackadaisical quantum walk. The lackadaisical quantum walk is an algorithm developed to search two-dimensional grids whose vertices have a self-loop of weight $l$. In this paper, we address several issues related to the application of the lackadaisical quantum walk to successfully search for multiple solutions on grids. Firstly, we show that only one of the two stopping conditions found in the literature is suitable for simulations. We also demonstrate that the final success probability depends on the space density of solutions and the relative distance between solutions. Furthermore, this work generalizes the lackadaisical quantum walk to search for multiple solutions on grids of arbitrary dimensions. In addition, we propose an optimal adjustment of the self-loop weight $l$ for such scenarios of arbitrary dimensions. It turns out the other fits of $l$ found in the literature are particular cases. Finally, we observe a two-to-one relation between the steps of the lackadaisical quantum walk and the ones of Grovers algorithm, which requires modifications in the stopping condition. In conclusion, this work deals with practical issues one should consider when applying the lackadaisical quantum walk, besides expanding the technique to a wider range of search problems.
We give a quantum algorithm for finding a marked element on the grid when there are multiple marked elements. Our algorithm uses quadratically fewer steps than a random walk on the grid, ignoring logarithmic factors. This is the first known quantum walk that finds a marked element in a number of steps less than the square-root of the extended hitting time. We also give a new tighter upper bound on the extended hitting time of a marked subset, expressed in terms of the hitting times of its members.
The n-dimensional hypercube quantum random walk (QRW) is a particularily appealing example of a quantum walk because it has a natural implementation on a register on $n$ qubits. However, any real implementation will encounter decoherence effects due to interactions with uncontrollable degrees of freedom. We present a complete characterization of the mixing properties of the hypercube QRW under a physically relevant Markovian decoherence model. In the local decoherence model considered the non-unitary dynamics are modeled as a sum of projections on individual qubits to an arbitrary direction on the Bloch sphere. We prove that there is always classical (asymptotic) mixing in this model and specify the conditions under which instantaneous mixing textit{always} exists. And we show that the latter mixing property, as well as the classical mixing time, depend heavily on the exact environmental interaction and its strength. Therefore, algorithmic applications of the QRW on the hypercube, if they intend to employ mixing properties, need to consider both the walk dynamics and the precise decoherence model.
We introduce quantum hypercube states, a class of continuous-variable quantum states that are generated as orthographic projections of hypercubes onto the quadrature phase-space of a bosonic mode. In addition to their interesting geometry, hypercube states display phase-space features much smaller than Plancks constant, and a large volume of Wigner-negativity. We theoretically show that these features make hypercube states sensitive to displacements at extremely small scales in a way that is surprisingly robust to initial thermal occupation and to small separation of the superposed state-components. In a high-temperature proof-of-principle optomechanics experiment we observe, and match to theory, the signature outer-edge vertex structure of hypercube states.
We study the quantum walk search algorithm of Shenvi, Kempe and Whaley [PRA 67 052307 (2003)] on data structures of one to two spatial dimensions, on which the algorithm is thought to be less efficient than in three or more spatial dimensions. Our aim is to understand why the quantum algorithm is dimension dependent whereas the best classical algorithm is not, and to show in more detail how the efficiency of the quantum algorithm varies with spatial dimension or accessibility of the data. Our numerical results agree with the expected scaling in 2D of $O(sqrt{N log N})$, and show how the prefactors display significant dependence on both the degree and symmetry of the graph. Specifically, we see, as expected, the prefactor of the time complexity dropping as the degree (connectivity) of the structure is increased.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
