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• 4 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•35 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•10 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•Proceedings of the VLDB Endowment•May 1, 2016•96 citations

NMR realization of adiabatic quantum algorithms for the modified Simon problem

Long Yu, Guanru Feng, Yongchao Tang +2 more

Having the advantages of inherent robustness and fault tolerance, adiabatic quantum algorithms have attracted much attention in recent years. In this paper, we report the NMR experimental realization of adiabatic algorithms for the modified Simon's problem in a NMR quantum information processor. We first realized an adiabatic quantum algorithm by Rao [Phys. Rev. A 67, 052306 (2003)] and then proposed a quantum algorithm by using the method of enhanced symmetry of the Hamiltonian given in Schaller and Schtzhold [Quantum Inf. Comput. 10, 109 (2010)]. We demonstrated this symmetry-enhanced algorithm in experiment. We studied the effects of the number of Trotter evolution steps on the validity of adiabatic evolution and decoherence. In practical applications, a trade-off between pulse imperfection and adiabatic requirement must be made in the Trotter evolution step number. An optimal evolution step number and run time were indicated by our results. The experimental demonstration also showed that the symmetry-enhanced algorithm gave a better performance.

Physical Review A•Jul 9, 2013•11 citations

Period finding with adiabatic quantum computation

Itay Hen

We outline an efficient quantum-adiabatic algorithm that solves Simon's problem, in which one has to determine the `period', or xor-mask, of a given black-box function. We show that the proposed algorithm is exponentially faster than its classical counterpart and has the same complexity as the corresponding circuit-based algorithm. Together with other related studies, this result supports a conjecture that the complexity of adiabatic quantum computation is equivalent to the circuit-based computational model in a stronger sense than the well-known, proven polynomial equivalence between the two paradigms. We also discuss the importance of the algorithm and its theoretical and experimental implications for the existence of an adiabatic version of Shor's integer factorization algorithm that would have the same complexity as the original algorithm.

arXiv:1307.6538•Europhysics Letters (EPL)•Mar 1, 2014•29 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.
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.
Having the advantages of inherent robustness and fault tolerance, adiabatic quantum algorithms have attracted much attention in recent years. In this paper, we report the NMR experimental realization of adiabatic algorithms for the modified Simon's problem in a NMR quantum information processor. We first realized an adiabatic quantum algorithm by Rao [Phys. Rev. A 67, 052306 (2003)] and then proposed a quantum algorithm by using the method of enhanced symmetry of the Hamiltonian given in Schaller and Schtzhold [Quantum Inf. Comput. 10, 109 (2010)]. We demonstrated this symmetry-enhanced algorithm in experiment. We studied the effects of the number of Trotter evolution steps on the validity of adiabatic evolution and decoherence. In practical applications, a trade-off between pulse imperfection and adiabatic requirement must be made in the Trotter evolution step number. An optimal evolution step number and run time were indicated by our results. The experimental demonstration also showed that the symmetry-enhanced algorithm gave a better performance.
We outline an efficient quantum-adiabatic algorithm that solves Simon's problem, in which one has to determine the `period', or xor-mask, of a given black-box function. We show that the proposed algorithm is exponentially faster than its classical counterpart and has the same complexity as the corresponding circuit-based algorithm. Together with other related studies, this result supports a conjecture that the complexity of adiabatic quantum computation is equivalent to the circuit-based computational model in a stronger sense than the well-known, proven polynomial equivalence between the two paradigms. We also discuss the importance of the algorithm and its theoretical and experimental implications for the existence of an adiabatic version of Shor's integer factorization algorithm that would have the same complexity as the original algorithm.