Scientists theoretically analyzed quantum algorithm for playing “Magic square” and showed that even a small noisy quantum computers can outperform classical counterparts. The work presented in the journal Nature Physics.
Theoretically quantum computers can solve many important tasks effectively, while the classic devices you will need an exponentially large time to solve them. However, most of today’s quantum computers are not powerful enough to show the superiority in solving any useful tasks.
Last year Google managed to demonstrate the clear superiority of the solution by chance emulation of the quantum circuit, but such a task cannot be considered very useful. Besides, it was used for a very powerful quantum computer. Since then, scientists are actively looking for challenges, to find effective solutions to them are quite modern noisy and not very large quantum devices.
Scientists from IBM research centers in Australia, Germany, Canada and Singapore under the leadership of Professor Marco Romanichel (Marco Tomamichel) investigated quantum supremacy with the help of mathematical game “Magic square”.
In this game, two participants filled square numbers +1 and -1. One of the players must randomly choose a string and fill it with numbers so that the number -1 is an even number, the other player at this time, flooding is a random column, so that the number -1 was odd. Players do not know which column (row) selected by another player. The numbers that appear at the intersection of row and column, multiplied together — the goal is to fill the square so that at least one cell gave +1. It is obvious that either both players win or lose.