Related papers: Quantum permutation puzzles with indistinguishable particles

Quantum permutation puzzles with indistinguishable particles

URL: http://arxiv.org/abs/2410.22287v1
Date: Tue, 29 Oct 2024 17:39:13 GMT
Title: Quantum permutation puzzles with indistinguishable particles
Authors: Noah Lordi, Maedee Trank-Greene, Akira Kyle, Joshua Combes,
Abstract summary: 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.
Score: 0.0
License:
Abstract: 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\times 2$ slide puzzle and briefly treat the $2\times 2 \times 1$ Rubik's cube.

Related papers

A Meta-Complexity Characterization of Quantum Cryptography [2.8311451575532156]
We prove the first meta-complexity characterization of a quantum cryptographic primitive. We show that one-way puzzles exist if and only if there is some quantum samplable distribution of binary strings over which it is hard to approximate Kolmogorov complexity.
arXiv Detail & Related papers (2024-10-07T12:29:27Z)
Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
Recent separations have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if hierarchy collapses. We show that quantum cryptography can be based on the extremely mild assumption that $mathsfP#P notsubseteq mathsf(io)BQP/qpoly$.
arXiv Detail & Related papers (2024-09-23T17:45:33Z)
Photonic implementation of the quantum Morra game [69.65384453064829]
We study a faithful translation of a two-player quantum Morra game, which builds on previous work by including the classical game as a special case. We propose a natural deformation of the game in the quantum regime in which Alice has a winning advantage, breaking the balance of the classical game. We discuss potential applications of the quantum Morra game to the study of quantum information and communication.
arXiv Detail & Related papers (2023-11-14T19:41:50Z)
Automated Graph Genetic Algorithm based Puzzle Validation for Faster Game Desig [69.02688684221265]
This paper presents an evolutionary algorithm, empowered by expert-knowledge informeds, for solving logical puzzles in video games efficiently. We discuss multiple variations of hybrid genetic approaches for constraint satisfaction problems that allow us to find a diverse set of near-optimal solutions for puzzles.
arXiv Detail & Related papers (2023-02-17T18:15:33Z)
One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
arXiv Detail & Related papers (2023-01-05T11:05:22Z)
Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z)
Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z)
Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z)
A new perspective of paramodulation complexity by solving massive 8 puzzles [0.4514386953429769]
A sliding puzzle is a combination puzzle where a player slide pieces along certain routes on a board to reach a certain end-configuration. It turned out that by counting the number of clauses yielded with paramodulation, we can evaluate the difficulty of each puzzle.
arXiv Detail & Related papers (2020-12-15T11:47:47Z)
SudoQ -- a quantum variant of the popular game [1.5229257192293197]
We introduce SudoQ, a quantum version of the classical game Sudoku. The solution set of SudoQ puzzles can be much larger than in the classical (commutative) setting.
arXiv Detail & Related papers (2020-05-21T19:19:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.