QMaze : Quantum Ray Tracing

Inspiration - Inspiration

Ray tracing is one of the most expensive things a computer can do, and at its core, it's just a search problem. Grover's algorithm cuts search time from O(N) to O(√N). We wanted to see if that actually meant something in practice, not just on paper.

Ray tracing est l’un des algorithmes les plus coûteux qu’un ordinateur puisse exécuter, puisqu’il s’agit d’un problème de recherche. L’algorithme de Grover permet de réduire le temps de recherche de O(N) à O(√N). Nous voulions vérifier si cela pouvait se traduire concrètement sur le plan expérimental, et non seulement en théorie.

What it does - Qu'est-ce qu'il fait

Places a circular target randomly in a 2D world, fires 16 rays at it, and uses Grover's algorithm to find which ray hits without checking them one by one. A classical solver runs at the same time so you can compare both results visually.

Il met en place une cible aléatoirement dans un plan 2D, il tire 16 rayons envers la cible, et ensuite l'algorithme de Grover trouve lequel des rayons frappe la cible, sans vérifier un par un chacune d'entre elles. Un solveur classique s’exécute en parallèle afin de pouvoir comparer visuellement les deux résultats.

How we built it - Comment on l'a crée

We converted the intersection math into fixed-point integer arithmetic so the oracle could be built entirely from quantum gates. The circuit uses a QFT-based adder to evaluate the hit condition in superposition across all 16 rays. Ran everything on Qiskit's AerSimulator.

Nous avons converti les calculs d’intersection en arithmétique entière à virgule fixe afin que l’oracle puisse être entièrement implémenté à partir de portes quantiques. Le circuit utilise un additionneur basé sur la QFT pour évaluer la condition d’intersection en superposition sur les 16 rayons. Nous avons exécuté le tout sur l’AerSimulator de Qiskit.

Challenges we ran into - Défis rencontrés

Reversibility was the main headache. Every intermediate calculation has to be undone after use or the ancilla qubits get corrupted. Getting the integer scaling right so nothing overflowed the accumulator also took way longer than expected.

La réversibilité a été le principal défi. Chaque calcul intermédiaire doit être annulé après utilisation, sinon les qubits ancillaires sont corrompus. Ajuster correctement l’échelle des entiers pour éviter tout dépassement de capacité dans l’accumulateur a également pris beaucoup plus de temps que prévu.

Accomplishments that we're proud of - Réalisations dont nous sommes fiers

The thing works. After 3 Grover iterations, the correct ray consistently comes out above 90% probability. Writing a working arithmetic oracle from scratch, with no carry ancilla, was something none of us had done before and honestly did not expect to finish.

Le système fonctionne. Après 3 itérations de Grover, le bon rayon apparaît de manière constante avec une probabilité supérieure à 90 %. Concevoir un oracle arithmétique fonctionnel à partir de zéro, sans qubits ancillaires de retenue, était quelque chose que nous n’avions jamais fait auparavant et que nous ne pensions honnêtement pas réussir à terminer.

What we learned- Ce que nous avons appris

Quantum arithmetic is way harder than quantum search. One line of classical code can take 30 gates to implement reversibly. Complexity class and real runtime are also very different things, which this project made obvious.

L’arithmétique quantique est beaucoup plus complexe que la recherche quantique. Une seule ligne de code classique peut nécessiter 30 portes pour être implémentée de manière réversible. Les classes de complexité et le temps d’exécution réel sont également très différents, ce que ce projet a clairement mis en évidence.

What's next for Quantum ray tracing - Prochaines étapes pour le ray tracing quantique

Multiple objects and 3D would be the natural next step. A more realistic direction is probably hybrid classical-quantum, using Grover to search something like a BVH tree rather than brute force ray-object pairs.

Ajouter plusieurs objets et passer à la 3D serait l’étape suivante naturelle. Une direction plus réaliste serait probablement une approche hybride classique-quantique, utilisant l’algorithme de Grover pour explorer une structure comme un arbre BVH plutôt que de tester de manière brute toutes les paires rayon-objet.

Built With

• python
• qiskit