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

Brazilian Conference on Intelligent Systems

Solving NP-complete Problems Using Quantum Weightless Neuron Nodes

Fernando M. de Paula Neto, Teresa B. Ludermir, Wilson Rosa de Oliveira, Adenilton José da Silva

Published Nov 1, 2015• 5 citations
Publisher

Abstract

Despite neural networks have super-Turing computing power, there is no known algorithm for obtaining a classical neural networks that solves NP-complete problems in polynomial time. However this paper shows that a quantum neural networks model coupled with a non-unitary operator can solve 3-SAT in polynomial time. The proposed method uses a network circuit to represent a Boolean logic function and a non-unitary operator to decide the satisfiability. The parameters of the network is set deterministically and manually, accordingly to the problem at hand with neither quantum nor classical learning.

DOI
10.1109/bracis.2015.22

Related papers

Vector space weightless neural networks.

Wilson Rosa de Oliveira, Adenilton José da Silva, Teresa B. Ludermir

By embedding the boolean space Z2 as an orthonormal basis in a vec- tor space we can treat the RAM based neuron as a matrix (operator) acting on the vector space. We show how this model (inspired by our research on quantum neu- ral networks) is of sufficient generality as to have classical weighted (perceptron- like), classical weightless (RAM-based, PLN, etc), quantum weighted and quantum weightless neural models as particular cases. It is also indicated how one could use it to polynomially solve 3-SAT and briefly mention how could one train this novel model.

The European Symposium on Artificial Neural Networks•Jan 1, 2014•3 citations

Generalized quantum Turing machine and its use to find an algorithm solving NP-Complete problem

Satoshi Iriyama, Masanori Ohya

Ohya and Volovich found the quantum algorithm with a chaos dynamics, called the OV SAT algorithm which enabled to solve NP-Complete problem in polynomial time. It is proved that the unitary operator of the quantum algorithm can be constructed by a product of so called fundamental gates. To discuss the computational complexity rigorously, we introduced a generalized quantum Turing machine(GQTM) where the computational process is given by quantum channels including a dispative dynamics and the configuration is represented by density operators. In this paper, we explain the GQTM and the OV SAT algorithm, then we discuss the computational complexity of OV SAT algorithm. Finally, we introduce some resent results and topics by use of GQTM.

International Symposium on Applied Sciences in Biomedical and Communication Technologies•Nov 1, 2010•1 citation

On the Universality of Quantum Logical Neural Networks

Adenilton José da Silva, Teresa B. Ludermir, Wilson Rosa de Oliveira

In this paper we investigate the computational power of the quantum weightless neural networks (q-WNN) and propose a novel quantum weightless neural node. The new quantum neuron is derived from the quantum probabilistic logic node (qPLN), which is a mathematical quantisation of the weightless neural node PLN. By a slight modification on the input lines of the qPLN node it is possible to define the quantum psi-neuron. We show in this paper that psi-neurons can be used to approximate any quantum circuit.

Brazilian Symposium on Neural Networks (SBRN)•Oct 1, 2012•7 citations

Neural networks with quantum architecture and quantum learning

Massimo Panella, Giuseppe Martinelli

Abstract A method is proposed for solving the two key problems facing quantum neural networks: introduction of nonlinearity in the neuron operation and efficient use of quantum superposition in the learning algorithm. The former is indirectly solved by using suitable Boolean functions. The latter is based on the use of a suitable nonlinear quantum circuit. The resulting learning procedure does not apply any optimization method. The optimal neural network is obtained by applying an exhaustive search among all the possible solutions. The exhaustive search is carried out by the proposed quantum circuit composed of both linear and nonlinear components. Copyright © 2009 John Wiley & Sons, Ltd.

International Journal of Circuit Theory and Applications•Jul 23, 2009•75 citations

Generalized Quantum Turing Machine and Its Use to Find an Algorithm Solving NP-Complete Problem (Invited Paper)

Satoshi Iriyama, Masanori Ohya

Ohya and Volovich found the quantum algorithm with a chaos dynamics, called the OV SAT algorithm which enabled to solve NP-Complete problem in polynomial time. It is proved that the unitary operator of the quantum algorithm can be constructed by a product of so called fundamental gates. To discuss the computational complexity rigorously, we intro- duced a generalized quantum Turing machine(GQTM) where the computational process is given by quantum channels including a dispative dynamics and the configuration is represented by density operators. In this paper, we explain the GQTM and the OV SAT algorithm, then we discuss the computational complexity of OV SAT algorithm. Finally, we introduce some resent results and topics by use of GQTM.

•Jan 1, 2010•0 citations

A quantum method to test the satisfiability of Boolean functions

Jin Qiang Wang, Jialin Chen, Chaofan Yu +1 more

Satisfiability (SAT) problem is one of the NP-hard problems. General SAT problem can be solved in polynomial time when the given formula contains only binary clauses (2-SAT). Quantum computation possesses some virtues that exceeding classical computation in speed, therefore it has the potential ability to solve NP-complete problems better than with classical methods. This paper introduces a new method to test the satisfiability of Boolean functions based on quantum ETOF gates.

IEEE International Conference on Solid-State and Integrated Circuit Technology•Oct 1, 2012•0 citations
Despite neural networks have super-Turing computing power, there is no known algorithm for obtaining a classical neural networks that solves NP-complete problems in polynomial time. However this paper shows that a quantum neural networks model coupled with a non-unitary operator can solve 3-SAT in polynomial time. The proposed method uses a network circuit to represent a Boolean logic function and a non-unitary operator to decide the satisfiability. The parameters of the network is set deterministically and manually, accordingly to the problem at hand with neither quantum nor classical learning.
By embedding the boolean space Z2 as an orthonormal basis in a vec- tor space we can treat the RAM based neuron as a matrix (operator) acting on the vector space. We show how this model (inspired by our research on quantum neu- ral networks) is of sufficient generality as to have classical weighted (perceptron- like), classical weightless (RAM-based, PLN, etc), quantum weighted and quantum weightless neural models as particular cases. It is also indicated how one could use it to polynomially solve 3-SAT and briefly mention how could one train this novel model.
Ohya and Volovich found the quantum algorithm with a chaos dynamics, called the OV SAT algorithm which enabled to solve NP-Complete problem in polynomial time. It is proved that the unitary operator of the quantum algorithm can be constructed by a product of so called fundamental gates. To discuss the computational complexity rigorously, we introduced a generalized quantum Turing machine(GQTM) where the computational process is given by quantum channels including a dispative dynamics and the configuration is represented by density operators. In this paper, we explain the GQTM and the OV SAT algorithm, then we discuss the computational complexity of OV SAT algorithm. Finally, we introduce some resent results and topics by use of GQTM.
In this paper we investigate the computational power of the quantum weightless neural networks (q-WNN) and propose a novel quantum weightless neural node. The new quantum neuron is derived from the quantum probabilistic logic node (qPLN), which is a mathematical quantisation of the weightless neural node PLN. By a slight modification on the input lines of the qPLN node it is possible to define the quantum psi-neuron. We show in this paper that psi-neurons can be used to approximate any quantum circuit.
Abstract A method is proposed for solving the two key problems facing quantum neural networks: introduction of nonlinearity in the neuron operation and efficient use of quantum superposition in the learning algorithm. The former is indirectly solved by using suitable Boolean functions. The latter is based on the use of a suitable nonlinear quantum circuit. The resulting learning procedure does not apply any optimization method. The optimal neural network is obtained by applying an exhaustive search among all the possible solutions. The exhaustive search is carried out by the proposed quantum circuit composed of both linear and nonlinear components. Copyright © 2009 John Wiley & Sons, Ltd.
Ohya and Volovich found the quantum algorithm with a chaos dynamics, called the OV SAT algorithm which enabled to solve NP-Complete problem in polynomial time. It is proved that the unitary operator of the quantum algorithm can be constructed by a product of so called fundamental gates. To discuss the computational complexity rigorously, we intro- duced a generalized quantum Turing machine(GQTM) where the computational process is given by quantum channels including a dispative dynamics and the configuration is represented by density operators. In this paper, we explain the GQTM and the OV SAT algorithm, then we discuss the computational complexity of OV SAT algorithm. Finally, we introduce some resent results and topics by use of GQTM.