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

Cambridge University Press eBooks

The quantum puzzle

Stephen W. McKnight, Christos Zahopoulos

Published Aug 10, 2015• 0 citations
Publisher
DOI
10.1017/cbo9781139565462.009

Related papers

The Quantum Puzzle and Time

Wm. S. Franklin

Science•Sep 19, 1924•0 citations

Quantum puzzles, mysteries and paradoxes

Jozef Gruska, Ferdinand Peper

•Jan 1, 2000•0 citations

The Quantum Enigma

Olivier Darrigol

Cambridge University Press eBooks•May 9, 2014•17 citations

Quantum Time-Lock Puzzles in the Quantum Random Oracle Model

Prabhanjan Ananth, Yao-Ting Lin

A time-lock puzzle allows a sender to hide a message in a puzzle such that recovering the message requires substantially more sequential computation than the time required to generate the puzzle, even when parallel computation is allowed. Applications of time-lock puzzles include timed-release encryption, sealed-bid auctions, electronic voting, fair contract signing, coin flipping, and Byzantine consensus. However, time-lock puzzles are known to be impossible in the classical random oracle model. To overcome the classical barrier, in this work we consider quantum time-lock puzzles, in which the puzzle itself is a quantum state. Our construction in the quantum random oracle model achieves generation in one oracle round, solving in at most $T$ oracle rounds, and security against polynomial-width quantum adversaries of depth $o(T)$ for every polynomially bounded delay $T=T(λ)$, resolving an open problem posed by Mahmoody, Moran, and Vadhan (2011).

quant-pharXiv:2609.38894•Oct 1, 2026•0 citations

Quantum permutation puzzles with indistinguishable particles

Noah Lordi, Maedée Trank-Greene, Akira Kyle +1 more

Permutation puzzles, such as the Rubik's Cube and the 15 puzzle, are enjoyed by the general public and mathematicians alike. Here we introduce quantum versions of permutation puzzles where the pieces of the puzzles are replaced with indistinguishable quantum particles. The moves in the puzzle are achieved by swapping or permuting the particles. We show that simply permuting the particles can be mapped to a classical permutation puzzle, even though the identical particles are entangled. However, we obtain a genuine quantum puzzle by adding a quantum move: the square root of swap. The resulting puzzle cannot be mapped to a classical permutation puzzle. We focus predominately on the quantization of the $2\ifmmode\times\else\texttimes\fi{}2$ slide puzzle and briefly treat the $2\ifmmode\times\else\texttimes\fi{}2\ifmmode\times\else\texttimes\fi{}1$ Rubik's Cube.

arXiv:2410.22287•Physical Review A•Apr 14, 2025•3 citations

Complexity of Solving Hash Puzzles Using Revised Boyer Quantum Algorithm

Chris Idota, Yuichi Kaji

This study investigates the computational complexity of solving hash puzzles using quantum algorithms. A hash puzzle is formalized as a problem for finding a pre-image whose hash value falls within a specified target set. It is known that Grover quantum search algorithm and Boyer algorithm, which is a Bayesian utilization of Grover algorithm, can compute the preimage of a given hash value more efficiently than non-quantum algorithms. However, those quantum algorithms use implicit assumptions and approximations that are not compatible with a general hash puzzle. This study revises Boyer algorithm by excluding those assumptions and approximations, and clarifies the relation between the size of the target set of a hash puzzle and the complexity necessary for solving the puzzle. It is shown that, in the quantum framework, a hash puzzle with fewer targets can be easier to solve than a hash puzzle with more targets, which contradicts to the classical understanding where puzzles with fewer targets are more difficult to solve.

International Symposium on Information Theory and its Applications•Nov 10, 2024•0 citations
A time-lock puzzle allows a sender to hide a message in a puzzle such that recovering the message requires substantially more sequential computation than the time required to generate the puzzle, even when parallel computation is allowed. Applications of time-lock puzzles include timed-release encryption, sealed-bid auctions, electronic voting, fair contract signing, coin flipping, and Byzantine consensus. However, time-lock puzzles are known to be impossible in the classical random oracle model. To overcome the classical barrier, in this work we consider quantum time-lock puzzles, in which the puzzle itself is a quantum state. Our construction in the quantum random oracle model achieves generation in one oracle round, solving in at most TTT oracle rounds, and security against polynomial-width quantum adversaries of depth o(T)o(T)o(T) for every polynomially bounded delay T=T(λ)T=T(λ)T=T(λ), resolving an open problem posed by Mahmoody, Moran, and Vadhan (2011).
Permutation puzzles, such as the Rubik's Cube and the 15 puzzle, are enjoyed by the general public and mathematicians alike. Here we introduce quantum versions of permutation puzzles where the pieces of the puzzles are replaced with indistinguishable quantum particles. The moves in the puzzle are achieved by swapping or permuting the particles. We show that simply permuting the particles can be mapped to a classical permutation puzzle, even though the identical particles are entangled. However, we obtain a genuine quantum puzzle by adding a quantum move: the square root of swap. The resulting puzzle cannot be mapped to a classical permutation puzzle. We focus predominately on the quantization of the $2\ifmmode\times\else\texttimes\fi{}2$ slide puzzle and briefly treat the $2\ifmmode\times\else\texttimes\fi{}2\ifmmode\times\else\texttimes\fi{}1$ Rubik's Cube.
This study investigates the computational complexity of solving hash puzzles using quantum algorithms. A hash puzzle is formalized as a problem for finding a pre-image whose hash value falls within a specified target set. It is known that Grover quantum search algorithm and Boyer algorithm, which is a Bayesian utilization of Grover algorithm, can compute the preimage of a given hash value more efficiently than non-quantum algorithms. However, those quantum algorithms use implicit assumptions and approximations that are not compatible with a general hash puzzle. This study revises Boyer algorithm by excluding those assumptions and approximations, and clarifies the relation between the size of the target set of a hash puzzle and the complexity necessary for solving the puzzle. It is shown that, in the quantum framework, a hash puzzle with fewer targets can be easier to solve than a hash puzzle with more targets, which contradicts to the classical understanding where puzzles with fewer targets are more difficult to solve.