Solving Rubik's Cube via Quantum Mechanics and Deep Reinforcement Learning
arXiv:2109.07199 · doi:10.1088/1751-8121/ac2596
Abstract
Rubik's Cube is one of the most famous combinatorial puzzles involving nearly possible configurations. Its mathematical description is expressed by the Rubik's group, whose elements define how its layers rotate. We develop a unitary representation of such group and a quantum formalism to describe the Cube from its geometrical constraints. Cubies are describedby single particle states which turn out to behave like bosons for corners and fermions for edges, respectively. When in its solved configuration, the Cube, as a geometrical object, shows symmetrieswhich are broken when driven away from this configuration. For each of such symmetries, we build a Hamiltonian operator. When a Hamiltonian lies in its ground state, the respective symmetry of the Cube is preserved. When all such symmetries are preserved, the configuration of the Cube matches the solution of the game. To reach the ground state of all the Hamiltonian operators, we make use of a Deep Reinforcement Learning algorithm based on a Hamiltonian reward. The Cube is solved in four phases, all based on a respective Hamiltonian reward based on its spectrum, inspired by the Ising model. Embedding combinatorial problems into the quantum mechanics formalism suggests new possible algorithms and future implementations on quantum hardware.
arXiv comment26 pages, 48 references, 55 equations, 5 tables, 7 figures
References in corpus (16)
- Ising formulations of many NP problems
- Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
- Reinforcement Learning in Different Phases of Quantum Control
- Reinforcement Learning with Neural Networks for Quantum Feedback
- Quantum phase transitions in transverse field spin models: from statistical physics to quantum information
- Fidelity-based Probabilistic Q-learning for Control of Quantum Systems
- When does reinforcement learning stand out in quantum control? A comparative study on state preparation
- Social applications of two-dimensional Ising models
- How "Quantum" is the D-Wave Machine?
- Coherent Transport of Quantum States by Deep Reinforcement Learning
- Reconstruction of a Photonic Qubit State with Reinforcement Learning
- Measurement-based adaptation protocol with quantum reinforcement learning
- Finding and proving the exact ground state of a generalized Ising model by convex optimization and MAX-SAT
- Reinforcement Learning for Molecular Design Guided by Quantum Mechanics
- Algorithms for Solving Rubik's Cubes
- Experimental semi-autonomous eigensolver using reinforcement learning