Conserved Quantities in Linear and Nonlinear Quantum Search

• URL: http://arxiv.org/abs/2503.06423v1
• Date: Sun, 09 Mar 2025 03:38:11 GMT
• Title: Conserved Quantities in Linear and Nonlinear Quantum Search
• Authors: David A. Meyer, Thomas G. Wong,
• Abstract summary: We bridge the fields of quantum computing algorithms, conservation laws, and many-body quantum systems by examining three algorithms.<n>The first algorithm uses a linear quantum walk, and we apply elementary calculus to show that the success probability of the algorithm reaches 1.<n>The second algorithm uses a nonlinear quantum walk with effective Hamiltonian $H(t) = lambda|psi|2$, which arises in the Gross-Pitaevskii equation describing Bose-Einstein condensates.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this tutorial, which contains some original results, we bridge the fields of quantum computing algorithms, conservation laws, and many-body quantum systems by examining three algorithms for searching an unordered database of size $N$ using a continuous-time quantum walk, which is the quantum analogue of a continuous-time random walk. The first algorithm uses a linear quantum walk, and we apply elementary calculus to show that the success probability of the algorithm reaches 1 when the jumping rate of the walk takes some critical value. We show that the expected value of its Hamiltonian $H_0$ is conserved. The second algorithm uses a nonlinear quantum walk with effective Hamiltonian $H(t) = H_0 + \lambda|\psi|^2$, which arises in the Gross-Pitaevskii equation describing Bose-Einstein condensates. When the interactions between the bosons are repulsive, $\lambda > 0$, and there exists a range of fixed jumping rates such that the success probability reaches 1 with the same asymptotic runtime of the linear algorithm, but with a larger multiplicative constant. Rather than the effective Hamiltonian, we show that the expected value of $H_0 + \frac{1}{2} \lambda|\psi|^2$ is conserved. The third algorithm utilizes attractive interactions, corresponding to $\lambda < 0$. In this case there is a time-varying critical function for the jumping rate $\gamma_c(t)$ that causes the success probability to reach 1 more quickly than in the other two algorithms, and we show that the expected value of $H(t)/[\gamma_c(t) N]$ is conserved.

Related papers

• Quantum Approximate $k$-Minimum Finding [2.810947654192424]
  We propose an optimal quantum $k$-minimum finding algorithm that works with approximate values for all $k geq 1$.<n>We present efficient quantum algorithms for identifying the $k$ smallest expectation values among multiple observables and for determining the $k$ lowest ground state energies of a Hamiltonian.
  arXiv  Detail & Related papers  (2024-12-21T11:21:15Z)
• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma.<n>This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles.<n>We show how to lift classical slow mixing results in the presence of a transverse field using Poisson Feynman-Kac techniques.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• 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)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions. We develop an algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees.
  arXiv  Detail & Related papers  (2023-09-19T22:53:17Z)
• Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem [0.0]
  This work revisits quantum algorithms for the well-known welded tree problem. It proposes a very succinct quantum algorithm based on the simplest coined quantum walks.
  arXiv  Detail & Related papers  (2023-04-17T16:03:50Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Improvement of quantum walk-based search algorithms in single marked vertex graphs [0.0]
  Amplitude amplification is usually used to amplify success probability, but the souffl'e problems follow. In this work, we define generalized interpolated quantum walks, which can both improve the success probability of search algorithms and avoid the souffl'e problems.
  arXiv  Detail & Related papers  (2022-09-09T07:43:46Z)
• Quantum Approximate Counting for Markov Chains and Application to Collision Counting [0.0]
  We show how to generalize the quantum approximate counting technique developed by Brassard, Hoyer and Tapp [ICALP 1998] to estimating the number of marked states of a Markov chain. This makes it possible to construct quantum approximate counting algorithms from quantum search algorithms based on the powerful "quantum walk based search" framework established by Magniez, Nayak, Roland and Santha.
  arXiv  Detail & Related papers  (2022-04-06T03:04:42Z)
• Estimating Gibbs partition function with quantumClifford sampling [6.656454497798153]
  We develop a hybrid quantum-classical algorithm to estimate the partition function. Our algorithm requires only a shallow $mathcalO(1)$-depth quantum circuit. Shallow-depth quantum circuits are considered vitally important for currently available NISQ (Noisy Intermediate-Scale Quantum) devices.
  arXiv  Detail & Related papers  (2021-09-22T02:03:35Z)
• Quantum Algorithm for Fidelity Estimation [8.270684567157987]
  For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem. We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
  arXiv  Detail & Related papers  (2021-03-16T13:57:01Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Emulating Quantum Interference with Generalized Ising Machines [0.0]
  This paper presents an exact and general procedure for mapping any sequence of quantum gates onto a network of probabilistic p-bits. We can view this structure as a Boltzmann machine whose states each represent a Feynman path leading from an initial configuration of qubits to a final configuration. Our results for mapping an arbitrary quantum circuit to a Boltzmann machine with a complex energy function should help push the boundaries of the simulability of quantum circuits with probabilistic resources.
  arXiv  Detail & Related papers  (2020-07-14T22:10:29Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.