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

Computational and Mathematical Methods

Experiments testing the commutativity of finite-dimensional algebras with a quantum adiabatic algorithm

Elías F. Combarro, José Ranilla, I. F. Rúa

Published Jan 1, 2019• 5 citations
Publisher

Abstract

Determining whether a given algebra is commutative or not is important in the study of these algebraic objects in general and in the classification of semifields in particular. The best classical (ie, nonquantum) algorithm for this task has a running time that is of order O(n3), where n is the dimension of the algebra. To reduce this cost, in this paper, we study an approach to test the commutativity of a finite-dimensional algebra using quantum adiabatic computing. Previous quantum algorithms solving the same problem were based on Grover's quantum search. The algorithm is built from a quantum oracle for the multiplication constants of the algebra. Results of the experiments carried out on a quantum computer simulator, based on two different annealing schedules, are presented, showing that a quantum adiabatic algorithm for the problem can determine the commutativity of finite-dimensional algebras with one-side bounded error with a running time of order , achieving a quadratic speedup over the classical case.

DOI
10.1002/cmm4.1009

Related papers

A Quantum Algorithm for the Commutativity of Finite Dimensional Algebras

Elías F. Combarro, José Ranilla, I. F. Rúa

A quantum procedure for testing the commutativity of a finite dimensional algebra is introduced. This algorithm, based on Grover's quantum search, is shown to provide a quadratic speed-up (when the number of queries to the algebra multiplication constants is considered) over any classical algorithm (both deterministic and randomized) with equal success rate and shown to be optimal among the class of probabilistic quantum query algorithms. This algorithm can also be readily adapted to test commutativity and hermiticity of square matrices, again with quadratic speed-up. The results of the experiments carried out on a quantum computer simulator and on one of IBM's 5-qubit quantum computers are presented.

IEEE Access•Jan 1, 2019•9 citations

Quantum Computation and Isomorphism Testing

David J. Rosenbaum

In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.

•Jan 1, 2015•2 citations

Fixed-point adiabatic quantum search

Alexander M. Dalzell, Theodore J. Yoder, Isaac L. Chuang

Fixed-point quantum search algorithms succeed at finding one of $M$ target items among $N$ total items even when the run time of the algorithm is longer than necessary. While the famous Grover's algorithm can search quadratically faster than a classical computer, it lacks the fixed-point property---the fraction of target items must be known precisely to know when to terminate the algorithm. Recently, Yoder, Low, and Chuang [Phys. Rev. Lett. 113, 210501 (2014)] gave an optimal gate-model search algorithm with the fixed-point property. Previously, it had been discovered by Roland and Cerf [Phys. Rev. A 65, 042308 (2002)] that an adiabatic quantum algorithm, operating by continuously varying a Hamiltonian, can reproduce the quadratic speedup of gate-model Grover search. We ask, can an adiabatic algorithm also reproduce the fixed-point property? We show that the answer depends on what interpolation schedule is used, so as in the gate model, there are both fixed-point and non-fixed-point versions of adiabatic search, only some of which attain the quadratic quantum speedup. Guided by geometric intuition on the Bloch sphere, we rigorously justify our claims with an explicit upper bound on the error in the adiabatic approximation. We also show that the fixed-point adiabatic search algorithm can be simulated in the gate model with neither loss of the quadratic Grover speedup nor of the fixed-point property. Finally, we discuss natural uses of fixed-point algorithms such as preparation of a relatively prime state and oblivious amplitude amplification.

arXiv:1609.03603•Physical Review A•Jan 11, 2017•26 citations

Adiabatic quantum search algorithm for structured problems

Jérémie Roland, Nicolas J. Cerf

The study of quantum computation has been motivated by the hope of finding efficient quantum algorithms for solving classically hard problems. In this context, quantum algorithms by local adiabatic evolution have been shown to solve an unstructured search problem with a quadratic speedup over a classical search, just as Grover's algorithm. In this paper, we study how the structure of the search problem may be exploited to further improve the efficiency of these quantum adiabatic algorithms. We show that by nesting a partial search over a reduced set of variables into a global search, it is possible to devise quantum adiabatic algorithms with a complexity that, although still exponential, grows with a reduced order in the problem size.

arXiv:quant-ph/0304039•Physical Review A•Dec 15, 2003•31 citations

Quantum Algorithms and Complexity for Numerical Problems

Zhang, Chi

Quantum computing has attracted a lot of attention in different research fields, such as mathematics, physics and computer science. Quantum algorithms can solve certain problems significantly faster than classical algorithms. There are many numerical problems, especially those arising from quantum systems, which are notoriously difficult to solve using classical computers, since the computational time required often scales exponentially with the size of the problem. However, quantum computers have the potential to solve these problems efficiently, which is also one of the founding ideas of the field of quantum computing. In this thesis, we explore five computational problems, designing innovative quantum algorithms and studying their computational complexity. First, we design an adiabatic quantum algorithm based on the Berry phases for the counting problem. For the running time, it is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result should be robust to decoherence and resilient to certain kinds of noise. Since the counting problem is the foundation of many other numerical problems, such as high-dimensional integration and path integration, our adiabatic algorithms can be directly generalized to these kinds of problems. In addition, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. The lower bound is very close to the best lower bound on query complexity known for the classical PAC learning model. We also study the algorithms and the cost of simulating a system evolving under a given Hamiltonian. We consider high order splitting methods that are particularly applicable in quantum simulation and obtain bounds on the number of exponentials required. Moreover, we derive the optimal order of convergence given the required error bound. We compare our complexity estimates to previously known ones and show the resulting speedup. Furthermore, we consider randomized algorithms for Hamiltonian simulation. The evolution is simulated by a product of exponentials in a random sequence and random evolution times. Hence the final state of the system is approximated by a mixed quantum state. We provide a scheme to bound the error of the final quantum state in a randomized algorithm, and obtain randomized algorithms which have the same efficiency as certain deterministic algorithms but which are simpler to implement. We also apply Hamiltonian simulation in estimating the ground state energy of a multiparticle system, which is also known as the multivariate Sturm-Liouville eigenvalue problem. Since the cost of this problem grows exponentially with the number of particles using deterministic classical algorithms, it suffers from the curse of dimensionality. Quantum computers can vanquish the curse, and we exhibit a quantum algorithm whose total cost are linear in the number of particles.

•Jan 1, 2011•0 citations

Continuous-time Quantum Algorithms: Searching and Adiabatic Computation

Lawrence M. Ioannou

One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. \nSoon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi et. al. [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover's search algorithm can. \nI begin with a review of the discrete- and continuous-time models of quantum computation. I then make precise the notion of "efficient quantum algorithms", motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms. After reviewing three quantum search algorithms [F00,FG96,G96], I develop the adiabatic 3SAT algorithm as a natural extension of Farhi and Gutmann's search algorithm. Along the way, I present the adiabatic search algorithm [vDMV01] and remark on its discrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework. \nUPDATE (February 2003): Please see article http://arxiv. org/abs/quant-ph/0302138 for a resolution to the problem of simulating the continuous-time adiabatic search algorithm with a quantum circuit using only O(sqrt(N)) resources.

•Jan 1, 2002•4 citations
Determining whether a given algebra is commutative or not is important in the study of these algebraic objects in general and in the classification of semifields in particular. The best classical (ie, nonquantum) algorithm for this task has a running time that is of order O(n3), where n is the dimension of the algebra. To reduce this cost, in this paper, we study an approach to test the commutativity of a finite-dimensional algebra using quantum adiabatic computing. Previous quantum algorithms solving the same problem were based on Grover's quantum search. The algorithm is built from a quantum oracle for the multiplication constants of the algebra. Results of the experiments carried out on a quantum computer simulator, based on two different annealing schedules, are presented, showing that a quantum adiabatic algorithm for the problem can determine the commutativity of finite-dimensional algebras with one-side bounded error with a running time of order , achieving a quadratic speedup over the classical case.
A quantum procedure for testing the commutativity of a finite dimensional algebra is introduced. This algorithm, based on Grover's quantum search, is shown to provide a quadratic speed-up (when the number of queries to the algebra multiplication constants is considered) over any classical algorithm (both deterministic and randomized) with equal success rate and shown to be optimal among the class of probabilistic quantum query algorithms. This algorithm can also be readily adapted to test commutativity and hermiticity of square matrices, again with quadratic speed-up. The results of the experiments carried out on a quantum computer simulator and on one of IBM's 5-qubit quantum computers are presented.
In this thesis, we study quantum computation and algorithms for isomorphism problems. Some of the problems that we cover are fundamentally quantum and therefore require quantum techniques. For other problems, classical approaches are more appropriate; however, we often give quantum variants of our classical algorithms as well. The field of quantum computation aims to accelerate algorithms by exploiting the laws of quantum mechanics. Several quantum algorithms are known that are exponentially faster than the best classical algorithms known for the same problems, including several which are relevant to cryptography. Quantum computing is therefore of great importance. On the theory side, it has already transformed our notions of which problems are tractable and which are not. On the practical side, the construction of a quantum computer would render many popular techniques for encryption obsolete. We derive several results in quantum computation. Quantum algorithms are normally formulated in an abstract way that ignores practical details such as where different parts of the computation are located physically. Using naive methods for translating these algorithms into practical quantum computing technologies increases the time complexity by a linear factor, while previous work reduced this factor to a square root. We further reduce this factor to a constant at the cost of requiring additional space. This retroactively justifies an important assumption made in many quantum algorithms. Another interesting problem is to determine the query complexity of extracting different types of information from physical processes. In the case of deterministic processes, it is well known that quantum algorithms cannot outperform deterministic algorithms by more than an exponential factor. We show --- somewhat surprisingly --- that when the process is allowed to be randomized, there are problems that have a constant quantum query complexity but cannot be solved classically no matter how many queries are made. In fact, we show how to construct such an infinity-vs-one separation from any weaker separation between the classical and quantum query complexities. In an isomorphism problem, we seek to determine if two algebraic or combinatorial objects have the same structure. One of the most well-known of these is the graph isomorphism problem, which is interesting since it is suspected to be of complexity intermediate between P and the NP-complete problems. We transition from quantum computation to isomorphism testing by considering the tree isomorphism problem. While linear-time classical algorithms are known for this problem, we show that a promising framework for developing efficient quantum algorithms for graph isomorphism, known as the state preparation approach, can also solve tree isomorphism. While this result might seem modest, it is important to know that the state preparation approach works for trees, since otherwise there would be little hope of using it to obtain efficient algorithms for more interesting classes of graphs. We also derive a powerful primitive along the way that is of independent interest. Next, we study the group isomorphism problem, which is a special case of graph isomorphism. Group isomorphism is suspected to be significantly easier than graph isomorphism, but still has unknown complexity. While group isomorphism is already of interest since it is a fundamental computational question about groups, searching for faster algorithms for group isomorphism is therefore also one way of approaching the graph isomorphism problem. We use collision detection methods to give a classical algorithm that obtains a square-root speedup over the best algorithm previously known for the general group isomorphism problem. For the solvable groups (which are conjectured to be difficult and contain almost all groups), we combine our collision detection techniques with group-theoretic methods to obtain a classical fourth-root speedup over the best algorithm known previously. Prior to this work, it was a longstanding open problem to obtain any improvement for either of these classes of groups. Finally, we give a general framework that yields speedups for many isomorphism problems. In particular, it yields the square-root speedup for testing isomorphism of general groups mentioned above. All of our group isomorphism-testing algorithms also have quantum variants that are slightly faster than their classical counterparts.
Fixed-point quantum search algorithms succeed at finding one of MMM target items among NNN total items even when the run time of the algorithm is longer than necessary. While the famous Grover's algorithm can search quadratically faster than a classical computer, it lacks the fixed-point property---the fraction of target items must be known precisely to know when to terminate the algorithm. Recently, Yoder, Low, and Chuang [Phys. Rev. Lett. 113, 210501 (2014)] gave an optimal gate-model search algorithm with the fixed-point property. Previously, it had been discovered by Roland and Cerf [Phys. Rev. A 65, 042308 (2002)] that an adiabatic quantum algorithm, operating by continuously varying a Hamiltonian, can reproduce the quadratic speedup of gate-model Grover search. We ask, can an adiabatic algorithm also reproduce the fixed-point property? We show that the answer depends on what interpolation schedule is used, so as in the gate model, there are both fixed-point and non-fixed-point versions of adiabatic search, only some of which attain the quadratic quantum speedup. Guided by geometric intuition on the Bloch sphere, we rigorously justify our claims with an explicit upper bound on the error in the adiabatic approximation. We also show that the fixed-point adiabatic search algorithm can be simulated in the gate model with neither loss of the quadratic Grover speedup nor of the fixed-point property. Finally, we discuss natural uses of fixed-point algorithms such as preparation of a relatively prime state and oblivious amplitude amplification.
The study of quantum computation has been motivated by the hope of finding efficient quantum algorithms for solving classically hard problems. In this context, quantum algorithms by local adiabatic evolution have been shown to solve an unstructured search problem with a quadratic speedup over a classical search, just as Grover's algorithm. In this paper, we study how the structure of the search problem may be exploited to further improve the efficiency of these quantum adiabatic algorithms. We show that by nesting a partial search over a reduced set of variables into a global search, it is possible to devise quantum adiabatic algorithms with a complexity that, although still exponential, grows with a reduced order in the problem size.
Quantum computing has attracted a lot of attention in different research fields, such as mathematics, physics and computer science. Quantum algorithms can solve certain problems significantly faster than classical algorithms. There are many numerical problems, especially those arising from quantum systems, which are notoriously difficult to solve using classical computers, since the computational time required often scales exponentially with the size of the problem. However, quantum computers have the potential to solve these problems efficiently, which is also one of the founding ideas of the field of quantum computing. In this thesis, we explore five computational problems, designing innovative quantum algorithms and studying their computational complexity. First, we design an adiabatic quantum algorithm based on the Berry phases for the counting problem. For the running time, it is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result should be robust to decoherence and resilient to certain kinds of noise. Since the counting problem is the foundation of many other numerical problems, such as high-dimensional integration and path integration, our adiabatic algorithms can be directly generalized to these kinds of problems. In addition, we study the quantum PAC learning model, offering an improved lower bound on the query complexity. The lower bound is very close to the best lower bound on query complexity known for the classical PAC learning model. We also study the algorithms and the cost of simulating a system evolving under a given Hamiltonian. We consider high order splitting methods that are particularly applicable in quantum simulation and obtain bounds on the number of exponentials required. Moreover, we derive the optimal order of convergence given the required error bound. We compare our complexity estimates to previously known ones and show the resulting speedup. Furthermore, we consider randomized algorithms for Hamiltonian simulation. The evolution is simulated by a product of exponentials in a random sequence and random evolution times. Hence the final state of the system is approximated by a mixed quantum state. We provide a scheme to bound the error of the final quantum state in a randomized algorithm, and obtain randomized algorithms which have the same efficiency as certain deterministic algorithms but which are simpler to implement. We also apply Hamiltonian simulation in estimating the ground state energy of a multiparticle system, which is also known as the multivariate Sturm-Liouville eigenvalue problem. Since the cost of this problem grows exponentially with the number of particles using deterministic classical algorithms, it suffers from the curse of dimensionality. Quantum computers can vanquish the curse, and we exhibit a quantum algorithm whose total cost are linear in the number of particles.
One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. \nSoon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi et. al. [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover's search algorithm can. \nI begin with a review of the discrete- and continuous-time models of quantum computation. I then make precise the notion of "efficient quantum algorithms", motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms. After reviewing three quantum search algorithms [F00,FG96,G96], I develop the adiabatic 3SAT algorithm as a natural extension of Farhi and Gutmann's search algorithm. Along the way, I present the adiabatic search algorithm [vDMV01] and remark on its discrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework. \nUPDATE (February 2003): Please see article http://arxiv. org/abs/quant-ph/0302138 for a resolution to the problem of simulating the continuous-time adiabatic search algorithm with a quantum circuit using only O(sqrt(N)) resources.