Comparison among Classical,Probabilistic and Quantum Algorithms for Hamiltonian Cycle Problem

The Hamiltonian cycle problem(HCP),which is an NP-complete problem,consists of having a graph G with n nodes and m edges and finding the path that connects each node exactly once.In this paper we compare some algorithms to solve a Hamiltonian cycle problem,using different models of computations and especially the probabilistic and quantum ones.Starting from the classical probabilistic approach of random walks,we take a step to the quantum direction by involving an ad hoc designed Quantum Turing Machine(QTM),which can be a useful conceptual project tool for quantum algorithms.Introducing several constraints to the graphs,our analysis leads to not-exponential speedup improvements to the best-known algorithms.In particular,the results are based on bounded degree graphs(graphs with nodes having a maximum number of edges)and graphs with the right limited number of nodes and edges to allow them to outperform the other algorithms.

Global Optimization for Solving Linear Non-Quadratic Optimal Control Problems

This paper presents a global optimization approach to solving linear non-quadratic optimal control problems. The main work is to construct a differential flow for finding a global minimizer of the Hamiltonian function over a Euclid space. With the Pontryagin principle, the optimal control is characterized by a function of the adjoint variable and is obtained by solving a Hamiltonian differential boundary value problem. For computing an optimal control, an algorithm for numerical practice is given with the description of an example.

An optical fiber network oracle for NP-complete problems

The modern information society is enabled by photonic fiber networks characterized by huge coverage and great complexity and ranging in size from transcontinental submarine telecommunication cables to fiber to the home and local segments.This world-wide network has yet to match the complexity of the human brain,which contains a hundred billion neurons,each with thousands of synaptic connections on average.However,it already exceeds the complexity of brains from primitive organisms,i.e.,the honey bee,which has a brain containing approximately one million neurons.In this study,we present a discussion of the computing potential of optical networks as information carriers.Using a simple fiber network,we provide a proof-of-principle demonstration that this network can be treated as an optical oracle for the Hamiltonian path problem,the famous mathematical complexity problem of finding whether a set of towns can be travelled via a path in which each town is visited only once.Pronouncement of a Hamiltonian path is achieved by monitoring the delay of an optical pulse that interrogates the network,and this delay will be equal to the sum of the travel times needed to visit all of the nodes(towns).We argue that the optical oracle could solve this NP-complete problem hundreds of times faster than brute-force computing.Additionally,we discuss secure communication applications for the optical oracle and propose possible implementation in silicon photonics and plasmonic networks.

Indefinite stochastic linear-quadratic optimal control problems with random jumps and related stochastic Riccati equations

We discuss the stochastic linear-quadratic(LQ) optimal control problem with Poisson processes under the indefinite case. Based on the wellposedness of the LQ problem, the main idea is expressed by the definition of relax compensator that extends the stochastic Hamiltonian system and stochastic Riccati equation with Poisson processes(SREP) from the positive definite case to the indefinite case. We mainly study the existence and uniqueness of the solution for the stochastic Hamiltonian system and obtain the optimal control with open-loop form. Then, we further investigate the existence and uniqueness of the solution for SREP in some special case and obtain the optimal control in close-loop form.

An Alternative Adiabatic Quantum Algorithm for the Hamiltonian Cycle Problem

We put forward an alternative quantum algorithm for finding ttamiltonian cycles in any N-vertex graph based on adiabatic quantum computing. With a yon Neumann measurement on the final state, one may determine whether there is a HamiRonian 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.