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:2504.10771 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Simon's Period Finding on a Quantum Annealer

Reece Robertson, Emery Doucet, Zakaria Mzaouali, Krzysztof Domino, Bartłomiej Gardas, Sebastian Deffner

Published Aug 30, 2025• 2 citations
arXivHTMLPDF

Abstract

Dating to 1994, Simon's period-finding algorithm is among the earliest and most fragile of quantum algorithms. The algorithm's fragility arises from the requirement that, to solve an$n$-qubit problem, one must fault-tolerantly sample$O(n)$linearly independent values from a solution space. In this paper, we study an adiabatic implementation of Simon's algorithm that requires a constant number of successful samples regardless of problem size. We implement this algorithm on D-Wave hardware and solve problems with up to 298 qubits. We compare the runtime of classical algorithms to the D-Wave solution to analyze any potential advantage.

DOI
10.1109/qce65121.2025.00030

Related papers

Experimental Realization of a One-Way Quantum Computer Algorithm Solving Simon’s Problem

Mark Tame, Bryn A. Bell, Carlo D. Franco +2 more

We report an experimental demonstration of a one-way implementation of a quantum algorithm solving Simon's problem-a black-box period-finding problem that has an exponential gap between the classical and quantum runtime. Using an all-optical setup and modifying the bases of single-qubit measurements on a five-qubit cluster state, key representative functions of the logical two-qubit version's black box can be queried and solved. To the best of our knowledge, this work represents the first experimental realization of the quantum algorithm solving Simon's problem. The experimental results are in excellent agreement with the theoretical model, demonstrating the successful performance of the algorithm. With a view to scaling up to larger numbers of qubits, we analyze the resource requirements for an n-qubit version. This work helps highlight how one-way quantum computing provides a practical route to experimentally investigating the quantum-classical gap in the query complexity model.

arXiv:1410.3859•Physical Review Letters•Nov 11, 2014•33 citations

On Relaxation of Simon's Algorithm

Ali Khosravi, Taraneh Eghlidos

Simon's algorithm is one of the most widely used quantum algorithms in cryptanalysis of symmetric ciphers, which has a significant advantage over its classical counterparts. However, if the number of unwanted collisions of the target function is large or if the number of adversary's quantum superposition queries is limited, the Simon's algorithm is not able to unambiguously compute the actual period. This problem can lead to the failure of period-finding-based quantum attacks. In this paper we first show that using Simon's algorithm, one can find proper partial periods of Boolean vector functions, such that the corresponding probabilities, independent of the target function, are directly related to the number of quantum queries. Next, we examine how to use the partial period instead of actual one in quantum period-finding-based attacks. As a result, the advantage of our proposed relaxing method is twofold: It improves success probabilities of quantum period-finding-based distinguishers, provided that the adversary is limited to a specified small number of queries, in contrast to the previous ones. On the other hand, our proposed method generalizes the previous forgery attacks on modes of operation for message authentication codes.

International ISC Conference on Information Security and Cryptology (ISCISC)•Sep 1, 2021•1 citation

Simon’s Algorithm in the NISQ Cloud

Reece Robertson, Emery Doucet, Ernest Spicer +1 more

Simon's algorithm was one of the first to demonstrate a genuine quantum advantage in solving a problem. The algorithm, however, assumes access to fault-tolerant qubits. In our work, we use Simon's algorithm to benchmark the error rates of devices currently available in the "quantum cloud". As a main result, we objectively compare the different physical platforms made available by IBM and IonQ. Our study highlights the importance of understanding the device architectures and topologies when transpiling quantum algorithms onto hardware. For instance, we demonstrate that two-qubit operations on spatially separated qubits on superconducting chips should be avoided.

arXiv:2406.11771•Entropy•Jun 20, 2025•3 citations

Optimal solving of a scheduling problem using quantum annealing metaheuristics on the D-Wave quantum solver

Wojciech Bożejko, Ryszard Klempous, Jarosław Pempera +4 more

This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. The main disadvantage of calculations on quantum computers is their non-determinism. For optimization problems, of course, it is possible to get surprisingly good results but without a guarantee of the actual optimality of the result, i.e, an assurance that there exists no better solution which could potentially be found by the quantum machine. In this paper, we propose an novel approach that provides such a guarantee of optimality. We generate a solution that is optimal in the strict mathematical sense, without probabilistic considerations. To accomplish this, we use the D-Wave quantum machine working as a sampler implementing quantum annealing -- an approach considered a hardware metaheuristic -- to obtain upper and lower bounds on the value of the objective function of the problem under consideration. Then, we use the Branch and Bound scheme controlled by quantum annealing. This allows us to obtain very quickly -- in constant time -- the boundaries of the considered subproblems. Our approach is a combination of calculations realized on a quantum machine controlled by procedures implemented on a classical computer, allowing us to generate optimal solutions to the NP-hard problems of task scheduling on a single machine with a total weighted tardiness criterion. The proposed quantum algorithm shows a significant advantage over the classical CPU approach both in terms of calculation time and the number of generated solution tree nodes.

•Apr 26, 2023•0 citations

Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer

Immanuel Trummer, Christoph E. Koch

The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA Ames Research Center in California, to explore the potential for hard optimization problems that arise in the context of databases. In this paper, we tackle the problem of multiple query optimization (MQO). We show how an MQO problem instance can be transformed into a mathematical formula that complies with the restrictive input format accepted by the quantum annealer. This formula is translated into weights on and between qubits such that the configuration minimizing the input formula can be found via a process called adiabatic quantum annealing. We analyze the asymptotic growth rate of the number of required qubits in the MQO problem dimensions as the number of qubits is currently the main factor restricting applicability. We experimentally compare the performance of the quantum annealer against other MQO algorithms executed on a traditional computer. While the problem sizes that can be treated are currently limited, we already find a class of problem instances where the quantum annealer is three orders of magnitude faster than other approaches.

arXiv:1510.06437•Oct 21, 2015•8 citations

Multiple query optimization on the D-Wave 2X adiabatic quantum computer

Immanuel Trummer, Christoph E. Koch

The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA Ames Research Center in California, to explore the potential for hard optimization problems that arise in the context of databases. In this paper, we tackle the problem of multiple query optimization (MQO). We show how an MQO problem instance can be transformed into a mathematical formula that complies with the restrictive input format accepted by the quantum annealer. This formula is translated into weights on and between qubits such that the configuration minimizing the input formula can be found via a process called adiabatic quantum annealing. We analyze the asymptotic growth rate of the number of required qubits in the MQO problem dimensions as the number of qubits is currently the main factor restricting applicability. We experimentally compare the performance of the quantum annealer against other MQO algorithms executed on a traditional computer. While the problem sizes that can be treated are currently limited, we already find a class of problem instances where the quantum annealer is three orders of magnitude faster than other approaches.

Proceedings of the VLDB Endowment•May 1, 2016•75 citations
Dating to 1994, Simon's period-finding algorithm is among the earliest and most fragile of quantum algorithms. The algorithm's fragility arises from the requirement that, to solve annnn-qubit problem, one must fault-tolerantly sampleO(n)O(n)O(n)linearly independent values from a solution space. In this paper, we study an adiabatic implementation of Simon's algorithm that requires a constant number of successful samples regardless of problem size. We implement this algorithm on D-Wave hardware and solve problems with up to 298 qubits. We compare the runtime of classical algorithms to the D-Wave solution to analyze any potential advantage.
We report an experimental demonstration of a one-way implementation of a quantum algorithm solving Simon's problem-a black-box period-finding problem that has an exponential gap between the classical and quantum runtime. Using an all-optical setup and modifying the bases of single-qubit measurements on a five-qubit cluster state, key representative functions of the logical two-qubit version's black box can be queried and solved. To the best of our knowledge, this work represents the first experimental realization of the quantum algorithm solving Simon's problem. The experimental results are in excellent agreement with the theoretical model, demonstrating the successful performance of the algorithm. With a view to scaling up to larger numbers of qubits, we analyze the resource requirements for an n-qubit version. This work helps highlight how one-way quantum computing provides a practical route to experimentally investigating the quantum-classical gap in the query complexity model.
Simon's algorithm is one of the most widely used quantum algorithms in cryptanalysis of symmetric ciphers, which has a significant advantage over its classical counterparts. However, if the number of unwanted collisions of the target function is large or if the number of adversary's quantum superposition queries is limited, the Simon's algorithm is not able to unambiguously compute the actual period. This problem can lead to the failure of period-finding-based quantum attacks. In this paper we first show that using Simon's algorithm, one can find proper partial periods of Boolean vector functions, such that the corresponding probabilities, independent of the target function, are directly related to the number of quantum queries. Next, we examine how to use the partial period instead of actual one in quantum period-finding-based attacks. As a result, the advantage of our proposed relaxing method is twofold: It improves success probabilities of quantum period-finding-based distinguishers, provided that the adversary is limited to a specified small number of queries, in contrast to the previous ones. On the other hand, our proposed method generalizes the previous forgery attacks on modes of operation for message authentication codes.
Simon's algorithm was one of the first to demonstrate a genuine quantum advantage in solving a problem. The algorithm, however, assumes access to fault-tolerant qubits. In our work, we use Simon's algorithm to benchmark the error rates of devices currently available in the "quantum cloud". As a main result, we objectively compare the different physical platforms made available by IBM and IonQ. Our study highlights the importance of understanding the device architectures and topologies when transpiling quantum algorithms onto hardware. For instance, we demonstrate that two-qubit operations on spatially separated qubits on superconducting chips should be avoided.
This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. The main disadvantage of calculations on quantum computers is their non-determinism. For optimization problems, of course, it is possible to get surprisingly good results but without a guarantee of the actual optimality of the result, i.e, an assurance that there exists no better solution which could potentially be found by the quantum machine. In this paper, we propose an novel approach that provides such a guarantee of optimality. We generate a solution that is optimal in the strict mathematical sense, without probabilistic considerations. To accomplish this, we use the D-Wave quantum machine working as a sampler implementing quantum annealing -- an approach considered a hardware metaheuristic -- to obtain upper and lower bounds on the value of the objective function of the problem under consideration. Then, we use the Branch and Bound scheme controlled by quantum annealing. This allows us to obtain very quickly -- in constant time -- the boundaries of the considered subproblems. Our approach is a combination of calculations realized on a quantum machine controlled by procedures implemented on a classical computer, allowing us to generate optimal solutions to the NP-hard problems of task scheduling on a single machine with a total weighted tardiness criterion. The proposed quantum algorithm shows a significant advantage over the classical CPU approach both in terms of calculation time and the number of generated solution tree nodes.
The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA Ames Research Center in California, to explore the potential for hard optimization problems that arise in the context of databases. In this paper, we tackle the problem of multiple query optimization (MQO). We show how an MQO problem instance can be transformed into a mathematical formula that complies with the restrictive input format accepted by the quantum annealer. This formula is translated into weights on and between qubits such that the configuration minimizing the input formula can be found via a process called adiabatic quantum annealing. We analyze the asymptotic growth rate of the number of required qubits in the MQO problem dimensions as the number of qubits is currently the main factor restricting applicability. We experimentally compare the performance of the quantum annealer against other MQO algorithms executed on a traditional computer. While the problem sizes that can be treated are currently limited, we already find a class of problem instances where the quantum annealer is three orders of magnitude faster than other approaches.
The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA Ames Research Center in California, to explore the potential for hard optimization problems that arise in the context of databases. In this paper, we tackle the problem of multiple query optimization (MQO). We show how an MQO problem instance can be transformed into a mathematical formula that complies with the restrictive input format accepted by the quantum annealer. This formula is translated into weights on and between qubits such that the configuration minimizing the input formula can be found via a process called adiabatic quantum annealing. We analyze the asymptotic growth rate of the number of required qubits in the MQO problem dimensions as the number of qubits is currently the main factor restricting applicability. We experimentally compare the performance of the quantum annealer against other MQO algorithms executed on a traditional computer. While the problem sizes that can be treated are currently limited, we already find a class of problem instances where the quantum annealer is three orders of magnitude faster than other approaches.