Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Computing: The Turing way

Massimiliano Di Ventra

Published Feb 21, 2022• 0 citations
Publisher

Abstract

Abstract This Chapter introduces the Turing paradigm of computation and computational complexity classes. It discusses the algorithmic way combinatorial optimization problems are traditionally solved and explains why some of them are particularly difficult to solve with algorithms. It anticipates the need for non-perturbative approaches to the solution of such problems.

DOI
10.1093/oso/9780192845320.003.0002

Related papers

Computational models

Riccardo Manenti, Mário Motta

Abstract In this chapter, we introduce the definitions of automata Turing machines. We present different flavors of Turing machines including deterministic, probabilistic, and multi-tape machines. We present several complexity classes, i.e. collections of problems that can be solved by a machine with similar resources, including the P and NP classes. We present the Church-Turing thesis, which states that if a problem can be solved by a physical machine, then it can also be solved by any deterministic Turing machine. In the last part of the chapter, we introduce quantum Turing machines and the quantum circuit model. We study the complexity class BQP. This is the class of problems that can be solved by a quantum computer with polynomial resources and a small error probability. Finally, we introduce QMA, the quantum version of the complexity class NP. We present the k-LOCAL problem, and we show that this problem is in QMA

•Aug 25, 2023•0 citations

The Use of Algorithms and Quantum Computing to Optimization Issues

Prof. Sofia Lindgren

A new paradigm in computing, quantum computing has the ability to solve computational problems that were previously considered impossible for classical computers. Optimization problems are fundamental to many disciplines, including operations research, finance, machine learning, and logistics; this article investigates how quantum computing methods can be used to solve these problems. In order to conduct calculations in a way that is radically distinct from classical computers, quantum computers utilize quantum mechanical phenomena like entanglement and superposition. Because of this, quantum algorithms might potentially achieve exponential speedups over classical algorithms for specific optimization tasks by simultaneously exploring large solution spaces. A number of well-known quantum algorithms have been reviewed in this abstract, including Grover's algorithm and quantum annealing methods created by D-Wave Systems, among others. These algorithms aim to solve a wide variety of optimization problems, such as scheduling issues, optimization of portfolios, and combinatorial optimization. Their computational complexity, theoretical foundations, and real-world applications on existing and future quantum hardware are covered in detail.

Revista Infoacceso•Jul 28, 2026•0 citations

Randomized Computation

Thomas Watson

This chapter discusses randomized algorithms, which produce correct output with high probability. The chapter covers some classic randomized algorithms, complexity classes, and useful tools from probability theory. It also introduces the topic of efficient derandomization (turning randomized algorithms into non-randomized ones) in the time- and space-bounded settings.

Cambridge University Press eBooks•Oct 9, 2026•0 citations

Solving Combinatorial Optimization Problems on a Photonic Quantum Computer

Mateusz Slysz, Krzysztof Kurowski, Grzegorz Waligóra

Combinatorial optimization problems pose significant computational challenges across various fields, from logistics to cryptography. Traditional computational methods often struggle with their exponential complexity, motivating exploration into alternative paradigms such as quantum computing. In this paper, we investigate the application of photonic quantum computing to solve combinatorial optimization problems. Leveraging the principles of quantum mechanics, we demonstrate how photonic quantum computers can efficiently explore solution spaces and identify optimal solutions for a range of combinatorial problems. We provide an overview of quantum algorithms tailored for combinatorial optimization for different quantum architectures (boson sampling, quantum annealing and gate-based quantum computing). Additionally, we discuss the advantages and challenges of implementing those algorithms on photonic quantum hardware. Through experiments run on an 8-qumode photonic quantum device, as well as numerical simulations, we evaluate the performance of photonic quantum computers in solving representative combinatorial optimization problems, such as the Max-Cut problem and the Job Shop Scheduling Problem.

arXiv:2409.13781•Sep 19, 2024•1 citation

Background on computational complexity

István Miklós

In computational complexity theory, we distinguish decision, optimization, counting and sampling problems. Although this book is about the computational complexity of counting and sampling, counting and sampling problems are related to decision and optimization problems. Counting problems are always at least as hard as their decision counterparts. Indeed, if we can tell, say, the number of perfect matchings in a graph G , then naturally we can tell if there exists a perfect matching in G : G contains a perfect matching if and only if the number of perfect matchings in G is at least 1.

Chapman & Hall/CRC eBooks•Feb 21, 2019•0 citations

Variational Quantum Algorithm for Constrained Topology Optimization in Quantum Scientific Computing

Jungin E. Kim, Jinhwan Sul, Yan Wang

Quantum scientific computing has emerged as a new paradigm to solve difficult scientific computing problems on quantum computers. One of them is topology optimization, which is computationally expensive because the combinatorial optimization problem and partial differential equations need to be solved simultaneously. In this paper, we propose a novel variational quantum algorithm for topology optimization through quantum entanglement. Two quantum registers are used to encode the optimal configurations and the solutions to physical constraints, respectively. The tasks of finding the optimal material configuration and solving the physical constraints are performed simultaneously in a single loop. A constraint encoding scheme is also proposed to incorporate volume and topology constraints in optimization. The gate complexity of the proposed quantum algorithm is analyzed. The theoretical lower bound of the success probability is obtained. The algorithm is demonstrated with compliance minimization problems including truss structures and Messerschmitt-Bölkow-Blohm beams.

arXiv:2412.07099•Dec 10, 2024•0 citations
Abstract This Chapter introduces the Turing paradigm of computation and computational complexity classes. It discusses the algorithmic way combinatorial optimization problems are traditionally solved and explains why some of them are particularly difficult to solve with algorithms. It anticipates the need for non-perturbative approaches to the solution of such problems.
Abstract In this chapter, we introduce the definitions of automata Turing machines. We present different flavors of Turing machines including deterministic, probabilistic, and multi-tape machines. We present several complexity classes, i.e. collections of problems that can be solved by a machine with similar resources, including the P and NP classes. We present the Church-Turing thesis, which states that if a problem can be solved by a physical machine, then it can also be solved by any deterministic Turing machine. In the last part of the chapter, we introduce quantum Turing machines and the quantum circuit model. We study the complexity class BQP. This is the class of problems that can be solved by a quantum computer with polynomial resources and a small error probability. Finally, we introduce QMA, the quantum version of the complexity class NP. We present the k-LOCAL problem, and we show that this problem is in QMA
A new paradigm in computing, quantum computing has the ability to solve computational problems that were previously considered impossible for classical computers. Optimization problems are fundamental to many disciplines, including operations research, finance, machine learning, and logistics; this article investigates how quantum computing methods can be used to solve these problems. In order to conduct calculations in a way that is radically distinct from classical computers, quantum computers utilize quantum mechanical phenomena like entanglement and superposition. Because of this, quantum algorithms might potentially achieve exponential speedups over classical algorithms for specific optimization tasks by simultaneously exploring large solution spaces. A number of well-known quantum algorithms have been reviewed in this abstract, including Grover's algorithm and quantum annealing methods created by D-Wave Systems, among others. These algorithms aim to solve a wide variety of optimization problems, such as scheduling issues, optimization of portfolios, and combinatorial optimization. Their computational complexity, theoretical foundations, and real-world applications on existing and future quantum hardware are covered in detail.
Combinatorial optimization problems pose significant computational challenges across various fields, from logistics to cryptography. Traditional computational methods often struggle with their exponential complexity, motivating exploration into alternative paradigms such as quantum computing. In this paper, we investigate the application of photonic quantum computing to solve combinatorial optimization problems. Leveraging the principles of quantum mechanics, we demonstrate how photonic quantum computers can efficiently explore solution spaces and identify optimal solutions for a range of combinatorial problems. We provide an overview of quantum algorithms tailored for combinatorial optimization for different quantum architectures (boson sampling, quantum annealing and gate-based quantum computing). Additionally, we discuss the advantages and challenges of implementing those algorithms on photonic quantum hardware. Through experiments run on an 8-qumode photonic quantum device, as well as numerical simulations, we evaluate the performance of photonic quantum computers in solving representative combinatorial optimization problems, such as the Max-Cut problem and the Job Shop Scheduling Problem.
In computational complexity theory, we distinguish decision, optimization, counting and sampling problems. Although this book is about the computational complexity of counting and sampling, counting and sampling problems are related to decision and optimization problems. Counting problems are always at least as hard as their decision counterparts. Indeed, if we can tell, say, the number of perfect matchings in a graph G , then naturally we can tell if there exists a perfect matching in G : G contains a perfect matching if and only if the number of perfect matchings in G is at least 1.
Quantum scientific computing has emerged as a new paradigm to solve difficult scientific computing problems on quantum computers. One of them is topology optimization, which is computationally expensive because the combinatorial optimization problem and partial differential equations need to be solved simultaneously. In this paper, we propose a novel variational quantum algorithm for topology optimization through quantum entanglement. Two quantum registers are used to encode the optimal configurations and the solutions to physical constraints, respectively. The tasks of finding the optimal material configuration and solving the physical constraints are performed simultaneously in a single loop. A constraint encoding scheme is also proposed to incorporate volume and topology constraints in optimization. The gate complexity of the proposed quantum algorithm is analyzed. The theoretical lower bound of the success probability is obtained. The algorithm is demonstrated with compliance minimization problems including truss structures and Messerschmitt-Bölkow-Blohm beams.