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

arXiv:1202.1809 · Physical Review Letters

Virtual Parallel Computing and a Search Algorithm Using Matrix Product States

Claudio Chamon, Eduardo R. Mucciolo

Published Jul 20, 2012• 15 citations
arXivHTMLPDF

Abstract

We propose a form of parallel computing on classical computers that is based on matrix product states. The virtual parallelization is accomplished by representing bits with matrices and by evolving these matrices from an initial product state that encodes multiple inputs. Matrix evolution follows from the sequential application of gates, as in a logical circuit. The action by classical probabilistic one-bit and deterministic two-bit gates such as NAND are implemented in terms of matrix operations and, as opposed to quantum computing, it is possible to copy bits. We present a way to explore this method of computation to solve search problems and count the number of solutions. We argue that if the classical computational cost of testing solutions (witnesses) requires less than O(n2) local two-bit gates acting on n bits, the search problem can be fully solved in subexponential time. Therefore, for this restricted type of search problem, the virtual parallelization scheme is faster than Grover's quantum algorithm.

DOI
10.1103/physrevlett.109.030503

Related papers

Hardware Efficient Quantum Search Algorithm

Ji Liu, Huiyang Zhou

Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.

arXiv:2103.14196•Mar 26, 2021•15 citations

Mathlab Implementation of Quantum Computation in Searching an Unstructured Database

Iyabo Olukemi Awoyelu, P. Okoh

In the classical model of a computer, the most fundamental building block, the bit, can only exist in one of two distinct states, a 0 or a 1. Computations are carried out by logic gates that act on these bits to produce other bits. Unless there is duplicate (parallel) hardware, only one problem instance (i.e. input data set) can be handled at a time. In this classical computing, increasing the number of bits increases the complexity of the problem and the time necessary to arrive at a solution. A quantum algorithm consists of a sequence of operations on a register, to transform it into a state which, when measured, yields the desired result with high probability. An n-bit quantum register can store an exponential amount of information. This paper aims at taking advantage of the superiority of quantum computing over classical computing to solve the problem of searching unstructured databases for a particular item or more than one item in good time. The general aim of this work is to establish the correctness and optimality of Grover’s quantum database search algorithm compared against classical database search methods in order to investigate the superiority or otherwise of quantum computing over classical computing. This is followed by a simulation of the algorithm using a classical computer, namely through functions that are present in MATLAB, referred to as “Quantum Computing Functions”. Povzetek: Članek predstavlja implementacijo kvantnega iskanja v nestrukturiranih bazah.

Informatica•Jan 1, 2012•0 citations

Concurrent Quantum Computation

Fumiko Yamaguchi, Cyrus P. Master, Y. Yamamoto

A quantum computer is a multi-particle interferometer that comprises beam splitters at both ends and arms, where the n two-level particles undergo the interactions among them. The arms are designed so that relevant functions required to produce a computational result is stored in the phase shifts of the 2^n arms. They can be detected by interferometry that allows us to utilize quantum parallelism. Quantum algorithms are accountable for what interferometers to be constructed to compute particular problems. A standard formalism for constructing the arms has been developed by the extension of classical reversible gate arrays. By its nature of sequential applications of logic operations, the required number of gates increases exponentially as the problem size grows. This may cause a crucial obstacle to perform a quantum computation within a limited decoherence time. We propose a direct and concurrent construction of the interferometer arms by one-time evolution of a physical system with arbitrary multi-particle interactions. It is inherently quantum mechanical and has no classical analogue. Encoding the functions used in Shor's algorithm for prime factoring, Grover's algorithm and Deutsch-Jozsa algorithm requires only one-time evolution of such a system regardless of the problem size n as opposed to its standard sequential counterpart that takes O(n^3), O(n) and O(n2^n).

arXiv:quant-ph/0005128•May 31, 2000•5 citations

Classical Search and Quantum Search Algorithms for Synthesis of Quantum Circuits and Optimization of Quantum Oracles

Sazzad Hossain

We observe an enormous increase in the computational power of digital computers. This was due to the revolution in manufacturing processes and controlling semiconductor structures on submicron scale, ultimately leading to the control of individual atoms. Eventually, the classical electric circuits encountered the barrier of quantum mechanics and its effects. However, the laws of quantum mechanics can be also used to produce computational devices that lead to extraordinary speed increases over classical computers. Thus quantum computing becomes a very promising and attractive research area. The Computer Aided Design for Quantum circuits becomes an essential ingredient for such emerging research which may lead to these powerful computers to be realized—an era of Quantum computing. This thesis presents an integrated theoretical study of software algorithms to design circuits of quantum oracles as well as methods for designing quantum oracles for Grover algorithm to solve combinatorial problems. An implementation of quantum algorithm involves the initialization of the input state and its manipulation with quantum gates followed by the measurements. In Grover algorithm the problem to be solved is specified by a permutative logic oracle – the fundamental problem is then how to build this oracle from quantum logic circuits and how to optimize these circuits. These problems are NP-hard and require search algorithms. In future, the search will be also done in quantum and this thesis leads to quantum algorithms to design quantum circuits more efficiently.

•Jan 1, 2009•1 citation

Evolutionary Computation in Coded Communications: an Implementation of Viterbi Algorithm

Jamal S., Dia I., Mohammed Haw

Quantum Computing hopefully is the future of computing systems. It still on its first steps. The development of some quantum algorithms gives the quantum computing a boost on its importance. These algorithms (such as Shor’s and Grover’s algorithms) proved to have superior performance over classical algorithms [1-4]. The recent findings, that quantum error correction can be used, showed that the decoherence problem can be solved and hence the quantum computers can be realized [5-7]. The quantum algorithms are based on the use of special gates applied on one, two or more qubits (quantum bits). The classical computer uses different gates (NOT, AND, NAND, OR and XOR). Quantum gates are in many aspects different from classical gates where all gates must be reversible. This makes the quantum gates act as 2x2 transformation operators, where we have n input qubits and n output qubits. To understand the quantum bits and gates we describe the group of amplitudes that describes the state of a quantum register as a vector. A qubit with state 0 , which is

InTech eBooks•Oct 1, 2009•1 citation

Simulation of many-qubit quantum computation with matrix product states

Mari Carmen Bañuls, Román Orús, José Ignacio Latorre +2 more

Matrix product states provide a natural entanglement basis to represent a quantum register and operate quantum gates on it. This scheme can be materialized to simulate a quantum adiabatic algorithm solving hard instances of an $NP$-complete problem. Errors inherent to truncations of the exact action of interacting gates are controlled by the size of the matrices in the representation. The property of finding the right solution for an instance and the expected value of the energy (cost function) are found to be remarkably robust against these errors. As a symbolic example, we simulate the algorithm solving a 100-qubit hard instance, that is, finding the correct product state out of $\ensuremath{\sim}{10}^{30}$ possibilities. Accumulated statistics for up to $60$ qubits seem to point at a subexponential growth of the average minimum time to solve hard instances with highly truncated simulations of adiabatic quantum evolution.

arXiv:quant-ph/0503174•Physical Review A•Feb 24, 2006•41 citations
We propose a form of parallel computing on classical computers that is based on matrix product states. The virtual parallelization is accomplished by representing bits with matrices and by evolving these matrices from an initial product state that encodes multiple inputs. Matrix evolution follows from the sequential application of gates, as in a logical circuit. The action by classical probabilistic one-bit and deterministic two-bit gates such as NAND are implemented in terms of matrix operations and, as opposed to quantum computing, it is possible to copy bits. We present a way to explore this method of computation to solve search problems and count the number of solutions. We argue that if the classical computational cost of testing solutions (witnesses) requires less than O(n2) local two-bit gates acting on n bits, the search problem can be fully solved in subexponential time. Therefore, for this restricted type of search problem, the virtual parallelization scheme is faster than Grover's quantum algorithm.
Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.
In the classical model of a computer, the most fundamental building block, the bit, can only exist in one of two distinct states, a 0 or a 1. Computations are carried out by logic gates that act on these bits to produce other bits. Unless there is duplicate (parallel) hardware, only one problem instance (i.e. input data set) can be handled at a time. In this classical computing, increasing the number of bits increases the complexity of the problem and the time necessary to arrive at a solution. A quantum algorithm consists of a sequence of operations on a register, to transform it into a state which, when measured, yields the desired result with high probability. An n-bit quantum register can store an exponential amount of information. This paper aims at taking advantage of the superiority of quantum computing over classical computing to solve the problem of searching unstructured databases for a particular item or more than one item in good time. The general aim of this work is to establish the correctness and optimality of Grover’s quantum database search algorithm compared against classical database search methods in order to investigate the superiority or otherwise of quantum computing over classical computing. This is followed by a simulation of the algorithm using a classical computer, namely through functions that are present in MATLAB, referred to as “Quantum Computing Functions”. Povzetek: Članek predstavlja implementacijo kvantnega iskanja v nestrukturiranih bazah.
A quantum computer is a multi-particle interferometer that comprises beam splitters at both ends and arms, where the n two-level particles undergo the interactions among them. The arms are designed so that relevant functions required to produce a computational result is stored in the phase shifts of the 2^n arms. They can be detected by interferometry that allows us to utilize quantum parallelism. Quantum algorithms are accountable for what interferometers to be constructed to compute particular problems. A standard formalism for constructing the arms has been developed by the extension of classical reversible gate arrays. By its nature of sequential applications of logic operations, the required number of gates increases exponentially as the problem size grows. This may cause a crucial obstacle to perform a quantum computation within a limited decoherence time. We propose a direct and concurrent construction of the interferometer arms by one-time evolution of a physical system with arbitrary multi-particle interactions. It is inherently quantum mechanical and has no classical analogue. Encoding the functions used in Shor's algorithm for prime factoring, Grover's algorithm and Deutsch-Jozsa algorithm requires only one-time evolution of such a system regardless of the problem size n as opposed to its standard sequential counterpart that takes O(n^3), O(n) and O(n2^n).
We observe an enormous increase in the computational power of digital computers. This was due to the revolution in manufacturing processes and controlling semiconductor structures on submicron scale, ultimately leading to the control of individual atoms. Eventually, the classical electric circuits encountered the barrier of quantum mechanics and its effects. However, the laws of quantum mechanics can be also used to produce computational devices that lead to extraordinary speed increases over classical computers. Thus quantum computing becomes a very promising and attractive research area. The Computer Aided Design for Quantum circuits becomes an essential ingredient for such emerging research which may lead to these powerful computers to be realized—an era of Quantum computing. This thesis presents an integrated theoretical study of software algorithms to design circuits of quantum oracles as well as methods for designing quantum oracles for Grover algorithm to solve combinatorial problems. An implementation of quantum algorithm involves the initialization of the input state and its manipulation with quantum gates followed by the measurements. In Grover algorithm the problem to be solved is specified by a permutative logic oracle – the fundamental problem is then how to build this oracle from quantum logic circuits and how to optimize these circuits. These problems are NP-hard and require search algorithms. In future, the search will be also done in quantum and this thesis leads to quantum algorithms to design quantum circuits more efficiently.
Quantum Computing hopefully is the future of computing systems. It still on its first steps. The development of some quantum algorithms gives the quantum computing a boost on its importance. These algorithms (such as Shor’s and Grover’s algorithms) proved to have superior performance over classical algorithms [1-4]. The recent findings, that quantum error correction can be used, showed that the decoherence problem can be solved and hence the quantum computers can be realized [5-7]. The quantum algorithms are based on the use of special gates applied on one, two or more qubits (quantum bits). The classical computer uses different gates (NOT, AND, NAND, OR and XOR). Quantum gates are in many aspects different from classical gates where all gates must be reversible. This makes the quantum gates act as 2x2 transformation operators, where we have n input qubits and n output qubits. To understand the quantum bits and gates we describe the group of amplitudes that describes the state of a quantum register as a vector. A qubit with state 0 , which is
Matrix product states provide a natural entanglement basis to represent a quantum register and operate quantum gates on it. This scheme can be materialized to simulate a quantum adiabatic algorithm solving hard instances of an NPNPNP-complete problem. Errors inherent to truncations of the exact action of interacting gates are controlled by the size of the matrices in the representation. The property of finding the right solution for an instance and the expected value of the energy (cost function) are found to be remarkably robust against these errors. As a symbolic example, we simulate the algorithm solving a 100-qubit hard instance, that is, finding the correct product state out of $\ensuremath{\sim}{10}^{30}$ possibilities. Accumulated statistics for up to 606060 qubits seem to point at a subexponential growth of the average minimum time to solve hard instances with highly truncated simulations of adiabatic quantum evolution.