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:2301.06706

Feasibility Analysis of Grover-meets-Simon Algorithm

Qianru Zhu, Huiqin Xie, Qiqing Xia, Li Yang

Published Jan 17, 2023• 1 citation
arXivHTMLPDF

Abstract

Quantum algorithm is a key tool for cryptanalysis. At present, people are committed to building powerful quantum algorithms and tapping the potential of quantum algorithms, so as to further analyze the security of cryptographic algorithms under quantum computing. Recombining classical quantum algorithms is one of the current ideas to construct quantum algorithms. However, they cannot be easily combined, the feasibility of quantum algorithms needs further analysis in quantum environment. This paper reanalyzes the existing combined algorithm Grover-meets-Simon algorithm in terms of the principle of deferred measurement. First of all, due to the collapse problem caused by the measurement, we negate the measurement process of Simon's algorithm during the process of the Grover-meets-Simon algorithm. Second, since the output of the unmeasured Simon algorithm is quantum linear systems of equations, we discuss the solution of quantum linear systems of equations and find it feasible to consider the deferred measurement of the parallel Simon algorithm alone. Finally, since the Grover-meets-Simon algorithm involves an iterative problem, we reconsider the feasibility of the algorithm when placing multiple measurements at the end. According to the maximum probability of success and query times, we get that the Grover-meets-Simon algorithm is not an effective attack algorithm when putting the measurement process of the Simon algorithm in the iterative process at the end of Grover-meets-Simon algorithm.

DOI
10.48550/arxiv.2301.06706

Related papers

Tight Analysis of Grover-Meets-Simon and Alg-PolyQ2 Attacks via Formalizing Quantum Rank-Solving under Deferred Measurement

Qiqing Xia, Qianru Zhu, Huiqin Xie +1 more

Abstract The combination of quantum algorithms is one promising approach to attacking symmetric cryptography. In this paper, we study in detail the Grover-meets-Simon and Alg-PolyQ2 algorithms under deferred measurement, which combine the ideas of Grover’s and Simon’s algorithms and are applicable to attacking the FX construction. By converting intermediate measurements into unitary operations deferred to the end of the quantum circuit, both quantum algorithms involve a quantum rank-solving problem. To address it, we first provide a formal analysis of the generalized quantum Gauss–Jordan elimination and characterize the resulting quantum state after the corresponding unitary operations, which serves as a subroutine in these two algorithms. Subsequently, we derive the tight bounds of the attack success probability of these two algorithms based on the initial amplitude, offering a novel perspective that confirms their effectiveness. Furthermore, our research perspective provides an idea for analyzing the attack success probability for some quantum algorithms integrating Grover’s algorithm without considering quantum input length, and contributes to a deeper understanding of these attacks’ underlying mechanisms under the deferred measurement principle.

Quantum Information and Computation•Dec 1, 2025•0 citations

Quantum Related-Key Attack Based on Simon’s Algorithm and Its Applications

Ping Zhang

With the development of quantum technology, quantum computing has an increasingly significant impact on cryptanalysis. Several quantum algorithms, such as Simon’s algorithm, Grover’s algorithm, the Bernstein–Vazirani algorithm, Shor’s algorithm, and the Grover-meets-Simon algorithm, have been proposed successively. However, almost all cryptanalysis is based on the quantum chosen-plaintext attack (qCPA) model. This paper focuses on a powerful cryptanalytic model, quantum related-key attack (qRKA), and proposes a strategy of qRKAs against symmetric ciphers using Simon’s algorithm. We construct a periodic function to efficiently recover the secret key of symmetric ciphers if the attacked symmetric ciphers satisfy Simon’s promise, and present the complexity analysis on specific symmetric ciphers. Then, we apply qRKA to the Even–Mansour cipher and SoEM construction, recover their secret keys, and show their complexity comparison in the distinct attack models. This work is of great significance for the qRKA cryptanalysis of existing provably secure cryptographic schemes and the design of future quantum secure cryptographic schemes.

Symmetry•Apr 24, 2023•6 citations

Algorithm for solving quantum linear systems of equations with coherent superposition and extended applications

Qiqing Xia, Qianru Zhu, Huiqin Xie +1 more

Abstract Many quantum algorithms for attacking symmetric cryptography involve the rank problem of quantum linear equations. In this paper, two quantum algorithms are proposed to solve quantum linear systems of equations with coherent superposition, and their specific quantum circuits are constructed. In contrast to previous related studies, our quantum algorithms are universal, computing both the rank and general solution by one measurement. The difference between them is whether the data register containing the quantum coefficient matrix can be disentangled from the other registers while keeping the data qubits unchanged. On this basis, the two quantum algorithms are applied as subroutines to parallel Simon’s algorithm (with multiple periods), Grover Meets Simon algorithm, and Alg-PolyQ2 algorithm. Subsequently, a quantum classifier within Grover Meets Simon algorithm and a detailed test oracle within Alg-PolyQ2 algorithms are constructed, including their respective quantum circuits. To the best of our knowledge, no such specific analysis has been previously performed. The success probability of these algorithms is rigorously analyzed to ensure that the probability of success on the proposed quantum algorithms will not be lower than that of the original algorithms. Finally, we discuss the lower bound of the number of controlled-NOT gates for solving quantum linear systems of equations with coherent superposition. Our analysis indicates that the proposed algorithms are suitable for conducting attacks against lightweight symmetric ciphers within the effective working time of an ion-trap quantum computer.

arXiv:2405.06888•The Computer Journal•Dec 11, 2024•1 citation

General method of combining Grover and Simon for attacking block ciphers

Xiang-Qun Fu, Bao Wansu, Shi Jianhong +1 more

The compatibility of different quantum algorithms should be considered when these algorithms are combined. In this paper, the method of combining Grover and Simon is studied for the first time, under some preconditions or assumptions. First, we give two preconditions of applying Grover's algorithm, which ensure that the success probability of finding the marked element is close to 1. Then, based on these two preconditions, it is found out that the success probability of the quantum algorithm for FX-construction is far less than 1. Furthermore, we give the design method of the Oracle function, and then present the general method of combining Grover and Simon algorithm for attacking block ciphers, with success probability close to 1.

China Communications•Apr 9, 2024•1 citation

Quantum Cryptanalysis: Breaking Classical Encryption with Shor's and Grover's Algorithms

Godwin Olaoye

The advent of quantum computing presents a paradigm shift in the field of cryptanalysis, challenging the security of classical encryption schemes that underpin modern digital communications. This study explores the capabilities of quantum algorithms, particularly Shor's algorithm and Grover's algorithm, in undermining widely used cryptographic systems. Shor's algorithm poses a direct threat to publickey cryptosystems such as RSA and ECC by enabling efficient integer factorization and discrete logarithm computation, which are computationally infeasible for classical computers. Meanwhile, Grover's algorithm provides a quadratic speedup for bruteforce attacks on symmetric-key cryptosystems like AES, significantly reducing their effective security. Through theoretical analysis and simulation-based evaluation, this paper highlights the vulnerabilities of classical encryption in the face of quantum advances and underscores the urgent need for post-quantum cryptographic solutions. The findings emphasize the critical importance of transitioning to quantum-resistant algorithms to ensure long-term data confidentiality in a future dominated by quantum technologies.

•Apr 10, 2025•4 citations

Comparative Study of Quantum Algorithms: A Comprehensive Analysis

Neha Junagade, Sheetal Umesh Bhandari, Rachana Y Patil

Quantum computing is a rapidly growing field. Quantum algorithms play a significant role and have applications in cryptography, machine learning, optimization, and computational issues [1][2]. They quantum features like entanglement and superposition that help carryout tasks that would be difficult for a classical computer. More Interest has been developed in Quantum algorithms due to their ability to solve specific computational problems quicker than that in classical algorithms [3]. These algorithms use fundamentals of quantum physics to carryout calculations quickly and effectively than traditional algorithms. Here in-depth analysis of quantum algorithms and classical algorithms is done by looking at the time and space complexity of quantum and classical algorithms including their capacity to tackle specific types of issues.First, we conduct a general comparison of Classical and Quantum Algorithm along with Background and motivation. We also discuss Simon's algorithm first and then Grover's algorithm in depth and their comparison with few other algorithms in a table format [5][6][7][8]. We also cover some recent advancements, Quantum supremacy, Post-Quantum Cryptography, 8 Quantum Artificial Intelligence, Hybrid Quantum-Classical Algorithms and few other important parameters. We also discuss the plausible impact of quantum algorithms on cybersecurity and cryptography [13][9]. Overall, this comparative study shows the uses and challenges involved in implementing quantum algorithms while offering an overview of quantum algorithms. We conclude by the fundamental ideas of quantum algorithms. Adding to this we also discuss the challenges and limitations of using quantum algorithms in practically. At the end, we provide a summary of the primary findings from this comparative study of Quantum and classical algorithms.

International Conference on Computing Communication Control and automation•Aug 23, 2024•1 citation
Quantum algorithm is a key tool for cryptanalysis. At present, people are committed to building powerful quantum algorithms and tapping the potential of quantum algorithms, so as to further analyze the security of cryptographic algorithms under quantum computing. Recombining classical quantum algorithms is one of the current ideas to construct quantum algorithms. However, they cannot be easily combined, the feasibility of quantum algorithms needs further analysis in quantum environment. This paper reanalyzes the existing combined algorithm Grover-meets-Simon algorithm in terms of the principle of deferred measurement. First of all, due to the collapse problem caused by the measurement, we negate the measurement process of Simon's algorithm during the process of the Grover-meets-Simon algorithm. Second, since the output of the unmeasured Simon algorithm is quantum linear systems of equations, we discuss the solution of quantum linear systems of equations and find it feasible to consider the deferred measurement of the parallel Simon algorithm alone. Finally, since the Grover-meets-Simon algorithm involves an iterative problem, we reconsider the feasibility of the algorithm when placing multiple measurements at the end. According to the maximum probability of success and query times, we get that the Grover-meets-Simon algorithm is not an effective attack algorithm when putting the measurement process of the Simon algorithm in the iterative process at the end of Grover-meets-Simon algorithm.
Abstract The combination of quantum algorithms is one promising approach to attacking symmetric cryptography. In this paper, we study in detail the Grover-meets-Simon and Alg-PolyQ2 algorithms under deferred measurement, which combine the ideas of Grover’s and Simon’s algorithms and are applicable to attacking the FX construction. By converting intermediate measurements into unitary operations deferred to the end of the quantum circuit, both quantum algorithms involve a quantum rank-solving problem. To address it, we first provide a formal analysis of the generalized quantum Gauss–Jordan elimination and characterize the resulting quantum state after the corresponding unitary operations, which serves as a subroutine in these two algorithms. Subsequently, we derive the tight bounds of the attack success probability of these two algorithms based on the initial amplitude, offering a novel perspective that confirms their effectiveness. Furthermore, our research perspective provides an idea for analyzing the attack success probability for some quantum algorithms integrating Grover’s algorithm without considering quantum input length, and contributes to a deeper understanding of these attacks’ underlying mechanisms under the deferred measurement principle.
With the development of quantum technology, quantum computing has an increasingly significant impact on cryptanalysis. Several quantum algorithms, such as Simon’s algorithm, Grover’s algorithm, the Bernstein–Vazirani algorithm, Shor’s algorithm, and the Grover-meets-Simon algorithm, have been proposed successively. However, almost all cryptanalysis is based on the quantum chosen-plaintext attack (qCPA) model. This paper focuses on a powerful cryptanalytic model, quantum related-key attack (qRKA), and proposes a strategy of qRKAs against symmetric ciphers using Simon’s algorithm. We construct a periodic function to efficiently recover the secret key of symmetric ciphers if the attacked symmetric ciphers satisfy Simon’s promise, and present the complexity analysis on specific symmetric ciphers. Then, we apply qRKA to the Even–Mansour cipher and SoEM construction, recover their secret keys, and show their complexity comparison in the distinct attack models. This work is of great significance for the qRKA cryptanalysis of existing provably secure cryptographic schemes and the design of future quantum secure cryptographic schemes.
Abstract Many quantum algorithms for attacking symmetric cryptography involve the rank problem of quantum linear equations. In this paper, two quantum algorithms are proposed to solve quantum linear systems of equations with coherent superposition, and their specific quantum circuits are constructed. In contrast to previous related studies, our quantum algorithms are universal, computing both the rank and general solution by one measurement. The difference between them is whether the data register containing the quantum coefficient matrix can be disentangled from the other registers while keeping the data qubits unchanged. On this basis, the two quantum algorithms are applied as subroutines to parallel Simon’s algorithm (with multiple periods), Grover Meets Simon algorithm, and Alg-PolyQ2 algorithm. Subsequently, a quantum classifier within Grover Meets Simon algorithm and a detailed test oracle within Alg-PolyQ2 algorithms are constructed, including their respective quantum circuits. To the best of our knowledge, no such specific analysis has been previously performed. The success probability of these algorithms is rigorously analyzed to ensure that the probability of success on the proposed quantum algorithms will not be lower than that of the original algorithms. Finally, we discuss the lower bound of the number of controlled-NOT gates for solving quantum linear systems of equations with coherent superposition. Our analysis indicates that the proposed algorithms are suitable for conducting attacks against lightweight symmetric ciphers within the effective working time of an ion-trap quantum computer.
The compatibility of different quantum algorithms should be considered when these algorithms are combined. In this paper, the method of combining Grover and Simon is studied for the first time, under some preconditions or assumptions. First, we give two preconditions of applying Grover's algorithm, which ensure that the success probability of finding the marked element is close to 1. Then, based on these two preconditions, it is found out that the success probability of the quantum algorithm for FX-construction is far less than 1. Furthermore, we give the design method of the Oracle function, and then present the general method of combining Grover and Simon algorithm for attacking block ciphers, with success probability close to 1.
The advent of quantum computing presents a paradigm shift in the field of cryptanalysis, challenging the security of classical encryption schemes that underpin modern digital communications. This study explores the capabilities of quantum algorithms, particularly Shor's algorithm and Grover's algorithm, in undermining widely used cryptographic systems. Shor's algorithm poses a direct threat to publickey cryptosystems such as RSA and ECC by enabling efficient integer factorization and discrete logarithm computation, which are computationally infeasible for classical computers. Meanwhile, Grover's algorithm provides a quadratic speedup for bruteforce attacks on symmetric-key cryptosystems like AES, significantly reducing their effective security. Through theoretical analysis and simulation-based evaluation, this paper highlights the vulnerabilities of classical encryption in the face of quantum advances and underscores the urgent need for post-quantum cryptographic solutions. The findings emphasize the critical importance of transitioning to quantum-resistant algorithms to ensure long-term data confidentiality in a future dominated by quantum technologies.
Quantum computing is a rapidly growing field. Quantum algorithms play a significant role and have applications in cryptography, machine learning, optimization, and computational issues [1][2]. They quantum features like entanglement and superposition that help carryout tasks that would be difficult for a classical computer. More Interest has been developed in Quantum algorithms due to their ability to solve specific computational problems quicker than that in classical algorithms [3]. These algorithms use fundamentals of quantum physics to carryout calculations quickly and effectively than traditional algorithms. Here in-depth analysis of quantum algorithms and classical algorithms is done by looking at the time and space complexity of quantum and classical algorithms including their capacity to tackle specific types of issues.First, we conduct a general comparison of Classical and Quantum Algorithm along with Background and motivation. We also discuss Simon's algorithm first and then Grover's algorithm in depth and their comparison with few other algorithms in a table format [5][6][7][8]. We also cover some recent advancements, Quantum supremacy, Post-Quantum Cryptography, 8 Quantum Artificial Intelligence, Hybrid Quantum-Classical Algorithms and few other important parameters. We also discuss the plausible impact of quantum algorithms on cybersecurity and cryptography [13][9]. Overall, this comparative study shows the uses and challenges involved in implementing quantum algorithms while offering an overview of quantum algorithms. We conclude by the fundamental ideas of quantum algorithms. Adding to this we also discuss the challenges and limitations of using quantum algorithms in practically. At the end, we provide a summary of the primary findings from this comparative study of Quantum and classical algorithms.