Vi studerar kvantalgoritmer på sökträd av okänd struktur, i en modell där trädet kan upptäckas genom lokal utforskning. Det vill säga, vi ges roten av trädet och tillgång till en svart låda som, med tanke på en vertex v, utgångar barnen i v. Vi konstruerar en kvantalgoritm som, med tanke på sådan tillgång till ett sökträd av djup som mest n, uppskattar storleken på trädet T inom en faktor av 1 ± δ i Õ( ε nT ) steg. Mer allmänt kan samma algoritm användas för att uppskatta storleken på riktade acykliska grafer (DAG) i en liknande modell. Vi visar sedan två tillämpningar av detta resultat: a) Vi visar hur man omvandlar en klassisk bakåttracking sökalgoritm som undersöker T noder av ett sökträd till en Õ ( ε Tn 3/2 ) tid kvantalgoritm, förbättra över en tidigare kvant baktracking algoritm av Montanaro (arXiv:1509.02374). b) Vi ger en kvantalgoritm för att utvärdera AND-OR-formler i en modell där formeln kan upptäckas genom lokal undersökning (modellering av positionsträd i 2-spelarspel) som utvärderar formler av storlek T och djup T o(1) i tid O(T 1/2+o(1) ). Således är kvanthastigheten i huvudsak samma som i fallet när formeln är känd i förväg.
I REF studeras kvantalgoritmer för problemet.
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Physics', 'Computer Science']}