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

Zhongguo kexue. Wulixue Lixue Tianwenxue

基于改进Grover算法的ECC扫描式攻击

Yuchen He, Yulong Fu, Zeyang Zhang, Tian Luan, Junwei Lu

Published Nov 1, 2024• 0 citations
Publisher

Abstract

Scan-based attacks represent a category of side-channel attacks that pose potential risks to elliptic curve cryptosystems. A critical computational element in such attacks is the unstructured search of the scan data. The Grover algorithm, a quantum algorithm for the unstructured search, achieves quadratic speedup over classical methods, making it a promising tool for enhancing scan-based attacks in the quantum context. In this paper, we propose two methods to improve the Grover algorithm used in the ECC scan-based attack. These methods reduce the depth of the quantum circuit by over 85% compared with the Grover-Long algorithm, thus improving the feasibility of the Grover algorithm in scan-based attacks in the noisy intermediate-scale quantum (NISQ) era.

DOI
10.1360/sspma-2024-0545

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

The Quadratic Leap: How Grover's Algorithm is Redefining Core Problems in Computer Science and Engineering

Palaganti Venkata Nagendra Sai Sandeep

Grover's algorithm stands as a cornerstone of quantum computing, offering a theoretical quadratic speedup for unstructured search problems. This allows for finding a target item in an unsorted database of N entries in approximately the square root of N steps, a significant improvement over classical algorithms which require a number of operations on the order of N in the worst case. This speedup becomes particularly compelling for very large datasets, where classical exhaustive search becomes computationally intractable. The algorithm achieves this by leveraging fundamental quantum mechanical principles, primarily superposition and interference. It operates by preparing qubits in a uniform superposition of all possible states, then iteratively applying a quantum oracle to mark the desired state by flipping its phase, followed by a diffusion operator that amplifies the probability of the marked state. Despite its theoretical promise, real-world implementation faces substantial challenges stemming from Noisy Intermediate-Scale Quantum (NISQ) hardware, which is characterized by high error rates and short coherence times. Consequently, achieving a true, scalable quantum advantage remains a future endeavor, contingent on significant hardware advancements. Nevertheless, Grover's algorithm holds significant potential across diverse fields, including enhancing brute-force attacks on cryptographic systems, accelerating solutions for optimization problems, and speeding up search processes in machine learning and unstructured database queries.

•Aug 2, 2025•2 citations

Optimization of 16-Element Quantum Search on IBMQ

Wei Zi, Shuai Yang, Cheng Guo +1 more

Unstructured searching, which is to find the marked element from a given unstructured data set, is a widely studied problem in computer science. It is well known that Grover algorithm provides a quadratic speedup to solve unstructured search problem compared with the classical algorithm. This algorithm has received a lot of attention due to the strong versatility. In this manuscript, we report experimental results of searching a unique target from 16 elements on five different quantum devices of IBM quantum Experience (IBMQ). We first implement the original Grover algorithm on these devices. However, the experiment probability of success of finding the correct target is almost the same as random choice. We then optimize the quantum circuit size of the search algorithm. The oracle operator and diffusion operator are two of the most costly operators in Grover algorithm. For the 16-element quantum search algorithm, both the oracle operator and diffusion operator consist of a triple controlled [Formula: see text] gate ([Formula: see text]) and some single-qubit gates. So we optimize the implementation of the [Formula: see text] gate according to the qubits layout of different quantum devices. On the ibmq_santiago, the experimental success rate of the 16-element quantum search algorithm is increased to [Formula: see text] by the optimization, which is better than all the published experiments implemented on IBMQ devices. For other IBMQ devices, the experimental success rate of 16-element quantum search also has been significantly improved. We then try to further reduce the size of the quantum circuit by modifying the Grover algorithm, with a tolerable loss of the theoretical success probability. On ibmq_quito, the experimental success rate is further improved from 25.23% to 27.56% after optimization. These experimental results show the importance of circuit optimization and algorithm optimization in the Noisy-Intermediate-Scale Quantum (NISQ) era.

SPIN•Sep 1, 2021•1 citation

Quadratically Fast Searching in Quantum Computation

Mohit Joshi, Manoj Kumar Mishra, S. Karthikeyan

Grover’s search algorithm is one of the most famous quantum algorithms, which enables search in unstructured dataspaces with a quadratic speedup over any known classical algorithm. This is one of the first algorithms to show quantum advantage over classical methods of computation. Besides its most anticipated application of brute force attack on symmetric key encryptions like AES, it is today being used in many modern applications as a subroutine. In this chapter, we describe the mathematical model of Grover’s quantum search algorithm, its behavior, and the theory of its circuit implementation. This chapter also discusses an exact variant of this algorithm and recent applications of Grover’s quantum search.

CRC Press eBooks•Mar 24, 2026•0 citations

Prospect of using Grover's search in the noisy-intermediate-scale quantum-computer era

Yulun Wang, Predrag Krstić

In order to understand the bounds of utilization of Grover's search algorithm for large unstructured data in the presence of quantum computer noise, we undertake a series of simulations by inflicting various types of noise, modeled by the IBM qiskit. We apply three forms of Grover's algorithm: (i) the standard one, with 4--10 qubits; (ii) a recently published modified Grover's algorithm, set to reduce the circuit depth; and (iii) the algorithms in (i) and (ii) with multicontrol Toffoli's gates modified by the addition of an ancilla qubit. Based on these simulations, we find the upper bound of noise for these cases, establish its dependence on the quantum depth of the circuit, and provide comparison among them. By extrapolation of the fitted thresholds, we predict what would be the typical gate error bounds when applying Grover's algorithms for the search of data in a data set as large as 32 000.

arXiv:2006.10037•Physical Review A•Oct 20, 2020•36 citations

Grover Algorithm: Enhancing the Search Mechanism

Jagriti Malhotra, Omkar Chavan, Pallavi Thakur

Grover’s algorithm is a quantum search algorithm that makes a huge difference in finding an element of interest from unsorted and unstructured data. In the case of a classical search algorithm, testing O(N) elements within a dataset of size N is a significant number. Grover’s algorithm reduces this number to $O(\sqrt N )$ so the gain is obvious. This paper covers applied aspects of Grover’s algorithm, namely quantum circuit layout, efficiency of gates, fidelity of qubits, and the optimization of resources for searching unstructured data. Focus has been placed on quantum error correction: namely, planar surface code; resource costs involved have been quantified. The paper discusses the implications of quantum computing on data retrieval and how algorithms in quantum computing are crucial for solving issues presented by a changing environment of computation.

OPJU International Technology Conference on Smart Computing for Innovation and Advancement in Industry (OTCON)•Apr 9, 2025•2 citations
Scan-based attacks represent a category of side-channel attacks that pose potential risks to elliptic curve cryptosystems. A critical computational element in such attacks is the unstructured search of the scan data. The Grover algorithm, a quantum algorithm for the unstructured search, achieves quadratic speedup over classical methods, making it a promising tool for enhancing scan-based attacks in the quantum context. In this paper, we propose two methods to improve the Grover algorithm used in the ECC scan-based attack. These methods reduce the depth of the quantum circuit by over 85% compared with the Grover-Long algorithm, thus improving the feasibility of the Grover algorithm in scan-based attacks in the noisy intermediate-scale quantum (NISQ) era.
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.
Grover's algorithm stands as a cornerstone of quantum computing, offering a theoretical quadratic speedup for unstructured search problems. This allows for finding a target item in an unsorted database of N entries in approximately the square root of N steps, a significant improvement over classical algorithms which require a number of operations on the order of N in the worst case. This speedup becomes particularly compelling for very large datasets, where classical exhaustive search becomes computationally intractable. The algorithm achieves this by leveraging fundamental quantum mechanical principles, primarily superposition and interference. It operates by preparing qubits in a uniform superposition of all possible states, then iteratively applying a quantum oracle to mark the desired state by flipping its phase, followed by a diffusion operator that amplifies the probability of the marked state. Despite its theoretical promise, real-world implementation faces substantial challenges stemming from Noisy Intermediate-Scale Quantum (NISQ) hardware, which is characterized by high error rates and short coherence times. Consequently, achieving a true, scalable quantum advantage remains a future endeavor, contingent on significant hardware advancements. Nevertheless, Grover's algorithm holds significant potential across diverse fields, including enhancing brute-force attacks on cryptographic systems, accelerating solutions for optimization problems, and speeding up search processes in machine learning and unstructured database queries.
Unstructured searching, which is to find the marked element from a given unstructured data set, is a widely studied problem in computer science. It is well known that Grover algorithm provides a quadratic speedup to solve unstructured search problem compared with the classical algorithm. This algorithm has received a lot of attention due to the strong versatility. In this manuscript, we report experimental results of searching a unique target from 16 elements on five different quantum devices of IBM quantum Experience (IBMQ). We first implement the original Grover algorithm on these devices. However, the experiment probability of success of finding the correct target is almost the same as random choice. We then optimize the quantum circuit size of the search algorithm. The oracle operator and diffusion operator are two of the most costly operators in Grover algorithm. For the 16-element quantum search algorithm, both the oracle operator and diffusion operator consist of a triple controlled [Formula: see text] gate ([Formula: see text]) and some single-qubit gates. So we optimize the implementation of the [Formula: see text] gate according to the qubits layout of different quantum devices. On the ibmq_santiago, the experimental success rate of the 16-element quantum search algorithm is increased to [Formula: see text] by the optimization, which is better than all the published experiments implemented on IBMQ devices. For other IBMQ devices, the experimental success rate of 16-element quantum search also has been significantly improved. We then try to further reduce the size of the quantum circuit by modifying the Grover algorithm, with a tolerable loss of the theoretical success probability. On ibmq_quito, the experimental success rate is further improved from 25.23% to 27.56% after optimization. These experimental results show the importance of circuit optimization and algorithm optimization in the Noisy-Intermediate-Scale Quantum (NISQ) era.
Grover’s search algorithm is one of the most famous quantum algorithms, which enables search in unstructured dataspaces with a quadratic speedup over any known classical algorithm. This is one of the first algorithms to show quantum advantage over classical methods of computation. Besides its most anticipated application of brute force attack on symmetric key encryptions like AES, it is today being used in many modern applications as a subroutine. In this chapter, we describe the mathematical model of Grover’s quantum search algorithm, its behavior, and the theory of its circuit implementation. This chapter also discusses an exact variant of this algorithm and recent applications of Grover’s quantum search.
In order to understand the bounds of utilization of Grover's search algorithm for large unstructured data in the presence of quantum computer noise, we undertake a series of simulations by inflicting various types of noise, modeled by the IBM qiskit. We apply three forms of Grover's algorithm: (i) the standard one, with 4--10 qubits; (ii) a recently published modified Grover's algorithm, set to reduce the circuit depth; and (iii) the algorithms in (i) and (ii) with multicontrol Toffoli's gates modified by the addition of an ancilla qubit. Based on these simulations, we find the upper bound of noise for these cases, establish its dependence on the quantum depth of the circuit, and provide comparison among them. By extrapolation of the fitted thresholds, we predict what would be the typical gate error bounds when applying Grover's algorithms for the search of data in a data set as large as 32 000.
Grover’s algorithm is a quantum search algorithm that makes a huge difference in finding an element of interest from unsorted and unstructured data. In the case of a classical search algorithm, testing O(N) elements within a dataset of size N is a significant number. Grover’s algorithm reduces this number to O(N)O(\sqrt N )O(N​) so the gain is obvious. This paper covers applied aspects of Grover’s algorithm, namely quantum circuit layout, efficiency of gates, fidelity of qubits, and the optimization of resources for searching unstructured data. Focus has been placed on quantum error correction: namely, planar surface code; resource costs involved have been quantified. The paper discusses the implications of quantum computing on data retrieval and how algorithms in quantum computing are crucial for solving issues presented by a changing environment of computation.