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

Linear and nonlinear quantum algorithms made explicit

Mitchell Chiew

Published Jan 1, 2019• 0 citations
Publisher

Abstract

Quantum computing literature is unstandardized and often-times unwieldy. We design and formalise explicit quantum algorithms with rubrics, pseudocode, quantum circuit diagrams, and exact order-of-magnitude expressions for their complexity. We devise new linear quantum algorithms for representing permutations of objects that outperform the previous world standard. Nonlinear quantum computing is a speculative field, and has the potential to solve NP-complete and harder problems. We find shortcomings in existing nonlinear quantum algorithms, and devise our own explicit algorithm that leaves no doubt as to the power of nonlinear quantum computing. Our work shows the advantage of making quantum algorithms explicit.

DOI
10.26182/5db64ccf46f91

Related papers

On nonlinear transformations in quantum computation

Zoë Holmes, Nolan J. Coble, Andrew T. Sornborger +1 more

While quantum computers are naturally well-suited to implementing linear operations, it is less clear how to implement nonlinear operations on quantum computers. However, nonlinear subroutines may prove key to a range of applications of quantum computing from solving nonlinear equations to data processing and quantum machine learning. Here we develop a series of basic subroutines for implementing nonlinear transformations of input quantum states. Our algorithms are framed around the concept of a weighted state, a mathematical entity describing the output of an operational procedure involving both quantum circuits and classical post-processing.

arXiv:2112.12307•Dec 23, 2021•1 citation

Solving quantum circuit compilation problem variants through genetic algorithms

Lis Arufe, Riccardo Rasconi, Angelo Oddi +2 more

Abstract The gate-based model is one of the leading quantum computing paradigms for representing quantum circuits. Within this paradigm, a quantum algorithm is expressed in terms of a set of quantum gates that are executed on the quantum hardware over time, subject to a number of constraints whose satisfaction must be guaranteed before running the circuit, to allow for feasible execution. The need to guarantee the previous feasibility condition gives rise to the Quantum Circuit Compilation Problem (QCCP). The QCCP has been demonstrated to be NP-Complete, and can be considered as a Planning and Scheduling problem. In this paper, we consider quantum compilation instances deriving from the general Quantum Approximation Optimization Algorithm (QAOA), applied to the MaxCut problem, devised to be executed on Noisy Intermediate Scale Quantum (NISQ) hardware architectures. More specifically, in addition to the basic QCCP version, we also tackle other variants of the same problem such as the QCCP-X (QCCP with crosstalk constraints), the QCCP-V (QCCP with variable qubit state initialization), as well as the QCCP-VX that includes both previous variants. All problem variants are solved using genetic algorithms. We perform an experimental study across a conventional set of instances taken from the literature, and show that the proposed genetic algorithm, termed $$GA_{VX}$$ G A VX , outperforms previous approaches in the literature.

Natural Computing•Aug 17, 2023•2 citations

A Quantum Computing Based Solution Approach for NP-Complete Problems

Seda Nur Gungor, Mehmet Karaköse

Although NP-complete problems have solutions that can be verified in polynomial time, their exponential computational complexity presents significant challenges for classical computing methods. This study focuses on transferring various NP-complete problems into the quantum computing framework. The application of specific quantum computing algorithms is proposed for solving these problems. Within the scope of this study, a reusable quantum component with problem-specific constraints is designed, and a quantum circuit model is introduced to adapt the Quantum Feasibility Labeling algorithm for solving the Maximum Clique problem. Additionally, the Quick Quantum Search algorithm, which performs a search with a single oracle call, is integrated into the solution of the Maximum Independent Set problem. The proposed quantum circuits provide illustrative examples of how the components of an NP-complete problem can be represented in a quantum computing environment and how problem-specific constraints can be implemented within a quantum circuit. The utilization of modular circuit designs effectively demonstrates the applicability of larger and more complex problems in quantum environments. These approaches not only enable more efficient use of computational resources compared to traditional methods but also lead to significant reductions in solution times. This study provides a comprehensive framework that not only demonstrates the practicality of quantum circuits for small-scale NP-complete problems but also lays the groundwork for addressing larger and more complex challenges in future quantum computing applications.

•Feb 19, 2025•4 citations

Quantum computation for solving linear systems

Yudong Cao

Quantum computation is a subject born out of the combination between physics and computer science. It studies how the laws of quantum mechanics can be exploited to perform computations much more efficiently than current computers (termed classical computers as oppose to quantum computers). The thesis starts by introducing ideas from quantum physics and theoretical computer science and based on these ideas, introducing the basic concepts in quantum computing. These introductory discussions are intended for non-specialists to obtain the essential knowledge needed for understanding the new results presented in the subsequent chapters. After introducing the basics of quantum computing, we focus on the recently proposed quantum algorithm for linear systems. The new results include i) special instances of quantum circuits that can be implemented using current experimental resources; ii) detailed quantum algorithms that are suitable for a broader class of linear systems. We show that for some particular problems the quantum algorithm is able to achieve exponential speedup over their classical counterparts.

•Jan 1, 2013•0 citations

Quantum algorithms: an overview

Ashley Montanaro

Abstract Quantum computers are designed to outperform standard computers by running quantum algorithms. Areas in which quantum algorithms can be applied include cryptography, search and optimisation, simulation of quantum systems and solving large systems of linear equations. Here we briefly survey some known quantum algorithms, with an emphasis on a broad overview of their applications rather than their technical details. We include a discussion of recent developments and near-term applications of quantum algorithms.

arXiv:1511.04206•npj Quantum Information•Jan 12, 2016•1,071 citations

Implementation of Classic Image Transformation Algorithm to Quantum State, Boundary Extraction and Transformation of Half-Tone Image to Binary

Sergey M. Gushanskiy, Viktor Potapov, Omar Correa Madrigal

Abstract The aim of the research is computer simulation of a quantum algorithm to solve the problem of transforming a classical image using quantum computing tools and methods, studying recognition algorithms and creating a recognition model using quantum methods. The method of quantum modeling makes it possible to convert a classical image into a quantum state, select boundaries and convert a grayscale image to a binary one, and shows the possibilities of the quantum information theory in interpreting classical problems. The main results of the article are the developed quantum algorithm that allows recognizing objects, as well as the quantum method aimed at representing/processing a color pixel image. The scientific novelty of the article is expressed in the construction of a quantum system, an exponential increase in the speed of solving computational NP-complete problems, which on classical machines can be solved in unacceptable time. The motivation for writing the work was a high growth interest in quantum computing and the benefits that they guarantee. The development of the theoretical foundations of creating software systems and the design of algorithms for new information technologies and specialized computing systems is a dynamic field, as evidenced by the number of existing works in this direction. The developed algorithms for various problems of complexity classes can give a significant gain in efficiency in comparison with existing classical ones and provide a solution to a number of complex mathematical (including cryptographic) problems.

Cybernetics and Information Technologies•Jun 1, 2020•3 citations
Quantum computing literature is unstandardized and often-times unwieldy. We design and formalise explicit quantum algorithms with rubrics, pseudocode, quantum circuit diagrams, and exact order-of-magnitude expressions for their complexity. We devise new linear quantum algorithms for representing permutations of objects that outperform the previous world standard. Nonlinear quantum computing is a speculative field, and has the potential to solve NP-complete and harder problems. We find shortcomings in existing nonlinear quantum algorithms, and devise our own explicit algorithm that leaves no doubt as to the power of nonlinear quantum computing. Our work shows the advantage of making quantum algorithms explicit.
While quantum computers are naturally well-suited to implementing linear operations, it is less clear how to implement nonlinear operations on quantum computers. However, nonlinear subroutines may prove key to a range of applications of quantum computing from solving nonlinear equations to data processing and quantum machine learning. Here we develop a series of basic subroutines for implementing nonlinear transformations of input quantum states. Our algorithms are framed around the concept of a weighted state, a mathematical entity describing the output of an operational procedure involving both quantum circuits and classical post-processing.
Abstract The gate-based model is one of the leading quantum computing paradigms for representing quantum circuits. Within this paradigm, a quantum algorithm is expressed in terms of a set of quantum gates that are executed on the quantum hardware over time, subject to a number of constraints whose satisfaction must be guaranteed before running the circuit, to allow for feasible execution. The need to guarantee the previous feasibility condition gives rise to the Quantum Circuit Compilation Problem (QCCP). The QCCP has been demonstrated to be NP-Complete, and can be considered as a Planning and Scheduling problem. In this paper, we consider quantum compilation instances deriving from the general Quantum Approximation Optimization Algorithm (QAOA), applied to the MaxCut problem, devised to be executed on Noisy Intermediate Scale Quantum (NISQ) hardware architectures. More specifically, in addition to the basic QCCP version, we also tackle other variants of the same problem such as the QCCP-X (QCCP with crosstalk constraints), the QCCP-V (QCCP with variable qubit state initialization), as well as the QCCP-VX that includes both previous variants. All problem variants are solved using genetic algorithms. We perform an experimental study across a conventional set of instances taken from the literature, and show that the proposed genetic algorithm, termed GAVXGA_{VX}GAVX​ G A VX , outperforms previous approaches in the literature.
Although NP-complete problems have solutions that can be verified in polynomial time, their exponential computational complexity presents significant challenges for classical computing methods. This study focuses on transferring various NP-complete problems into the quantum computing framework. The application of specific quantum computing algorithms is proposed for solving these problems. Within the scope of this study, a reusable quantum component with problem-specific constraints is designed, and a quantum circuit model is introduced to adapt the Quantum Feasibility Labeling algorithm for solving the Maximum Clique problem. Additionally, the Quick Quantum Search algorithm, which performs a search with a single oracle call, is integrated into the solution of the Maximum Independent Set problem. The proposed quantum circuits provide illustrative examples of how the components of an NP-complete problem can be represented in a quantum computing environment and how problem-specific constraints can be implemented within a quantum circuit. The utilization of modular circuit designs effectively demonstrates the applicability of larger and more complex problems in quantum environments. These approaches not only enable more efficient use of computational resources compared to traditional methods but also lead to significant reductions in solution times. This study provides a comprehensive framework that not only demonstrates the practicality of quantum circuits for small-scale NP-complete problems but also lays the groundwork for addressing larger and more complex challenges in future quantum computing applications.
Quantum computation is a subject born out of the combination between physics and computer science. It studies how the laws of quantum mechanics can be exploited to perform computations much more efficiently than current computers (termed classical computers as oppose to quantum computers). The thesis starts by introducing ideas from quantum physics and theoretical computer science and based on these ideas, introducing the basic concepts in quantum computing. These introductory discussions are intended for non-specialists to obtain the essential knowledge needed for understanding the new results presented in the subsequent chapters. After introducing the basics of quantum computing, we focus on the recently proposed quantum algorithm for linear systems. The new results include i) special instances of quantum circuits that can be implemented using current experimental resources; ii) detailed quantum algorithms that are suitable for a broader class of linear systems. We show that for some particular problems the quantum algorithm is able to achieve exponential speedup over their classical counterparts.
Abstract Quantum computers are designed to outperform standard computers by running quantum algorithms. Areas in which quantum algorithms can be applied include cryptography, search and optimisation, simulation of quantum systems and solving large systems of linear equations. Here we briefly survey some known quantum algorithms, with an emphasis on a broad overview of their applications rather than their technical details. We include a discussion of recent developments and near-term applications of quantum algorithms.
Abstract The aim of the research is computer simulation of a quantum algorithm to solve the problem of transforming a classical image using quantum computing tools and methods, studying recognition algorithms and creating a recognition model using quantum methods. The method of quantum modeling makes it possible to convert a classical image into a quantum state, select boundaries and convert a grayscale image to a binary one, and shows the possibilities of the quantum information theory in interpreting classical problems. The main results of the article are the developed quantum algorithm that allows recognizing objects, as well as the quantum method aimed at representing/processing a color pixel image. The scientific novelty of the article is expressed in the construction of a quantum system, an exponential increase in the speed of solving computational NP-complete problems, which on classical machines can be solved in unacceptable time. The motivation for writing the work was a high growth interest in quantum computing and the benefits that they guarantee. The development of the theoretical foundations of creating software systems and the design of algorithms for new information technologies and specialized computing systems is a dynamic field, as evidenced by the number of existing works in this direction. The developed algorithms for various problems of complexity classes can give a significant gain in efficiency in comparison with existing classical ones and provide a solution to a number of complex mathematical (including cryptographic) problems.