Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0101142

A quantum computing scheme for the Hamiltonian path problem

G. Sampath

Published Jan 30, 2001• 0 citations
arXivHTMLPDF

Abstract

A quantum computing scheme that uses a single photon and multiple-slit gratings is suggested for the Hamiltonian path problem on a simple graph G of N vertices. The photon is input to an N-slit grating followed by an N x N matrix of `processing units'. A unit consists of a delay line followed by a grating with k slits (0 < k < N) whose outputs are directed to k units in the next row in a manner determined by the adjacency matrix of G. There is a one-to-one mapping between paths of length N-1 in the graph and physical paths through the matrix. The photon's path is a superposition of all these physical paths. The time taken by the photon along a physical path corresponding to a Hamiltonian path in G is a fixed value equal to the sum of N distinct delays, and is different from the time along any other path. The graph is Hamiltonian if any one of N detectors placed in the output of the N units in row N detects the photon at this fixed time.

DOI
10.48550/arxiv.quant-ph/0101142

Related papers

Generalized fractional revival on graphs

Whitney Drazen

A continuous-time quantum walk is a process on a network of quantum particles that is governed by the transition matrix $U(t) = e^{-itA}$, where is $A$ is the adjacency matrix of the graph representing the network. Certain instantaneous phenomena occuring in quantum walks can be utilized in quantum computing algorithms. The two-vertex phenomenon fractional revival occurs between vertices $u$ and $v$ at time $t$ if the columns of $U(t)$ corresponding to $u$ and $v$ are only supported on the rows indexed by those same two vertices. This means that given any initial state supported only on vertices $u$ and $v$, the state of the system at time $t$ will again be supported only on those same two vertices. Fractional revival can be used to generate entanglement between two quantum particles. We will discuss $K$-fractional revival, the generalization of fractional revival to $K$, a larger subset of the vertices in our graph. We will also explore the related concept approximate $K$-fractional revival, which denotes the existence of a sequence of times for which $U(t)$ comes arbitrarily close to achieving $K$-fractional revival. Next, we will examine some spectral characterizations of these phenomena, which will allow us to determine if a given graph exhibits either $K$-fractional revival or approximate $K$-fractional revival. Lastly, we will detail families of examples of approximate $K$-fractional revival on path graphs.--Author's abstract

•Jan 1, 2021•0 citations

Quantum computing Hamiltonian cycles

Terry Rudolph

An algorithm for quantum computing Hamiltonian cycles of simple, cubic, bipartite graphs is discussed. It is shown that it is possible to evolve a quantum computer into an entanglement of states which map onto the set of all possible paths originating from a chosen vertex, and furthermore to subsequently project out all states not corresponding to Hamiltonian cycles.

arXiv:quant-ph/9603001•Mar 3, 1996•1 citation

ON SELECTING OPTIMAL PARAMETERS FOR DELAY TIME MEASUREMENT USING THE HONG–OU–MANDEL EFFECT

Dmitry Kuts, Mikhail S. Podoshvedov, А. Г. Воронцов +2 more

The paper deals with the measurement error of the delay time between the arrivals at the beam splitter of two photons traveling through different channels in an optical system based on a HongOu-Mandel (HOM) interferometer. We consider the source of two-photon light to be the radiation of spontaneous parametric scattering (SPS) of light of the second type. The photon delay in one of the HOM interferometer channels can be induced by a change in the optical path length due to various factors: mechanical displacement of interferometer parts, changes in the refractive index of the medium caused by temperature variations, electric fields, etc. In the scheme, the outputs of the beam splitter are connected to single-photon detectors, which send signals to a coincidence counter upon photon detection. The coincidence counter data determine the delay time. The authors determine the absolute error in estimating the delay time in terms of the biphoton spectral width, the visibility, calculated from the maximum and minimum values of the coincidence counter signal, and the estimated delay time value itself. The derived expression facilitates finding the estimated delay time value. The study reveals that for a fixed biphoton field width, the delay time corresponding to the minimum absolute error value approaches the inflection point of the coincidence-time curve with decreasing visibility. This should be taken into account when designing measuring devices based on the Hong-Ou-Mandel interferometer.

Bulletin of the South Ural State University series Mathematics Mechanics Physics•Jan 1, 2025•0 citations

Universal two-body-Hamiltonian quantum computing

Daniel Nagaj

We present a Hamiltonian quantum-computation scheme universal for quantum computation. Our Hamiltonian is a sum of a polynomial number (in the number of gates $L$ in the quantum circuit) of constant-norm, time-independent, two-body interaction terms. Furthermore, each qubit in the system interacts only with a constant number of other qubits in a three-layer, geometrically local layout. The computer runs in three steps---it starts in a simple initial product state, evolves according to a time-independent Hamiltonian for time of order ${L}^{2}$ (up to logarithmic factors), and finishes with a two-qubit measurement. Our model improves previous universal two-local-Hamiltonian constructions, as it avoids using perturbation gadgets and large energy-penalty terms in the Hamiltonian, which would result in a large required run time.

arXiv:1002.0420•Physical Review A•Mar 27, 2012•26 citations

A route to quantum computing through the theory of quantum graphs

Фаррох Разавиниа

Based on our previous works, and in order to relate them with the theory of quantum graphs and the quantum computing principles, we once again try to introduce some newly developed technical structures just by relying on our toy example, the coordinate ring of $n\times n$ quantum matrix algebra $M_q(n)$, and the associated directed locally finite graphs $\mathcal{G}(Π_n)$, and the Cuntz-Krieger $C^*$-graph algebras. Meaningly, we introduce a $(4i-6)$-qubit quantum system by using the Cuntz-Krieger $\mathcal{G}(Π_i)$-families associated to the $4i-6$ distinct Hamiltonian paths of $\mathcal{G}(Π_i)$, for $i\in\{2,\cdots,n\}$. We also will present a proof of a claim raised in our previous paper concerning the graph $C^*$-algebra structure and the associated Cuntz-Krieger $\mathcal{G}(Π_n)$-families.

arXiv:2404.13773•Apr 21, 2024•0 citations

Algebraic Aspects of Multi-Particle Quantum Walks

Jamie Smith

A continuous time quantum walk consists of a particle moving among the vertices of a graph G. Its movement is governed by the structure of the graph. More formally, the adjacency matrix A is the Hamiltonian that determines the movement of our particle. Quantum walks have found a number of algorithmic applications, including unstructured search, element distinctness and Boolean formula evaluation. We will examine the properties of periodicity and state transfer. In particular, we will prove a result of the author along with Godsil, Kirkland and Severini, which states that pretty good state transfer occurs in a path of length n if and only if the n+1 is a power of two, a prime, or twice a prime. We will then examine the property of strong cospectrality, a necessary condition for pretty good state transfer from u to v. \n \nWe will then consider quantum walks involving more than one particle. In addition to moving around the graph, these particles interact when they encounter one another. Varying the nature of the interaction term gives rise to a range of different behaviours. We will introduce two graph invariants, one using a continuous-time multi-particle quantum walk, and the other using a discrete-time quantum walk. Using cellular algebras, we will prove several results which characterize the strength of these two graph invariants. \n \nLet A be an association scheme of n × n matrices. Then, any element of A can act on the space of n × n matrices by left multiplication, right multiplication, and Schur multiplication. The set containing these three linear mappings for all elements of A generates an algebra. This is an example of a Jaeger algebra. Although these algebras were initially developed by Francois Jaeger in the context of spin models and knot invariants, they prove to be useful in describing multi-particle walks as well. We will focus on triply-regular association schemes, proving several new results regarding the representation of their Jaeger algebras. As an example, we present the simple modules of a Jaeger algebra for the 4-cube.

•Dec 4, 2012•4 citations
A quantum computing scheme that uses a single photon and multiple-slit gratings is suggested for the Hamiltonian path problem on a simple graph G of N vertices. The photon is input to an N-slit grating followed by an N x N matrix of `processing units'. A unit consists of a delay line followed by a grating with k slits (0 < k < N) whose outputs are directed to k units in the next row in a manner determined by the adjacency matrix of G. There is a one-to-one mapping between paths of length N-1 in the graph and physical paths through the matrix. The photon's path is a superposition of all these physical paths. The time taken by the photon along a physical path corresponding to a Hamiltonian path in G is a fixed value equal to the sum of N distinct delays, and is different from the time along any other path. The graph is Hamiltonian if any one of N detectors placed in the output of the N units in row N detects the photon at this fixed time.
A continuous-time quantum walk is a process on a network of quantum particles that is governed by the transition matrix U(t)=e−itAU(t) = e^{-itA}U(t)=e−itA, where is AAA is the adjacency matrix of the graph representing the network. Certain instantaneous phenomena occuring in quantum walks can be utilized in quantum computing algorithms. The two-vertex phenomenon fractional revival occurs between vertices uuu and vvv at time ttt if the columns of U(t)U(t)U(t) corresponding to uuu and vvv are only supported on the rows indexed by those same two vertices. This means that given any initial state supported only on vertices uuu and vvv, the state of the system at time ttt will again be supported only on those same two vertices. Fractional revival can be used to generate entanglement between two quantum particles. We will discuss KKK-fractional revival, the generalization of fractional revival to KKK, a larger subset of the vertices in our graph. We will also explore the related concept approximate KKK-fractional revival, which denotes the existence of a sequence of times for which U(t)U(t)U(t) comes arbitrarily close to achieving KKK-fractional revival. Next, we will examine some spectral characterizations of these phenomena, which will allow us to determine if a given graph exhibits either KKK-fractional revival or approximate KKK-fractional revival. Lastly, we will detail families of examples of approximate KKK-fractional revival on path graphs.--Author's abstract
The paper deals with the measurement error of the delay time between the arrivals at the beam splitter of two photons traveling through different channels in an optical system based on a HongOu-Mandel (HOM) interferometer. We consider the source of two-photon light to be the radiation of spontaneous parametric scattering (SPS) of light of the second type. The photon delay in one of the HOM interferometer channels can be induced by a change in the optical path length due to various factors: mechanical displacement of interferometer parts, changes in the refractive index of the medium caused by temperature variations, electric fields, etc. In the scheme, the outputs of the beam splitter are connected to single-photon detectors, which send signals to a coincidence counter upon photon detection. The coincidence counter data determine the delay time. The authors determine the absolute error in estimating the delay time in terms of the biphoton spectral width, the visibility, calculated from the maximum and minimum values of the coincidence counter signal, and the estimated delay time value itself. The derived expression facilitates finding the estimated delay time value. The study reveals that for a fixed biphoton field width, the delay time corresponding to the minimum absolute error value approaches the inflection point of the coincidence-time curve with decreasing visibility. This should be taken into account when designing measuring devices based on the Hong-Ou-Mandel interferometer.
We present a Hamiltonian quantum-computation scheme universal for quantum computation. Our Hamiltonian is a sum of a polynomial number (in the number of gates LLL in the quantum circuit) of constant-norm, time-independent, two-body interaction terms. Furthermore, each qubit in the system interacts only with a constant number of other qubits in a three-layer, geometrically local layout. The computer runs in three steps---it starts in a simple initial product state, evolves according to a time-independent Hamiltonian for time of order L2{L}^{2}L2 (up to logarithmic factors), and finishes with a two-qubit measurement. Our model improves previous universal two-local-Hamiltonian constructions, as it avoids using perturbation gadgets and large energy-penalty terms in the Hamiltonian, which would result in a large required run time.
Based on our previous works, and in order to relate them with the theory of quantum graphs and the quantum computing principles, we once again try to introduce some newly developed technical structures just by relying on our toy example, the coordinate ring of n×nn\times nn×n quantum matrix algebra Mq(n)M_q(n)Mq​(n), and the associated directed locally finite graphs G(Πn)\mathcal{G}(Π_n)G(Πn​), and the Cuntz-Krieger C∗C^*C∗-graph algebras. Meaningly, we introduce a (4i−6)(4i-6)(4i−6)-qubit quantum system by using the Cuntz-Krieger G(Πi)\mathcal{G}(Π_i)G(Πi​)-families associated to the 4i−64i-64i−6 distinct Hamiltonian paths of G(Πi)\mathcal{G}(Π_i)G(Πi​), for i∈{2,⋯ ,n}i\in\{2,\cdots,n\}i∈{2,⋯,n}. We also will present a proof of a claim raised in our previous paper concerning the graph C∗C^*C∗-algebra structure and the associated Cuntz-Krieger G(Πn)\mathcal{G}(Π_n)G(Πn​)-families.
A continuous time quantum walk consists of a particle moving among the vertices of a graph G. Its movement is governed by the structure of the graph. More formally, the adjacency matrix A is the Hamiltonian that determines the movement of our particle. Quantum walks have found a number of algorithmic applications, including unstructured search, element distinctness and Boolean formula evaluation. We will examine the properties of periodicity and state transfer. In particular, we will prove a result of the author along with Godsil, Kirkland and Severini, which states that pretty good state transfer occurs in a path of length n if and only if the n+1 is a power of two, a prime, or twice a prime. We will then examine the property of strong cospectrality, a necessary condition for pretty good state transfer from u to v. \n \nWe will then consider quantum walks involving more than one particle. In addition to moving around the graph, these particles interact when they encounter one another. Varying the nature of the interaction term gives rise to a range of different behaviours. We will introduce two graph invariants, one using a continuous-time multi-particle quantum walk, and the other using a discrete-time quantum walk. Using cellular algebras, we will prove several results which characterize the strength of these two graph invariants. \n \nLet A be an association scheme of n × n matrices. Then, any element of A can act on the space of n × n matrices by left multiplication, right multiplication, and Schur multiplication. The set containing these three linear mappings for all elements of A generates an algebra. This is an example of a Jaeger algebra. Although these algebras were initially developed by Francois Jaeger in the context of spin models and knot invariants, they prove to be useful in describing multi-particle walks as well. We will focus on triply-regular association schemes, proving several new results regarding the representation of their Jaeger algebras. As an example, we present the simple modules of a Jaeger algebra for the 4-cube.