• Home
  • Aktuelles
  • Technologie
  • Forschung
  • Lehre
  • Wirtschaft
  • Jobs
  • Home
  • Aktuelles
  • Technologie
  • Forschung
  • Lehre
  • Wirtschaft
  • Jobs
Kontakt
  • Deutsch
  • English

  • Home
  • Aktuelles
  • Technologie
  • Forschung
  • Lehre
  • Wirtschaft
  • Jobs
Kontakt
  • Deutsch
  • English

The Dynamic Time Warping Distance Measure as QUBO Formulation

The Dynamic Time Warping Distance Measure as Q U BO 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
Oettingenstr. 67
80538 München
Telefon: +49 89 2180-9153
E-Mail: qar-lab@mobile.ifi.lmu.de

© Copyright 2025

Allgemein

Team
Kontakt
Impressum

Social Media

Twitter Linkedin Github

Sprache

  • Deutsch
  • English
Cookie-Zustimmung verwalten
Wir verwenden Cookies, um unsere Website und unseren Service zu optimieren.
Funktional Immer aktiv
Die technische Speicherung oder der Zugang ist unbedingt erforderlich für den rechtmäßigen Zweck, die Nutzung eines bestimmten Dienstes zu ermöglichen, der vom Teilnehmer oder Nutzer ausdrücklich gewünscht wird, oder für den alleinigen Zweck, die Übertragung einer Nachricht über ein elektronisches Kommunikationsnetz durchzuführen.
Vorlieben
Die technische Speicherung oder der Zugriff ist für den rechtmäßigen Zweck der Speicherung von Präferenzen erforderlich, die nicht vom Abonnenten oder Benutzer angefordert wurden.
Statistiken
Die technische Speicherung oder der Zugriff, der ausschließlich zu statistischen Zwecken erfolgt. Die technische Speicherung oder der Zugriff, der ausschließlich zu anonymen statistischen Zwecken verwendet wird. Ohne eine Vorladung, die freiwillige Zustimmung deines Internetdienstanbieters oder zusätzliche Aufzeichnungen von Dritten können die zu diesem Zweck gespeicherten oder abgerufenen Informationen allein in der Regel nicht dazu verwendet werden, dich zu identifizieren.
Marketing
Die technische Speicherung oder der Zugriff ist erforderlich, um Nutzerprofile zu erstellen, um Werbung zu versenden oder um den Nutzer auf einer Website oder über mehrere Websites hinweg zu ähnlichen Marketingzwecken zu verfolgen.
Optionen verwalten Dienste verwalten Verwalten von {vendor_count}-Lieferanten Lese mehr über diese Zwecke
Einstellungen anzeigen
{title} {title} {title}