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

Quantum Electronics and Laser Science Conference

Counterfactual quantum computation

Onur Hosten, Matthew T. Rakher, Julio T. Barreiro, Nicholas A. Peters, Paul G. Kwiat

Published Dec 10, 2005• 2 citations
Publisher

Abstract

We present the first demonstration of Jozsa's "counterfactual computation", using an optical Grover's search algorithm. We put the algorithm in a superposition of "running" and "not-running", obtaining information even though the algorithm does not run.
DOI
10.1109/qels.2005.1548783

Related papers

An invitation to quantum computing

Andreas R. Blass, Yuri G. Gurevich

When a computer scientist attempts to understand quantum computing, he may stumble over the physics that seems to be a prerequisite. As a result, the attempt may be abandoned. This little pedagogical essay is aimed to help with this problem. We present the specific example of Grover’s search algorithm, but we put computation first and postpone physics.

Bulletin of the European Association for Theoretical Computer Science•Sep 26, 2018•2 citations

A Generalization of Deutch-Jozsa Algorithm

Elton Ballhysa

Quantum Computation is seen as an alternative paradigm for computing as the physical implentations for the basic information unit, the binary digit, approach the atomic level. As the laws of quantum mechanics take over at this level, quantum phenomena such as superposition, the ensuing parallelism and entanglement can be harnessed to offer faster algorithms. Deutch- Jozsa was the first problem for such an algorithm was exhibited that was provably faster than any deterministic classical algorithm. Here we make an attempt at a generalization of this algorithm, hoping that it could lead to similar generalizations for other quantum algorithms.

•Jun 30, 2009•0 citations

Searching with Quantum Computers

Lov K. Grover

This article introduces quantum computation by analogy with probabilistic computation. A basic description of the quantum search algorithm is given by representing the algorithm as a C program in a novel way.

arXiv:quant-ph/0011118•Dr. Dobb's Journal archive•Nov 30, 2000•15 citations

Pixel identification in an image using Grover Search Algorithm

Mohd. Hussain Mir, Singh, Harkirat

Quantum Computing offers an entirely new way of doing computation governed by the rules of quantum mechanics like Superposition and Entanglement. These rules allow us to do computation over all the possible states simultaneously. Hence, offering exponentially higher computation power than the present classical computers. Quantum computing algorithms are entirely different from classical algorithms due to quantum parallel computing derived from quantum state superposition and entanglement, which has natural advantages over classical image processing. Grover algorithm is a quantum-based search algorithm used to find the correct answer from an unsorted database by computing all the inputs simultaneously. Thus, giving us a quadratic speed-up of order O(n) 1/2 in comparison to the classical algorithm which offers speedup with order O(n). We used the Grover algorithm for identifying the black pixel in a (2x2) classical image by first converting it into a quantum state and then running the Grover algorithm for identifying the pixel with 0 value maximum gray-scale intensity. This technique has applications in areas like steganography offering data encryption between users, image segmentation.

arXiv:2107.03039•Jul 7, 2021•1 citation

Impossibility of the Counterfactual Computation for All Possible Outcomes

Lev Vaidman A

A recent proposal for counterfactual computation [O. Hosten et al. Nature (London) 439, 949 (2006) is analyzed. It is argued that the method does not provide counterfactual computation for all possible outcomes. The explanation involves a novel paradoxical feature of pre- and postselected quantum particles: The particle can reach a certain location without being on the path that leads to this location.

arXiv:quant-ph/0610174•Physical Review Letters•Apr 18, 2007•60 citations

The Grover Dilemma and Three Fundamental Barriers to Oracle-Based Quantum Search Algorithms

Ying Liu (18461)

Grover’s algorithm is widely celebrated as providing quadratic quantum speedup for unsorted database search, forming the theoretical foundation for numerous claimed quantum advantages in machine learning, optimization, and computational applications. We demonstrate that Grover’s algorithm and oracle-based quantum search algorithms face three fundamental barriers that severely limit their practical applicability. First, we identify the Grover Dilemma: when the computational space exceeds the valid data space, Grover’s algorithm must choose between 1) creating uniform superposition over all computational states—including invalid states that lead to incorrect results, 2) restricting superposition to only valid states containing solutions—requiring prior knowledge that reduces the problem to trivial O(1) complexity, or 3) constructing superposition over valid states through classical preprocessing—requiring O(N) cost that eliminates the claimed O( N ) quantum advantage. We extend this analysis to establish a unified framework of three independent barriers affecting oracle-based quantum search: 1) the Grover Dilemma (superposition construction for structured problems), 2) the Setup Cost Dilemma (oracle construction and data loading costs), and 3) Oracle Circularity (oracle specification requiring solution of the target problem). These barriers are logically independent—a quantum algorithm must avoid all three to achieve genuine advantage. Through systematic analysis of major problem classes and specific quantum algorithms, we found that oracle-based quantum search provides genuine computational advantage only in an exceptionally narrow class of problems. Our contributions are formalized in ten theorems: Theorems 6.1-6.5 establish the general framework (Grover Dilemma Barrier, Setup Cost Barrier, Oracle Circularity Barrier, Composite Barrier, and general conditions for no quantum advantage); Theorems 6.6-6.8 prove no quantum advantage for Deutsch’s Algorithm, Deutsch-Jozsa Algorithm, and Simon’s Algorithm in practical scenarios; Theorems 6.9-6.10 prove no quantum advantage for NP-complete problems and learning/optimization problems subject to Oracle Circularity. The three-barrier framework provides a systematic method for evaluating quantum search algorithm claims and distinguishing genuine advantages from artifacts of incomplete cost analysis.

Journal of Quantum Information Science•Jan 1, 2026•4 citations
Quantum Computation is seen as an alternative paradigm for computing as the physical implentations for the basic information unit, the binary digit, approach the atomic level. As the laws of quantum mechanics take over at this level, quantum phenomena such as superposition, the ensuing parallelism and entanglement can be harnessed to offer faster algorithms. Deutch- Jozsa was the first problem for such an algorithm was exhibited that was provably faster than any deterministic classical algorithm. Here we make an attempt at a generalization of this algorithm, hoping that it could lead to similar generalizations for other quantum algorithms.
Quantum Computing offers an entirely new way of doing computation governed by the rules of quantum mechanics like Superposition and Entanglement. These rules allow us to do computation over all the possible states simultaneously. Hence, offering exponentially higher computation power than the present classical computers. Quantum computing algorithms are entirely different from classical algorithms due to quantum parallel computing derived from quantum state superposition and entanglement, which has natural advantages over classical image processing. Grover algorithm is a quantum-based search algorithm used to find the correct answer from an unsorted database by computing all the inputs simultaneously. Thus, giving us a quadratic speed-up of order O(n) 1/2 in comparison to the classical algorithm which offers speedup with order O(n). We used the Grover algorithm for identifying the black pixel in a (2x2) classical image by first converting it into a quantum state and then running the Grover algorithm for identifying the pixel with 0 value maximum gray-scale intensity. This technique has applications in areas like steganography offering data encryption between users, image segmentation.
Grover’s algorithm is widely celebrated as providing quadratic quantum speedup for unsorted database search, forming the theoretical foundation for numerous claimed quantum advantages in machine learning, optimization, and computational applications. We demonstrate that Grover’s algorithm and oracle-based quantum search algorithms face three fundamental barriers that severely limit their practical applicability. First, we identify the Grover Dilemma: when the computational space exceeds the valid data space, Grover’s algorithm must choose between 1) creating uniform superposition over all computational states—including invalid states that lead to incorrect results, 2) restricting superposition to only valid states containing solutions—requiring prior knowledge that reduces the problem to trivial O(1) complexity, or 3) constructing superposition over valid states through classical preprocessing—requiring O(N) cost that eliminates the claimed O( N ) quantum advantage. We extend this analysis to establish a unified framework of three independent barriers affecting oracle-based quantum search: 1) the Grover Dilemma (superposition construction for structured problems), 2) the Setup Cost Dilemma (oracle construction and data loading costs), and 3) Oracle Circularity (oracle specification requiring solution of the target problem). These barriers are logically independent—a quantum algorithm must avoid all three to achieve genuine advantage. Through systematic analysis of major problem classes and specific quantum algorithms, we found that oracle-based quantum search provides genuine computational advantage only in an exceptionally narrow class of problems. Our contributions are formalized in ten theorems: Theorems 6.1-6.5 establish the general framework (Grover Dilemma Barrier, Setup Cost Barrier, Oracle Circularity Barrier, Composite Barrier, and general conditions for no quantum advantage); Theorems 6.6-6.8 prove no quantum advantage for Deutsch’s Algorithm, Deutsch-Jozsa Algorithm, and Simon’s Algorithm in practical scenarios; Theorems 6.9-6.10 prove no quantum advantage for NP-complete problems and learning/optimization problems subject to Oracle Circularity. The three-barrier framework provides a systematic method for evaluating quantum search algorithm claims and distinguishing genuine advantages from artifacts of incomplete cost analysis.