Quantum mechanics

Algorithm

Quantum computer

Discrete mathematics

Theoretical computer science

Longest path problem

Computer science

Mathematical optimization

Physics

Organic chemistry

Graph

Mathematics

Quadratic unconstrained binary optimization

Mathematical analysis

Path (computing)

Quantum

Combinatorics

Mathematical economics

Logarithm

Logical matrix

Chemistry

Programming language

Shortest path problem

Group (periodic table)

Binary number

Arithmetic

Theoretical Computer Science

The longest path problem on graphs is an NP-hard optimization problem, and as such, it is not known to have an efficient classical solution in the general case. This study develops two quadratic unconstrained binary optimization (QUBO) formulations of this well-known problem. The first formulation is based on an approach outlined by (Bauckhage et al., 2018) for the shortest path problem and follows simply from the principle of assigning positions on the path to vertices; using k|V| binary variables, this formulation will find the longest path that visits exactly k of a graph's |V| vertices, if such a path exists. As a point of theoretical interest, we present a second formulation based on degree constraints that is more complicated, but reduces the dependence of the number of variables on k to logarithmic; specifically, it requires |V|+2|E|⌊log2⁡k⌋+3|E| binary variables to encode the longest path problem. We adapt these basic formulations for several variants of the standard longest path problem. Scaling factors for penalty terms and preprocessing time required to construct the Q matrix representing the problem are made explicit in the paper.

QUBO formulations of the longest path problem