Hoe kun je op quantumwijze getallen vinden in een rij die kleiner zijn dan getal k

[sensor]

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!

[physicalattraction]

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.

[Gast]

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.

[sensor]

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

Ik kan iedereen aanbevelen enige tijd te besteden aan het programmeren van quantumcomputers. Er komen heel veel disciplines samen.

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,

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.