search

qiskit-community / qiskit-camp-asia-19

31 stars 7 forks source link

Solving Eternity II puzzle by quantum reinforcement learning inspired approach #18

Open asa-eagle opened 5 years ago

asa-eagle commented 5 years ago

Abstract

The Eternity II puzzle is an edge-matching puzzle which involves placing 256 square pieces into a 16 by 16 grid, constrained by the requirement to match adjacent edges. It has been designed to be difficult to solve by brute-force computer search. So why don’t we try solving it with a Quantum computer?

image1

Description

The Eternity II puzzle is an edge-matching puzzle which involves placing 256 square pieces into a 16 by 16 grid, constrained by the requirement to match adjacent edges. This puzzle was released on 28 July 2007 and a $2 million prize was offered for the first complete solution.
The competition ended at noon on 31 December 2010, with no solution being found.

According to Wikipedia, “It has been designed to be difficult to solve by brute-force computer search.” So why don’t we try solving it with a Quantum computer?

I know the quantum computer is not powerful enough yet so I’m thinking to start from small model. (like 16 pieces) Actually I tried this small model with quantum annealer (https://qiita.com/AsaEagle/items/2cdb524cd762eae12992) but this time thinking about using quantum reinforcement learning. Let’s find a better algorithm for this puzzle and the break of number of pieces for solving this problem in the future!

Members

Deliverable

GitHub repo

kumagaimasahito commented 5 years ago

Hi! I usually study combinatorial optimization problems, so I think this topic is so familiar with me. Can I take part in this group, as CS?

martian17 commented 5 years ago

I'm interested in this one CS major

kobashuu commented 5 years ago

Hi! I'm undergraduate student from Tokyo. I'm beginner at qiskit but interested in optimization problems. Can I join in?

asa-eagle commented 5 years ago

@kumagaimasahito of-course! you are welcome! @martian17 @kobashuu everebody is welcome!

manato438 commented 5 years ago

Hello, I'm Manato Akiyama from Japan. I also interested in this topic! Can I join?

yk-nt commented 5 years ago

I'm interested in this, I'm studying at quantum cryptography but I'm beginner at qiskit. I want to join.

asa-eagle commented 5 years ago

@manato438 @yukin07 sure!

yukidmy commented 5 years ago

I'm a master student in CS field and a very beginner at qiskit. I want to join this project but is it already full?

y4izus commented 5 years ago

Sorry, this group is already full, we should confirmed that the people already assigned is still interested on be part of this project before add anyone else

FumiakiAzegami commented 5 years ago

Will join

asa-eagle commented 5 years ago

This is our code (Including some result so it takes a while to open it..) https://github.com/asa-eagle/eternity/blob/master/eternity2_sampling_result7.ipynb

asa-eagle commented 5 years ago

Updated the code https://github.com/asa-eagle/eternity/blob/master/eternity2_sampling_result8.ipynb

asa-eagle commented 5 years ago

Our presentation https://github.com/asa-eagle/eternity/blob/master/presentation.pdf