arXiv:2109.07199 · Journal of Physics A Mathematical and Theoretical

Solving Rubik’s cube via quantum mechanics and deep reinforcement learning

Sebastiano Corli, Lorenzo Del Moro, Davide Emilio Galli, Enrico Prati

Published Sep 10, 2021• 10 citations

Abstract

Abstract Rubik’s cube is one of the most famous combinatorial puzzles involving nearly 4.3 × 10 19 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 described by 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 symmetries which 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.

DOI: 10.1088/1751-8121/ac2596

Related papers

Casting Rubik’s Group into a Unitary Representation for Reinforcement Learning

Sebastiano Corli, Lorenzo Del Moro, Davide Emilio Galli +1 more

Abstract Rubik’s Cube is one of the most famous combinatorial puzzles involving nearly 4.3 × 1019 possible configurations. However, only a single configuration matches the solved one. Its mathematical description is expressed by the Rubik’s group, whose elements define how its layers rotate. We develop a unitary representation of the Rubik’s group and a quantum formalism to describe the Cube based on its geometrical constraints. Using single particle quantum states, we describe the cubies as bosons for corners and fermions for edges. By introducing a set of four Ising-like Hamiltonians, we managed to set the solved configuration of the Cube as the global ground state for all the Hamiltonians. To reach the ground state of all the Hamiltonian operators, we made use of a Deep Reinforcement Learning algorithm based on a Hamiltonian reward. The Rubik’s Cube is successfully solved through four phases, each phase driven by a corresponding Hamiltonian reward based on its energy spectrum. We call our algorithm QUBE, as it employs quantum mechanics to tackle the combinatorial problem of solving the Rubik’s Cube. Embedding combinatorial problems into the quantum mechanics formalism suggests new possible algorithms and future implementations on quantum hardware.

Journal of Physics Conference SeriesJun 1, 20235 citations

Exploring fixed points and eigenstates of quantum systems with reinforcement learning

María Laura Olivera-Atencio, Jesús Casado-Pascual, Denis Lacroix

We introduce a reinforcement learning algorithm designed to identify the fixed points of a given quantum operation. The method iteratively constructs the unitary transformation that maps the computational basis onto the basis of fixed points through a reward-penalty scheme based on quantum measurements. In cases where the operation corresponds to a Hamiltonian evolution, this task reduces to determining the Hamiltonian eigenstates. The algorithm is first benchmarked on random Hamiltonians acting on two and three qubits and then applied to many-body systems of up to six qubits, including the transverse-field Ising model and the all-to-all pairing Hamiltonian. In both cases, the algorithm is demonstrated to perform successfully; in the pairing model, it can also reveal hidden symmetries, which can be exploited to restrict learning to specific symmetry sectors. Finally, we discuss the possibility of post-selecting high-fidelity states even when full convergence has not been reached.

quant-pharXiv:2511.17491Physical Review ResearchNov 24, 20250 citations

Reinforcement Learning with Deep Quantum Neural Networks

Wei Hu, James Lee Hu

The advantage of quantum computers over classical computers fuels the recent trend of developing machine learning algorithms on quantum computers, which can potentially lead to breakthroughs and new learning models in this area. The aim of our study is to explore deep quantum reinforcement learning (RL) on photonic quantum computers, which can process information stored in the quantum states of light. These quantum computers can naturally represent continuous variables, making them an ideal platform to create quantum versions of neural networks. Using quantum photonic circuits, we implement Q learning and actor-critic algorithms with multilayer quantum neural networks and test them in the grid world environment. Our experiments show that 1) these quantum algorithms can solve the RL problem and 2) compared to one layer, using three layer quantum networks improves the learning of both algorithms in terms of rewards collected. In summary, our findings suggest that having more layers in deep quantum RL can enhance the learning outcome.

Journal of Quantum Information ScienceJan 1, 201913 citations

Reinforcement learning enhanced quantum-inspired algorithm for combinatorial optimization

Dmitrii Beloborodov, Alexander E. Ulanov, Jakob Foerster +2 more

Quantum hardware and quantum-inspired algorithms are becoming increasingly popular for combinatorial optimization. However, these algorithms may require careful hyperparameter tuning for each problem instance. We use a reinforcement learning agent in conjunction with a quantum-inspired algorithm to solve the Ising energy minimization problem, which is equivalent to the Maximum Cut problem. The agent controls the algorithm by tuning one of its parameters with the goal of improving recently seen solutions. We propose a new Rescaled Ranked Reward (R3) method that enables a stable single-player version of self-play training and helps the agent escape local optima. The training on any problem instance can be accelerated by applying transfer learning from an agent trained on randomly generated problems. Our approach allows sampling high quality solutions to the Ising problem with high probability and outperforms both baseline heuristics and a black-box hyperparameter optimization approach.

arXiv:2002.04676Machine Learning Science and TechnologyOct 20, 202018 citations

What we can do with one qubit in quantum machine learning: ten classical machine learning problems that can be solved with a single qubit

Manuel Pegalájar Cuéllar

This work focuses on quantum machine learning and analyzes the power of one single qubit to solve classical machine learning problems. We explore possible strategies to address traditional supervised, unsupervised, and reinforcement learning tasks. In particular, we study binary and multinomial classification, regression problems, time series forecasting, clustering, and quantum reinforcement learning. Our results suggest that the same methodology could be used to address all three types of learning with different measurement strategies and, despite the strong limitation of reduced data dimensionality of the candidate problems, a single qubit can achieve similar or even improved performance with respect to state-of-the-art classic machine learning methods in many cases. As simulating the evolution of one qubit state is computationally efficient, our study enables the possibility to use the qubit model as a candidate solution to implement simple decision-making machine learning models in hardware with extremely low memory resources such as embedded systems or edge devices. The outcomes provided could be also of interest in academia and for the construction of demonstrators using low-scale contemporary quantum hardware.

Quantum Machine IntelligenceNov 12, 20248 citations

A framework for deep energy-based reinforcement learning with quantum speed-up

Sofiène Jerbi, Hendrik Poulsen Nautrup, Lea M. Trenkwalder +2 more

In the past decade, deep learning methods have seen tremendous success in various supervised and unsupervised learning tasks such as classification and generative modeling. More recently, deep neural networks have emerged in the domain of reinforcement learning as a tool to solve decision-making problems of unprecedented complexity, e.g., navigation problems or game-playing AI. Despite the successful combinations of ideas from quantum computing with machine learning methods, there have been relatively few attempts to design quantum algorithms that would enhance deep reinforcement learning. This is partly due to the fact that quantum enhancements of deep neural networks, in general, have not been as extensively investigated as other quantum machine learning methods. In contrast, projective simulation is a reinforcement learning model inspired by the stochastic evolution of physical systems that enables a quantum speed-up in decision making. In this paper, we develop a unifying framework that connects deep learning and projective simulation, opening the route to quantum improvements in deep reinforcement learning. Our approach is based on so-called generative energy-based models to design reinforcement learning methods with a computational advantage in solving complex and large-scale decision-making problems.

Oct 28, 20194 citations