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

ICT Express

Big Step: A fast quantum algorithm for nonce discovery in Proof-of-Work blockchains

Young-Hoon Park

Published Dec 2, 2025• 2 citations
Publisher

Abstract

Since the emergence of quantum computing, Grover’s algorithm has been widely studied as a method to attack Proof-of-Work (PoW) blockchains. However, it requires multiple oracle and diffuser iterations, causing high computational overhead and ancilla qubit usage. In this paper, we propose a novel quantum algorithm that efficiently finds valid nonces in PoW-based blockchains without iterative amplification. It introduces a non-unitary quantum operator that directly generates a superposition of valid nonces in one step. We also present an efficient quantum circuit implementation and theoretically prove that our algorithm significantly reduces computational resources compared to conventional Grover-based methods.

DOI
10.1016/j.icte.2025.11.023

Related papers

Implementation of Grover’s Iterator for Quantum Searching With an Arbitrary Number of Qubits

Sihyung Lee, Seung Yeob Nam

Grover’s algorithm harnesses the power of quantum computing to swiftly locate specific elements in an unstructured database, outperforming classical computers in tasks like database searching. This algorithm capitalizes on the unique ability of qubits to be in both 0 and 1 states simultaneously (superposition), allowing it to scan the entire search space at once. It then boosts the probability of the target element, making it more prominent. While the foundational concepts of Grover’s algorithm are well-documented, practical implementation using quantum operators, especially for large search spaces, remains less explored beyond basic examples with a small number of qubits. Existing general synthesis techniques often involve numerous operators or are time-consuming. Our proposed methods specifically address the amplitude-amplification component of Grover’s algorithm for any size of search space. These methods detail the required types and quantities of qubits and operators, emphasizing minimal usage and efficient assembly. Developed and evaluated in Python, our methods consistently identified target elements with over 95% accuracy and achieved configurations comparably compact as those in the existing literature but at a faster pace. We anticipate that these methods facilitate practical implementations of Grover’s algorithm across various domains.

IEEE Access•Jan 1, 2024•7 citations

Quantum Attacks and Defenses for Proof-of-Stake

Amr M. Khalifa, Ayman Mohammad Bahaa-Eldin, Mohamed Sobh

Advances in both quantum computation and blockchain systems necessitate a rigid analysis for the security of blockchains in the advent of powerful quantum computers. Computational problems that are proved or believed to be intractable by classical computers are known to be attacked by well-studied quantum algorithms. Such problems are used as basis to secure blockchains and hence the security of such systems must be defended. As proof-of-work is used in early blockchains to maintain consensus, proof-of-stake was proposed to lower its high energy consumption and provide a higher network throughput. Proof-of-Stake has hence got an increasing interest, variations, implementations and enhancements whilst its quantum security defenses remained almost the same. By comparing proof-of-work to proof-of-stake, we find that the latter is more vulnerable to certain attack vectors. We suggest general defenses for quantum-resilient blockchains and thoroughly analyze post-quantum signature schemes to select an appropriate alternative to the most serious threat on conventional digital signatures.

International Conference on Computer Engineering & Systems (ICCES)•Dec 1, 2019•19 citations

Implementation of Efficient Quantum Computing Algorithm for Searching

Nirhali Atharva, Malwade Rohit, P. Akshay +2 more

The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.

International Research Journal on Advanced Engineering Hub (IRJAEH)•May 21, 2025•0 citations

Quantum Advantage on Proof of Work

Dan A. Bard, Joseph J. Kearney, Carlos A. Pérez-Delgado

Proof-of-Work (PoW) is a fundamental underlying technology behind most major blockchain cryptocurrencies. It has been previously pointed out that quantum devices provide a computational advantage in performing PoW in the context of Bitcoin. Here we make the case that this quantum advantage extends not only to all existing PoW mechanisms, but to any possible PoW as well. This has strong consequences regarding both quantum-based attacks on the integrity of the entirety of the blockchain, as well as more legitimate uses of quantum computation for the purpose of mining Bitcoin and other cryptocurrencies. For the first case, we estimate when these quantum attacks will become feasible, for various cryptocurrencies, and discuss the impact of such attacks. For the latter, we derive a precise formula to calculate the economic incentive for switching to quantum-based cryptocurrency miners. Using this formula, we analyze several test scenarios, and conclude that investing in quantum hardware for cryptocurrency mining has the potential to pay off immensely.

arXiv:2105.01821•May 5, 2021•2 citations

Quantum advantage on proof of work

Dan A. Bard, Joseph J. Kearney, Carlos A. Pérez-Delgado

Proof-of-Work (PoW) is a fundamental underlying technology behind most major blockchain cryptocurrencies. It has been previously pointed out that quantum devices provide a computational advantage in performing PoW in the context of Bitcoin. Here we make the case that this quantum advantage extends not only to all existing PoW mechanisms, but to any possible PoW as well. This has strong consequences regarding both quantum-based attacks on the integrity of the entirety of the blockchain, as well as more legitimate uses of quantum computation for the purpose of mining Bitcoin and other cryptocurrencies. For the first case, we estimate when these quantum attacks will become feasible, for various cryptocurrencies, and discuss the impact of such attacks. For the latter, we derive a precise formula to calculate the economic incentive for switching to quantum-based cryptocurrency miners. Using this formula, we analyze several test scenarios, and conclude that investing in quantum hardware for cryptocurrency mining has the potential to pay off immensely.

Array•Jul 6, 2022•25 citations

Post-Quantum Blockchain Proofs of Work.

Alexandru Cojocaru, Juan A. Garay, Aggelos Kiayias +2 more

A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. Arguably, its main impact has been in the setting of cryptocurrencies such as Bitcoin and its underlying blockchain protocol, which received significant attention in recent years due to its potential for various applications as well as for solving fundamental distributed computing questions in novel threat models. PoWs enable the linking of blocks in the blockchain data structure and thus the problem of interest is the feasibility of obtaining a sequence (chain) of such proofs. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity. Effectively, this is an extension of a threshold direct product theorem to an average-case unstructured search problem. Our proof, adding to active recent efforts, simplifies and generalizes the recording technique due to Zhandry (Crypto 2019). In addition, we revisit the formal treatment of security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), against quantum adversaries and show that its security holds under a quantum analogue of the ``honest majority'' assumption that we formulate. Our analysis indicates that security of the Bitcoin backbone protocol is guaranteed provided that the number of adversarial quantum queries is bounded so that each quantum query is worth $O(p^{-1/2})$ classical ones, where $p$ is the probability of success of a single classical query to the protocol's underlying hash function. Somewhat surprisingly, the wait time for safe settlement in the case of quantum adversaries matches the safe settlement time in the classical case.

•Dec 1, 2021•0 citations
Since the emergence of quantum computing, Grover’s algorithm has been widely studied as a method to attack Proof-of-Work (PoW) blockchains. However, it requires multiple oracle and diffuser iterations, causing high computational overhead and ancilla qubit usage. In this paper, we propose a novel quantum algorithm that efficiently finds valid nonces in PoW-based blockchains without iterative amplification. It introduces a non-unitary quantum operator that directly generates a superposition of valid nonces in one step. We also present an efficient quantum circuit implementation and theoretically prove that our algorithm significantly reduces computational resources compared to conventional Grover-based methods.
Grover’s algorithm harnesses the power of quantum computing to swiftly locate specific elements in an unstructured database, outperforming classical computers in tasks like database searching. This algorithm capitalizes on the unique ability of qubits to be in both 0 and 1 states simultaneously (superposition), allowing it to scan the entire search space at once. It then boosts the probability of the target element, making it more prominent. While the foundational concepts of Grover’s algorithm are well-documented, practical implementation using quantum operators, especially for large search spaces, remains less explored beyond basic examples with a small number of qubits. Existing general synthesis techniques often involve numerous operators or are time-consuming. Our proposed methods specifically address the amplitude-amplification component of Grover’s algorithm for any size of search space. These methods detail the required types and quantities of qubits and operators, emphasizing minimal usage and efficient assembly. Developed and evaluated in Python, our methods consistently identified target elements with over 95% accuracy and achieved configurations comparably compact as those in the existing literature but at a faster pace. We anticipate that these methods facilitate practical implementations of Grover’s algorithm across various domains.
Advances in both quantum computation and blockchain systems necessitate a rigid analysis for the security of blockchains in the advent of powerful quantum computers. Computational problems that are proved or believed to be intractable by classical computers are known to be attacked by well-studied quantum algorithms. Such problems are used as basis to secure blockchains and hence the security of such systems must be defended. As proof-of-work is used in early blockchains to maintain consensus, proof-of-stake was proposed to lower its high energy consumption and provide a higher network throughput. Proof-of-Stake has hence got an increasing interest, variations, implementations and enhancements whilst its quantum security defenses remained almost the same. By comparing proof-of-work to proof-of-stake, we find that the latter is more vulnerable to certain attack vectors. We suggest general defenses for quantum-resilient blockchains and thoroughly analyze post-quantum signature schemes to select an appropriate alternative to the most serious threat on conventional digital signatures.
The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.
Proof-of-Work (PoW) is a fundamental underlying technology behind most major blockchain cryptocurrencies. It has been previously pointed out that quantum devices provide a computational advantage in performing PoW in the context of Bitcoin. Here we make the case that this quantum advantage extends not only to all existing PoW mechanisms, but to any possible PoW as well. This has strong consequences regarding both quantum-based attacks on the integrity of the entirety of the blockchain, as well as more legitimate uses of quantum computation for the purpose of mining Bitcoin and other cryptocurrencies. For the first case, we estimate when these quantum attacks will become feasible, for various cryptocurrencies, and discuss the impact of such attacks. For the latter, we derive a precise formula to calculate the economic incentive for switching to quantum-based cryptocurrency miners. Using this formula, we analyze several test scenarios, and conclude that investing in quantum hardware for cryptocurrency mining has the potential to pay off immensely.
Proof-of-Work (PoW) is a fundamental underlying technology behind most major blockchain cryptocurrencies. It has been previously pointed out that quantum devices provide a computational advantage in performing PoW in the context of Bitcoin. Here we make the case that this quantum advantage extends not only to all existing PoW mechanisms, but to any possible PoW as well. This has strong consequences regarding both quantum-based attacks on the integrity of the entirety of the blockchain, as well as more legitimate uses of quantum computation for the purpose of mining Bitcoin and other cryptocurrencies. For the first case, we estimate when these quantum attacks will become feasible, for various cryptocurrencies, and discuss the impact of such attacks. For the latter, we derive a precise formula to calculate the economic incentive for switching to quantum-based cryptocurrency miners. Using this formula, we analyze several test scenarios, and conclude that investing in quantum hardware for cryptocurrency mining has the potential to pay off immensely.
A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. Arguably, its main impact has been in the setting of cryptocurrencies such as Bitcoin and its underlying blockchain protocol, which received significant attention in recent years due to its potential for various applications as well as for solving fundamental distributed computing questions in novel threat models. PoWs enable the linking of blocks in the blockchain data structure and thus the problem of interest is the feasibility of obtaining a sequence (chain) of such proofs. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity. Effectively, this is an extension of a threshold direct product theorem to an average-case unstructured search problem. Our proof, adding to active recent efforts, simplifies and generalizes the recording technique due to Zhandry (Crypto 2019). In addition, we revisit the formal treatment of security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), against quantum adversaries and show that its security holds under a quantum analogue of the ``honest majority'' assumption that we formulate. Our analysis indicates that security of the Bitcoin backbone protocol is guaranteed provided that the number of adversarial quantum queries is bounded so that each quantum query is worth O(p−1/2)O(p^{-1/2})O(p−1/2) classical ones, where ppp is the probability of success of a single classical query to the protocol's underlying hash function. Somewhat surprisingly, the wait time for safe settlement in the case of quantum adversaries matches the safe settlement time in the classical case.