arXiv:quant-ph/9603001

Quantum computing Hamiltonian cycles

Terry Rudolph

Published Mar 3, 1996• 1 citation

Abstract

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.

DOI: 10.48550/arxiv.quant-ph/9603001

Related papers

An Alternative Adiabatic Quantum Algorithm for the Hamiltonian Cycle Problem

Da-Jian Zhang, D. M. Tong, Yao Lu +1 more

Abstract We put forward an alternative quantum algorithm for finding Hamiltonian cycles in any N-vertex graph based on adiabatic quantum computing. With a von Neumann measurement on the final state, one may determine whether there is a Hamiltonian cycle in the graph and pick out a cycle if there is any. Although the proposed algorithm provides a quadratic speedup, it gives an alternative algorithm based on adiabatic quantum computation, which is of interest because of its inherent robustness.

Communications in Theoretical PhysicsMay 1, 20153 citations

A quantum computing scheme for the Hamiltonian path problem

G. Sampath

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.

arXiv:quant-ph/0101142Jan 30, 20010 citations

Algorithmes quantiques, cycles hamiltoniens et la k-coloration des graphes

Mohamed Sghiar

I will prove the existence of the Feynman quantum algorithm, polynomial and of the order $ \mathcal{ O } (n ^ 3 ) $ which inform us about the presence of the Hamiltonian cycles in a graph with cardinality n and in this case allows us to find them completely. And I will also prove the existence of the Pauli quantum algorithm with the order $\mathcal { O } (n ^ 3) $ which enable us to know whether the k-coloring graph is possible and make us this coloration if it is possible.

Apr 4, 20163 citations

Correspondence between the Hamiltonian cycle problem and the quantum lattice gauge theory

Xiaopeng Cui, Yu Shi

Abstract We propose the correspondence between the Hamiltonian cycle (HC) problem in graph theory and the quantum lattice gauge theory (QZ2LGT) defined on the lattice dual to that graph. For the QZ2LGT, when the coupling parameter g is less than the critical value g c , the ground state is a superposition of all configurations with closed strings of same spins, which can be obtained by using an adiabatic quantum algorithm. A subsequent search for a HC among those closed strings solves the original HC problem. The method is demonstrated for random samples of small graphs.

Europhysics Letters (EPL)Nov 1, 20231 citation

Entanglement of multi-qubit quantum graph states and studies structural properties of tripartite graphs with quantum computing

Kh. P. Gnatenko

We propose a method for constructing multi-qubit entangled quantum states that represent weighted tripartite graphs, and develop approaches for investigating their structural properties using quantum computing. In the general case of multi-qubit states corresponding to arbitrary tripartite graph structures, we derive an expression for the entanglement distance. We establish a connection between entanglement and properties of the corresponding tripartite graphs. Namely, we show that the entanglement of a qubit with the rest of the system in a quantum tripartite graph state depends on the weights of the arcs in the neighborhood of the corresponding vertex, as well as on its degree with respect to the vertex sets of the tripartite graph. As an illustrative example, we consider a tripartite graph forming a triangle and evaluate the entanglement distance with quantum computing. We also compute quantum correlators for the general case of tripartite quantum graph states and relate these quantities to structural features of the underlying graphs, including the number of non-overlapping neighbors, the number of common neighbors of the corresponding vertices, and the number of 4-cycles. Obtained relationships between the quantum properties of multi-qubit states and the structural features of tripartite graphs opens up the possibility of investigating classical systems, such as tripartite graphs, using quantum computing. It is worth emphasizing that tripartite graphs have applications in practical problems, including resource allocation, scheduling, and database and hypergraph modeling.

quant-pharXiv:2604.27829May 1, 20260 citations

Transformation of Quantum States in Quantum Computation

Jun Lu

Quantum computation is based on transformation of quantum states. Quantum bits are two-level quantum systems, and as the simplest elementary building blocks for a quantum computer, they provide a convenient labeling for pairs of states and their physical realizations. Closed quantum systems evolve unitarily as determined by their Hamiltonians, but to perform quantum computation one must be able to control the Hamiltonian to effect an arbitrary selection from a universal family of unitary transformations.

Applied Mechanics and MaterialsJul 1, 20110 citations