• Home
  • News
  • Technology
  • Research
  • Teaching
  • Business
  • Jobs
  • Home
  • News
  • Technology
  • Research
  • Teaching
  • Business
  • Jobs
Contact
  • de
  • en

  • Home
  • News
  • Technology
  • Research
  • Teaching
  • Business
  • Jobs
Contact
  • de
  • en

The Dynamic Time Warping Distance Measure as QUBO Formulation

The Dynamic Time Warping Distance Measure as QUBO Formulation

S. Feld, C. Roch, T. Gabor, M. To, and C. Linnhoff-Popien

Abstract

Dynamic Time Warping (DTW) is a representative of a distance measure that is able to calculate the distance between two time series. It is often used for the recognition of handwriting or spoken language. The metaheuristic Quantum Annealing (QA) can be used to solve combinatorial optimization problems. Similar to Simulated Annealing it seeks to find a global minimum of a target function. In order to use specialized QA hardware, the problem to be optimized needs to be translated into a Quadratic Unconstrained Binary Optimization (QUBO) problem. With this paper we investigate whether it is possible to transfer the DTW distance measure into a QUBO formulation. The motivation behind is the hope on an accelerated execution once the QA hardware scales up and the aspiration of gaining benefits due to quantum effects that are not given in the classical calculation. In principle, we find that it is possible to transform DTW into a QUBO formulation suitable for executing on QA hardware. Also, the algorithm returns not only the minimum total distance between two sequences, but also the corresponding warping path. However, there are several difficulties that make a manual intervention necessary.

IEEE 5th International Conference on Computer and Communication Systems (ICCCS 2020)

PDF Download


QAR-Lab – Quantum Applications and Research Laboratory
Ludwig-Maximilians-Universität München
Oettingenstraße 67
80538 Munich
Phone: +49 89 2180-9153
E-mail: qar-lab@mobile.ifi.lmu.de

© Copyright 2021

General

Team
Contact
Legal notice

Social Media

Twitter
Linkedin
Github

Language

  • de
  • en