Editorial

3 pages, 166 KiB

Open AccessEditorial

Preface to the Special Issue on “Quantum Computing Algorithms and Computational Complexity”

by Fernando L. Pelayo and Mauro Mezzini

Mathematics 2022, 10(21), 4032; https://0-doi-org.brum.beds.ac.uk/10.3390/math10214032 - 30 Oct 2022

Viewed by 723

In 1982, Richard Feynman stated that in order to simulate quantum systems, we would rather go for a sort of brand-new powered quantum processor instead of a classical one [...] Full article

(This article belongs to the Special Issue Quantum Computing Algorithms and Computational Complexity)

Research

Jump to: Editorial

18 pages, 5245 KiB

Open AccessArticle

A Fast Quantum Image Component Labeling Algorithm

by Yan Li, Dapeng Hao, Yang Xu and Kinkeung Lai

Mathematics 2022, 10(15), 2718; https://0-doi-org.brum.beds.ac.uk/10.3390/math10152718 - 01 Aug 2022

Cited by 3 | Viewed by 1125

Abstract

Component Labeling, as a fundamental preprocessing task in image understanding and pattern recognition, is an indispensable task in digital image processing. It has been proved that it is one of the most time-consuming tasks within pattern recognition. In this paper, a fast quantum [...] Read more.

Component Labeling, as a fundamental preprocessing task in image understanding and pattern recognition, is an indispensable task in digital image processing. It has been proved that it is one of the most time-consuming tasks within pattern recognition. In this paper, a fast quantum image component labeling algorithm is proposed, which is the quantum counterpart of classical local-operator technique. A binary image is represented by the modified novel enhanced quantum image representation (NEQR) and a quantum parallel-shrink operator and quantum propagate operator are executed in succession, to finally obtain the component label. The time complexity of the proposed quantum image component labeling algorithm is

O (n^{2})

, and the spatial complexity of the quantum circuits designed is

O (c n)

. Simulation verifies the correctness of results. Full article

(This article belongs to the Special Issue Quantum Computing Algorithms and Computational Complexity)

► Show Figures

Figure 1

9 pages, 288 KiB

Open AccessArticle

Progress towards Analytically Optimal Angles in Quantum Approximate Optimisation

by Daniil Rabinovich, Richik Sengupta, Ernesto Campos, Vishwanathan Akshay and Jacob Biamonte

Mathematics 2022, 10(15), 2601; https://0-doi-org.brum.beds.ac.uk/10.3390/math10152601 - 26 Jul 2022

Cited by 6 | Viewed by 1137

Abstract

The quantum approximate optimisation algorithm is a p layer, time variable split operator method executed on a quantum processor and driven to convergence by classical outer-loop optimisation. The classical co-processor varies individual application times of a problem/driver propagator sequence to prepare a state [...] Read more.

The quantum approximate optimisation algorithm is a p layer, time variable split operator method executed on a quantum processor and driven to convergence by classical outer-loop optimisation. The classical co-processor varies individual application times of a problem/driver propagator sequence to prepare a state which approximately minimises the problem’s generator. Analytical solutions to choose optimal application times (called parameters or angles) have proven difficult to find, whereas outer-loop optimisation is resource intensive. Here we prove that the optimal quantum approximate optimisation algorithm parameters for

p = 1

layer reduce to one free variable and in the thermodynamic limit, we recover optimal angles. We moreover demonstrate that conditions for vanishing gradients of the overlap function share a similar form which leads to a linear relation between circuit parameters, independent of the number of qubits. Finally, we present a list of numerical effects, observed for particular system size and circuit depth, which are yet to be explained analytically. Full article

(This article belongs to the Special Issue Quantum Computing Algorithms and Computational Complexity)

► Show Figures

Figure 1

13 pages, 2388 KiB

Open AccessArticle

Quantum Weighted Fractional Fourier Transform

by Tieyu Zhao, Tianyu Yang and Yingying Chi

Mathematics 2022, 10(11), 1896; https://0-doi-org.brum.beds.ac.uk/10.3390/math10111896 - 01 Jun 2022

Cited by 2 | Viewed by 1344

Abstract

Quantum Fourier transform (QFT) is an important part of many quantum algorithms. However, there are few reports on quantum fractional Fourier transform (QFRFT). The main reason is that the definitions of fractional Fourier transform (FRFT) are diverse, while some definitions do not include [...] Read more.

Quantum Fourier transform (QFT) is an important part of many quantum algorithms. However, there are few reports on quantum fractional Fourier transform (QFRFT). The main reason is that the definitions of fractional Fourier transform (FRFT) are diverse, while some definitions do not include unitarity, which leads to some studies pointing out that there is no QFRFT. In this paper, we first present a reformulation of the weighted fractional Fourier transform (WFRFT) and prove its unitarity, thereby proposing a quantum weighted fractional Fourier transform (QWFRFT). The proposal of QWFRFT provides the possibility for many quantum implementations of signal processing. Full article

(This article belongs to the Special Issue Quantum Computing Algorithms and Computational Complexity)

► Show Figures

Figure 1

20 pages, 907 KiB

Open AccessArticle

GPS: A New TSP Formulation for Its Generalizations Type QUBO

by Saul Gonzalez-Bermejo, Guillermo Alonso-Linaje and Parfait Atchade-Adelomou

Mathematics 2022, 10(3), 416; https://0-doi-org.brum.beds.ac.uk/10.3390/math10030416 - 28 Jan 2022

Cited by 10 | Viewed by 3583

Abstract

We propose a new Quadratic Unconstrained Binary Optimization (QUBO) formulation of the Travelling Salesman Problem (TSP), with which we overcame the best formulation of the Vehicle Routing Problem (VRP) in terms of the minimum number of necessary variables. After, we will present a [...] Read more.

We propose a new Quadratic Unconstrained Binary Optimization (QUBO) formulation of the Travelling Salesman Problem (TSP), with which we overcame the best formulation of the Vehicle Routing Problem (VRP) in terms of the minimum number of necessary variables. After, we will present a detailed study of the constraints subject to the new TSP model and benchmark it with MTZ and native formulations. Finally, we will test whether the correctness of the formulation by entering it into a QUBO problem solver. The solver chosen is a D-Wave_2000Q6 quantum computer simulator due to the connection between Quantum Annealing and QUBO formulations. Full article

(This article belongs to the Special Issue Quantum Computing Algorithms and Computational Complexity)

► Show Figures

Figure 1

12 pages, 282 KiB

Open AccessArticle

Quantum Algorithms for Some Strings Problems Based on Quantum String Comparator

by Kamil Khadiev, Artem Ilikaev and Jevgenijs Vihrovs

Mathematics 2022, 10(3), 377; https://0-doi-org.brum.beds.ac.uk/10.3390/math10030377 - 26 Jan 2022

Cited by 8 | Viewed by 2043

Abstract

We study algorithms for solving three problems on strings. These are sorting of n strings of length k, “the Most Frequent String Search Problem”, and “searching intersection of two sequences of strings”. We construct quantum algorithms that are faster than classical (randomized [...] Read more.

We study algorithms for solving three problems on strings. These are sorting of n strings of length k, “the Most Frequent String Search Problem”, and “searching intersection of two sequences of strings”. We construct quantum algorithms that are faster than classical (randomized or deterministic) counterparts for each of these problems. The quantum algorithms are based on the quantum procedure for comparing two strings of length k in

O (\sqrt{k})

queries. The first problem is sorting n strings of length k. We show that classical complexity of the problem is

Θ (n k)

for constant size alphabet, but our quantum algorithm has

\tilde{O} (n \sqrt{k})

complexity. The second one is searching the most frequent string among n strings of length k. We show that the classical complexity of the problem is

Θ (n k)

, but our quantum algorithm has

\tilde{O} (n \sqrt{k})

complexity. The third problem is searching for an intersection of two sequences of strings. All strings have the same length k. The size of the first set is n, and the size of the second set is m. We show that the classical complexity of the problem is

Θ ((n + m) k)

, but our quantum algorithm has

\tilde{O} ((n + m) \sqrt{k})

complexity. Full article

(This article belongs to the Special Issue Quantum Computing Algorithms and Computational Complexity)

11 pages, 346 KiB

Open AccessArticle

On the Amplitude Amplification of Quantum States Corresponding to the Solutions of the Partition Problem

by Mauro Mezzini, Jose J. Paulet, Fernando Cuartero, Hernan I. Cruz and Fernando L. Pelayo

Mathematics 2021, 9(17), 2027; https://0-doi-org.brum.beds.ac.uk/10.3390/math9172027 - 24 Aug 2021

Cited by 1 | Viewed by 1493

Abstract

In this paper we investigate the effects of a quantum algorithm which increases the amplitude of the states corresponding to the solutions of the partition problem by a factor of almost two. The study is limited to one iteration. Full article

(This article belongs to the Special Issue Quantum Computing Algorithms and Computational Complexity)

► Show Figures

Figure 1

24 pages, 433 KiB

Open AccessArticle

On the Complexity of Finding the Maximum Entropy Compatible Quantum State

by Serena Di Giorgio and Paulo Mateus

Mathematics 2021, 9(2), 193; https://0-doi-org.brum.beds.ac.uk/10.3390/math9020193 - 19 Jan 2021

Cited by 3 | Viewed by 1777

Abstract

Herein we study the problem of recovering a density operator from a set of compatible marginals, motivated by limitations of physical observations. Given that the set of compatible density operators is not singular, we adopt Jaynes’ principle and wish to characterize a compatible [...] Read more.

Herein we study the problem of recovering a density operator from a set of compatible marginals, motivated by limitations of physical observations. Given that the set of compatible density operators is not singular, we adopt Jaynes’ principle and wish to characterize a compatible density operator with maximum entropy. We first show that comparing the entropy of compatible density operators is complete for the quantum computational complexity class QSZK, even for the simplest case of 3-chains. Then, we focus on the particular case of quantum Markov chains and trees and establish that for these cases, there exists a procedure polynomial in the number of subsystems that constructs the maximum entropy compatible density operator. Moreover, we extend the Chow–Liu algorithm to the same subclass of quantum states. Full article

(This article belongs to the Special Issue Quantum Computing Algorithms and Computational Complexity)

► Show Figures