Hoe kun je op quantumwijze getallen vinden in een rij die kleiner zijn dan getal k
Moderator: physicalattraction
-
- Berichten: 337
Hoe kun je op quantumwijze getallen vinden in een rij die kleiner zijn dan getal k
Gegeven een positief getal k en een rij of lijst met integer getallen. Zoek de nummers in de lijst met getallen die kleiner zijn dan k. Begin met een rij getallen op volgorde.
Bijvoorbeeld
def kleiner_dan_k (k, list[]):
return result
print(kleiner dan k(3, [0,1,2,3,4,5,6,7])
0,1,2
Quantum algoritme!
Bijvoorbeeld
def kleiner_dan_k (k, list[]):
return result
print(kleiner dan k(3, [0,1,2,3,4,5,6,7])
0,1,2
Quantum algoritme!
- Moderator
- Berichten: 4.135
Re: Hoe kun je op quantumwijze getallen vinden in een rij die kleiner zijn dan getal k
Dat is een "big ask" om zo een quantum algoritme te vragen! Ik heb ooit een paar weken gespendeerd aan het begrijpen van quantum computing in het algemeen, en het factorisatiealgoritme specifiek. Ik zou niet zomaar een quantum algoritme kunnen schrijven.
- Berichten: 362
Re: Hoe kun je op quantumwijze getallen vinden in een rij die kleiner zijn dan getal k
Dit is een soort van sorteren, zie hier een paper over quantum sorting algoritmes.
Het best haalbare volgens deze auteurs is blijkbaar een orde Omega(n log(n)) algoritme, klassieke algoritmes kunnen ook lineair zijn (Radix Sort). Wellicht kan dat beter als je alleen de laagste zoveel elementen nodig hebt, maar dat weet ik niet.
Het best haalbare volgens deze auteurs is blijkbaar een orde Omega(n log(n)) algoritme, klassieke algoritmes kunnen ook lineair zijn (Radix Sort). Wellicht kan dat beter als je alleen de laagste zoveel elementen nodig hebt, maar dat weet ik niet.
-
- Berichten: 337
Re: Hoe kun je op quantumwijze getallen vinden in een rij die kleiner zijn dan getal k
Ik kan iedereen aanbevelen enige tijd te besteden aan het programmeren van quantumcomputers. Er komen heel veel disciplines samen.physicalattraction schreef: ↑vr 12 apr 2024, 11:31 Dat is een "big ask" om zo een quantum algoritme te vragen! Ik heb ooit een paar weken gespendeerd aan het begrijpen van quantum computing in het algemeen, en het factorisatiealgoritme specifiek. I
Dit is een mooie oplossing er wordt gebruikt gemaakt van een binary tree search en een oracle. Ik zag echter niet zo in hoe dit te implementeren. Heb ondertussen wel iets gevonden wat gebruik maakt van het grover algoritme maar dan in een variant met een comparator:https://arxiv.org/pdf/quant-ph/0605003.
Er wordt gebruik gemaakt van een comparator circuit in een grover algoritme. In dit circuit wordt een bitcompartor gebruikt waarmee de grootste van twee qubits of twee getallen kan worden bepaald. Vervolgens kun je dit weer in een search algoritme stoppen. De inputs zijn dan de K parameter en de lijst. De lijst getallen wordt gemaakt met een paar H of Hadmardgates. Dit geeft een superpositie van een aantal states ofwel een rijtje getallen. Vervolgens wordt door de comparator alleen naar getallen kleiner dan de waarde k gekeken.