One-Shot and Concurrent Hitting Times for Grover-Coined Quantum Walks on Cubelike Graphs

• URL: http://arxiv.org/abs/2609.04503v1
• Date: Thu, 03 Sep 2026 21:44:45 GMT
• Title: One-Shot and Concurrent Hitting Times for Grover-Coined Quantum Walks on Cubelike Graphs
• Abstract summary: We study the one-shot and concurrent hitting for the discrete-time Grover-coined quantum walk on cubelike graphs.<n>Our results extend Kempe's hypercube hitting phenomenon.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the one-shot and concurrent hitting for the discrete-time Grover-coined quantum walk on cubelike graphs $G=\text{Cay}(\mathbb Z_2^d,Ω)$ of degree $Δ=|Ω|$. Starting from the vertex labeled $0$, we identify $σ=\bigoplus_{ω\inΩ}ω$ as a natural target vertex; for the hypercube, $σ$ is precisely the antipodal vertex. For families with $Δ\to\infty$, let $T$ be an integer having the same parity as $Δ$ and satisfying $ \left|T-\frac{πΔ}{2}\right|\leq 1. $ We show that the probability $p_T(σ)$ of finding the walker at $σ$ when it is measured at time $T$ satisfies $$ p_T(σ)=1-O(Δ^{-1/5}). $$ Thus the target is found with probability tending to one after $Θ(Δ)$ steps. For the concurrently measured walk, let $H_T^{\mathrm{Conc}}(σ)$ denote the probability that the target is detected at or before time $T$ when it is tested after every step. We prove $$ p_T(σ)\leq T H_T^{\mathrm{Conc}}(σ), $$ which implies $H_T^{\mathrm{Conc}}(σ)=Ω(Δ^{-1})$ over the same time scale. The proof uses the Walsh-Fourier decomposition, an exact two-dimensional reduction of each Fourier mode, and a universal second-moment identity for the associated character sums. Our results extend Kempe's hypercube hitting phenomenon (J. Kempe, Probab. Theory Relat. Fields 133, 215-235, 2005) to arbitrary cubelike generating sets and establish the conjectured asymptotic hitting behavior for cublelike and augmented cubes in Mulherkar, Rajdeepak and Sunitha (Int. J. Quantum Inf. 20,2250020, 2022)

Related papers

• An Optimal Analysis of the Product Test [42.29010058743949]
  Product testing decides whether a pure multipartite quantum state is fully unentangled across a specified tensor decomposition.<n>Despite being a fundamental property testing task and having many applications, the product test's exact (worst-case) acceptance probability curve has yet to be fully determined.<n>As a complexity-theoretic application, our results improve the one-shot soundness parameter in the Harrow-Montanaro reduction from $mathsfQMA(k)$ to $mathsfQMA(2)$.
  arXiv  Detail & Related papers  (2026-07-23T16:17:44Z)
• The Quantum Walk Characteristic Polynomial Distinguishes All Strongly Regular Graphs of Prime Orde [0.0]
  We prove that the emphquantum walk characteristic $_q(G,) coloneqq det(I - U_G)$, where $U_G$ is the coined quantum walk operator on $G$, completely determines $G$ up to isomorphism within the class of strongly regular graphs of the same order.<n>As a consequence, graph isomorphism is decidable in time within this class using the quantum spectrum without resorting to the general quasi-polynomial algorithm of Babai Babai.
  arXiv  Detail & Related papers  (2026-04-02T00:40:31Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• Tripartite information of free fermions: a universal entanglement coefficient from the sine kernel [51.56484100374058]
  We study the tripartite information I_3 of free fermions on two-dimensional lattices partitioned into three adjacent strips of width w.<n>We find that g(z) has a unique zero at z* = 1.329 +/- 0.001: modes with k_F w z* violate monogamy of mutual information.<n>Two exact cancellations -- of the z ln z area-law terms and of the z2 terms -- are intrinsic to the I_3 combination.
  arXiv  Detail & Related papers  (2026-03-03T15:39:35Z)
• Permanents of matrix ensembles: computation, distribution, and geometry [0.0]
  We use the GPU to greaatly accelerate the computation of permanents over $mathbbC,$ $mathbbR,$ $mathbbF_p$ and $mathbbQ.$<n>We study the permanent along geodesics on the unitary group.<n>For the geodesic from the identity to the $n$-cycle permutation matrix, we find a universal scaling function $f(t)=frac1nln|perm((t))|$ that is independent of$n$ in
  arXiv  Detail & Related papers  (2026-02-08T22:31:42Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• Convergence Rate for the Last Iterate of Stochastic Gradient Descent Schemes [0.0]
  We prove that SHB attains constant momentum with $F_*$ when Fdelta is convex.<n>We also prove that SHB attains constant momentum with $F_*$ when Fdelta is convex.
  arXiv  Detail & Related papers  (2025-07-09T20:59:23Z)
• Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem [0.0]
  We prove that to each synchronous non-local game $mathcalG=(I,O,lambda)$ with $|I|=n$ and $O=m geq 3$, there is an associated graph $G_lambda$.<n>We also prove that there exists an $alpha in (0,1)$ for which determining whether the non-commutative Max-$3$-Cut of a graph is $E|$ or less than $alpha |E|$ is RE-hard.
  arXiv  Detail & Related papers  (2024-12-27T02:05:37Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Quantum walks on blow-up graphs [0.0]
  A blow-up of $n$ copies of a graph $G$ is the graph $oversetnuplusG$. We investigate the existence of quantum state transfer on a blow-up graph $oversetnuplusG$.
  arXiv  Detail & Related papers  (2023-08-26T14:07:25Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  We introduce an observation-matrix-based framework for fully asynchronous online Federated Learning with adversaries. Our main result is that the proposed algorithm almost surely converges to the desired mean $mu.$ We derive this convergence using a novel differential-inclusion-based two-timescale analysis.
  arXiv  Detail & Related papers  (2023-04-04T04:32:29Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  We show how all properties of a quantum manifold of states are fully described by a gauge-invariant Bargmann. We show how our results have immediate applications to the modern theory of polarization.
  arXiv  Detail & Related papers  (2022-05-30T18:01:34Z)
• Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality [6.621324975749854]
  We show that the noise stability of a function $f:mathbbRn to -1, 1$ is the expected value of $f(boldsymbolx) cdot f(boldsymboly)$. We conjecture that the expected value of $langle f(boldsymbolx), f(boldsymboly)rangle$ is minimized by the function $f(x) = x_leq k / Vert x_leq k /
  arXiv  Detail & Related papers  (2021-11-01T20:45:42Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

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.