D-Wave Systems breaks the 1000 qubit quantum computing barri

[zullil]

Are we talking about solving chess theoretically (all the moves, all the lines) or practically? I don't need to know, for example, if 1. f3 holds, or if it's a black win, because I wouldn't play it anyway.

[d]rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1

As soon as we know that this is draw with correct play we'll let you know.

[Jesse Gersenson]

(38^5500)

Code: Select all

64532931270784997255072947271902112972253434591521878478176684793280
83233346245983777484700548222579590474919634131921907568236244639585
38950437386863558987375939008618701969023057370762168941824144730764
57314534443031758637010758155504244539579448658810742196151207892406
69738800395346786623650138621966233264056371061888162206595654904617
70749054574638904045551342488051710975875375773308106698344015161330
46475221034078741450265004225947815174889333373811176946202044314073
14463500754762140490877085118712175229110297568870110926677724279200
74294562973580487689993064486182738104346895916106553706625650537321
74976143147162016488510485509052723945903417825388644249809533981634
33123017112279981293501245407437627562819365782749367378098668202593
18867441995367850609283388654862128369631946990281155130916703160771
27591903118863121892151900018993081192123574125177034147329996652633
13210217614249970714300496270095017748395862139334606464172521589437
71742410210091924410828271759778918653642135770605203463575508538135
75444304728423627025733028242872533093277446483934161063651047452738
01461699319155714676573076752046227007788202325605672573463127531511
62316612706933773323284814431099776830193956289277253223245551547317
19539300742354123447202720167345929398513453649436058292665108294566
24397883340295161401480036980210893459840221415411772723950838176413
87156400796808259625203740337496153169783521299880320543661029469620
99424761193014300626316658436369093425450846501915652821799841924679
35996702199900346234201433173527975697845639774265476369014144028409
09073793328629770427228880459590805078274219708846191256527261092533
87544051382745374751963910137430093635242684550125636439262750613218
97985699973654717267776138374023582074778168339699314428234354995416
57890706371642676220460816236402880219757718089891068492336803512978
55001726239426983665649026493603441697195600098845354051046191441516
49934596123845201919626772892026715691147111941129333678255284217137
68151849086224779150826154769244400463583335413191337320270150883569
40076673794741879193079751396612205852221485089288071324630431215753
84729610895421300416704462420790020802988198919843544357285682496507
83624032089683866477613091667118500237485546165492532223497766304469
96596927188807445476059765075084263740103601668153355210439784886459
84400498483300464599349323356978658492313378672364954938072784114259
08256260431153119416050308012022742306185319254418894281073441324366
59339996754264525514940046129695590553999496450076337184035951459113
87906273629458170136887316985993705051576039778949191082175097138702
72103544805377247543408291000971445404403975093403406168621595346341
76737765567796582224906959991080986683636366295729861699352078083517
10088968908275340908921746106232333463250372547699788478110060927704
56751350193704801264726816720406014732004169220653434081372261862850
87464110042480528432632556103114080733157113665234428163980045216857
83375228626180225753624918390962318862596362727182790470633035246685
33286229940930371042646919679672414855808159593056696754344761391199
82324023249002933332814810497878512230994206559117460980026541830047
56976004022705952321871073582718669038248887221749152643590419351447
37095407591745682722836006206022799569658492224772184943590238147705
03955497498709485987162755453372082946310660728783286157895802522936
06103136653440286491209672850052075583858671886160826922584231479430
11161723530644185351702045455541879987344553872634460243061483836163
65065802603515342023124648025673399262658909405684243867626602722918
51468181828264865733326022482921272087512196636524616268618885682753
94179336855935231857169711490873629519819887584833992523510967828224
02187631402741137941239528054081153958472816799119930518873716458738
55048753142039164232244147050851124409631300977880723589183591621165
25916647686323845235714348470919190698212520186755785906681268510435
49701656866979364011452909809028625036636307261047745426205360127675
82508537577477719259176870709729889856613946835939941606077420471553
13642206250337408512518607519157720791309762333539750093981843205826
83254762071217781544547366608610092927230204043302647175907182624143
48598820156608364015626094570684633299106566306155866949094422943294
32110776029568777074543721110781045931844714019841790978924991712706
73860870062342508162863493587494601533469623027617003203910766328246
12942511805040345158299437586431871289250269240562005751865817188148
68472165149400193515435839323852966270292133873030696012826942007260
31365880505390087786739724235428328930902198757402605021185329781606
76632866588344995863761416436469585633115493797278135201969179945493
42221220996455585403483892873960406505115241024955240102392308464233
14415284476892033308705398332156203026904129933191862371313344743530
27701624982346742115732240474185612161486364983228280807878972228484
75084688679146758808296762450546638038553418727244217505272460947840
38673618026426794757295419797924748928165458785182406048481997457547
19154652000414195037324752482391147589899362442072181403541790918669
62310371665979801804964042988214384898920195198354193632453606922351
75303999502982036753233652450151623203767189742187077314385632318706
10873934873105233062315704495197142266725757565408005171294158690441
99031739375153723017634846413315385845971748812394671865517672654211
73549568018841909843429096910332439899727773728826885485571100796948
76531020105870787990434110950018797901499640063138390500788687102516
73709853600391933881594165306224859980940770499136158189353282144313
63569364814684054306154642107269804377983449078900516642475593176227
87512632309012538957575967998518097677023986203192675748133436362765
65467189410749343967069409930019289458601127756235734880736582474834
22000335416436660139821732943090440028407419989107790627267076714569
00110496084019198541823375725043447500771781565981304350046178312952
27185267398882970233167542711322395649888045100356112772813329543527
76216964331714938694237129289155409977030269943371914326057398178100
66058147402909987720905001872003684502417387677294019475459117197291
04843842814499821002180060915834902675385359737116562230227061600653
42377098304661643632595077899297400262978845605555760355810824018504
63965792922615541141698120211385374559254663409023945695524737500673
36242775886272589600469228575425822981412848251220227276058198223729
39340682177098912353716557512371988022883900799223613145036885343286
53551774999184367023131290928818950178839917349147081319661251366953
24175948489026979893247512687881651531872095656330491030060824729089
41027392378411501019997771145383730896777246302106137702535595146456
05958936008469433550339400688522670501863418075975050482719234553286
21503229296468230687165833299568652723094229608759063635343979518120
05875016362316736356228955048697694781503320831862209237951240639019
84725719811847731368969873603182723333882434848278472603842407431313
84172764122168084634555384218466289381184131743165359595417361511472
34719441228128652844504406394831374275423368906921583639731749667645
78924029447782853998182107236086390098614940631090122130618831276976
12974561583266841337640278898538417465883456670907388074135165339982
25620754347487098151157804780015023027951794246700835172773630558232
48679874057589460085458235735726193447973219891741383364736783888361
11472098480439761064466884205034215223351145307941726923018450694047
26986089615723548903858293978590189484854314969940470240162560628142
10317360348766644838194803054442753613578817783564254965573691605260
37672260042947790643690830856239706239051213980085086195467662957005
97237537681978358153054221417487559373118271579066420664580540785760
62139144046628885413815197566344482085775824384882369961164853550067
15602601124289858879104807044769894065906072977566615340710172727910
18180542101708262545178946907981491922831231919119057324963150259005
19104921264280412218406368309992871760214395759355518106783220471952
63900287284154887694182908757755824903773568410478464244017985928122
87007797934890231756553514200854322811048369687440940355931390693475
44349355141874144092594621794408422849272207322349733258840973624136
51499437092623844483373168741292757853328578959025014555404229858465
76847603019344027431363452291144762287531456735635580900882635546194
25608385453789547587053571014573452939423414936926285352350798386616
59082203869890110996721953407088848779234796915900356385168580211270
04802269625083208180647517940989719690184446661454195588213216966449
95631915337738857537522755094493393827270418915080066969243967483782
16252896737015954750589412411088956219684512439592709146957789720501
08003177848257637370140064656907064481975469024521889310934780919427
78103877548969836316850807142144192493125768499429376

[Vinvin]

(38^5500)

...

Or, from my windows calculator : 6,4532931270784997255072947271902e+8688

[bob]

See http://www.kurzweilai.net/d-wave-system ... ng-barrier

At 1000 qubits, the new processor considers 2^1000 possibilities simultaneously, a search space which dwarfs the 2^512 possibilities available to the 512-qubit D-Wave Two. ‪”In fact, the new search space contains far more possibilities than there are ‪particles in the observable universe.”

D-Wave is mentioning some applications here, http://www.dwavesys.com/quantum-computing/applications

I was wondering if some of them could be bent to target chess.
So far, I was sure I would never see chess solved in my lifetime. With quantum computers gaining traction, I'm not so sure anymore.

Two thirds voted never?! Is this the nineteenth or twenty-first century?

Before quantum computing will have any impact on chess programming it will be solved by other means so the answer to the poll is 'never'.

I'm not so sure it will ever be solved by any means. To solve it, ALL paths have to be searched to an endpoint conclusion of some sort. That is an absolutely impossible number of nodes thanks to the rules of the game (50 move rule is one issue). With the longest possible game something like 5500 moves, alpha/beta would choke on sort(38^5500) nodes. I don't even know how one would think about storing such a thing while searching it.

No machine present has the potential and programming may have to start from scratch when a quantum computer with the potential is created.

I think a machine with the potential may be created well before 2050.

Even with quantum computing, I don't see how such a tree is going to be searched in parallel or stored (38^5500 positions)...

[bob]

Are we talking about solving chess theoretically (all the moves, all the lines) or practically? I don't need to know, for example, if 1. f3 holds, or if it's a black win, because I wouldn't play it anyway.

Normally "solve" means to find the best move in any position. Which means that you would have to search f3 as well as everything else, even if e4 wins, since f3 might win quicker...

Just showing that e4 wins is a weaker solution, but one that would be good enough I suppose.

[Dirt]

Code: Select all

64532931270784997255072947271902112972253434591521878478176684793280
...
78103877548969836316850807142144192493125768499429376

That's a bit of an upper bound, though. I've seen estimates of 10^46 or so possible positions, which it may be possible to build a database for. It would be at least Ceres sized, and perhaps as large as the Earth. Actually calculating the data would take a non-trivial amount of time.

It's probably best to make something like a 26 piece tablebase and solve chess from that, It still looks too hard to bother with just for a game.

[Terry McCracken]

See http://www.kurzweilai.net/d-wave-system ... ng-barrier

At 1000 qubits, the new processor considers 2^1000 possibilities simultaneously, a search space which dwarfs the 2^512 possibilities available to the 512-qubit D-Wave Two. ‪”In fact, the new search space contains far more possibilities than there are ‪particles in the observable universe.”

D-Wave is mentioning some applications here, http://www.dwavesys.com/quantum-computing/applications

I was wondering if some of them could be bent to target chess.
So far, I was sure I would never see chess solved in my lifetime. With quantum computers gaining traction, I'm not so sure anymore.

Two thirds voted never?! Is this the nineteenth or twenty-first century?

Before quantum computing will have any impact on chess programming it will be solved by other means so the answer to the poll is 'never'.

I'm not so sure it will ever be solved by any means. To solve it, ALL paths have to be searched to an endpoint conclusion of some sort. That is an absolutely impossible number of nodes thanks to the rules of the game (50 move rule is one issue). With the longest possible game something like 5500 moves, alpha/beta would choke on sort(38^5500) nodes. I don't even know how one would think about storing such a thing while searching it.

No machine present has the potential and programming may have to start from scratch when a quantum computer with the potential is created.

I think a machine with the potential may be created well before 2050.

Even with quantum computing, I don't see how such a tree is going to be searched in parallel or stored (38^5500 positions)...

We'll have to wait and see. With a massive quantum computer it should be doable but such a machine has to be created first.

We might have AGI before we have such a quantum monstrosity. Then I will be more concerned, if I'm still around, what the AGI could do. A hell of a lot more than us.

[Dann Corbit]

See http://www.kurzweilai.net/d-wave-system ... ng-barrier

At 1000 qubits, the new processor considers 2^1000 possibilities simultaneously, a search space which dwarfs the 2^512 possibilities available to the 512-qubit D-Wave Two. ‪”In fact, the new search space contains far more possibilities than there are ‪particles in the observable universe.”

D-Wave is mentioning some applications here, http://www.dwavesys.com/quantum-computing/applications

I was wondering if some of them could be bent to target chess.
So far, I was sure I would never see chess solved in my lifetime. With quantum computers gaining traction, I'm not so sure anymore.

Two thirds voted never?! Is this the nineteenth or twenty-first century?

Before quantum computing will have any impact on chess programming it will be solved by other means so the answer to the poll is 'never'.

I'm not so sure it will ever be solved by any means. To solve it, ALL paths have to be searched to an endpoint conclusion of some sort. That is an absolutely impossible number of nodes thanks to the rules of the game (50 move rule is one issue). With the longest possible game something like 5500 moves, alpha/beta would choke on sort(38^5500) nodes. I don't even know how one would think about storing such a thing while searching it.

No machine present has the potential and programming may have to start from scratch when a quantum computer with the potential is created.

I think a machine with the potential may be created well before 2050.

Even with quantum computing, I don't see how such a tree is going to be searched in parallel or stored (38^5500 positions)...

We'll have to wait and see. With a massive quantum computer it should be doable but such a machine has to be created first.

We might have AGI before we have such a quantum monstrosity. Then I will be more concerned, if I'm still around, what the AGI could do. A hell of a lot more than us.

The entire tree does not have to be searched if there is a forced mate that is closer.
Suppose (for instance) that there is a forced mate in 200.
In such a case, 38^200 nodes would be all that are needed.

For some algorithms (e.g. factoring a number) a quantum computer can change NP into P.

A 1000 qubit quantum computer makes RSA and other cryptography schemes unsafe. Since it is not unlikely that our banks use RSA variants, that is something to actually worry about (should a malevolent person gain access to such a computer). The factoring algorithm does not simply try every possible factor, but instead utilizes properties of modular arithmetic.
https://en.wikipedia.org/wiki/Shor%27s_algorithm

The number 56,153 was factored on a quantum computer with 4 qubits.
Nikesh S. Dattani and Nathaniel Bryans. "Quantum factorization of 56153 with only 4 qubits."

Quantum computers also have a special black box search algorithm, but it only reduces search effort to sqrt(nodes).
https://en.wikipedia.org/wiki/Grover%27s_algorithm

It remains to be seen if there exists any algorithm which can turn chess search into P from NP. But until Shor's algorithm, factoring was assumed to be NP (exponential as a function of the number of bits of the product of two large primes).

[Dann Corbit]

New quantum search algorithm:
"Quantum search algorithm tailored to clause satisfaction problems"
Avatar Tulsi

[mvk]

In the practical sense, I conjecture that chess will be solved first by a heuristic searcher, running on conventional digital computers, that can't be beaten anymore (that is: the draw rate reaches 100.000%). After that, people will lose all interest in the topic, no matter any further technological advances in computing machinery.