A quantum algorithm for ray casting using an orthographic camera

Universidade do Minho Escola de Engenharia Departamento de Inform´ atica Carolina Alves A Quantum Algorithm for Ray Casting using an Orthographic Camera December 2019 Universidade do Minho Escola de Engenharia Departamento de Inform´ atica Carolina Alves A Quantum Algorithm for Ray Casting using an Orthographic Camera Master dissertation Master Degree in Physics Engineering Dissertation supervised by Lu´ıs Paulo Santos December 2019 i DIREITOS DE AUTOR E CONDIC¸ ˜ OES DE UTILIZAC¸ ˜ AO DO TRABALHO POR TERCEIROS Este ´ e um trabalho acad´ emico que pode ser utilizado por terceiros desde que respeitadas as regras e boas pr´ aticas internacionalmente aceites, no que concerne aos direitos de autor e direitos conexos. Assim, o presente trabalho pode ser utilizado nos termos previstos na licenc¸a abaixo indicada. Caso o utilizador necessite de permiss˜ ao para poder fazer um uso do trabalho em condic¸ ˜ oes n˜ ao previstas no licenciamento indicado, dever´ a contactar o autor, atrav´ es do Reposit´ oriUM da Universidade do Minho. ACKNOWLEDGEMENTS This thesis would not have been possible without the help and guidance of Professor Lu´ ıs Paulo Santos, my supervisor, to whom I want to give a big thank you. I also want to thank my parents and my brother for all of their support throughout these course’s years. A kind thank you to my colleagues and friends who accompanied me across these years at university. Wishing you all the best. Lastly, I want to thank all the professors in this course for all of their work that, in one way or another, helped me and led me to this. This work is a result of project “SmartEGOV/NORTE-01-0145-FEDER-000037”, supported by the Norte Portugal Regional Operational Programme (NORTE 2020), under the PORTUGAL 2020 Partnership Agreement, through the European Regional Development Fund (EFDR). iii STATEMENT OF INTEGRITY I hereby declare having conducted this academic work with integrity. I confirm that I have not used plagiarism or any form of undue use of information or falsification of results along the process leading to its elaboration. I further declare that I have fully acknowledged the Code of Ethical Conduct of the University of Minho. ABSTRACT Quantum computing has the potential to provide better time complexities (than those achieved with classical computers) for challenging problems solved by classical computers or even provide a solution for problems out of reach of classical computers in terms of time complexity (where the time consumed for the resolution of the problem is not practical, e.g. thousands of years). Here we’re not solving an unsolvable problem but trying to improve its time complexity. There are several problems in rendering that are good candidates to being solved in a quantum fashion. Although previous research has proposed of theoretical ways of doing this, here we present a practical solution. This work takes a first step in applying quantum computing to one of the most fundamental operations in rendering: ray casting. This technique allows computing visibility between two points in a3D model of the world which is described by a collection of geometric primitives. The algorithm returns, for a given ray, which primitive it intersects closest to its origin. Without a spatial acceleration structure, the complexity for this operation is O(N). The main goal of this work is to use the Grover’s Algorithm, a quantum search algorithm based on amplitude amplification, to improve the complexity of this problem. This algorithm provides a quadratic speed up allowing for visibility evaluation for unstructured primitives in O(√N) steps. Due to technological limitations associated with current quantum computers we had to simplify our problem’s structure and in this work the geometrical setup is limited to rectangles and parallel rays (orthographic projection). Keywords: quantum computing, Grover’s algorithm, complexity, ray casting. RESUMO A computac¸˜ ao quˆ antica tem o potencial de proporcionar melhores complexidades temporais, do que aquelas alcanc¸adas por computadores cl´ assicos, para problemas exigentes resolvidos por estes ou at´ e proporcionar uma soluc¸˜ ao para problemas fora do alcance dos mesmos em termos de tempo consumido (onde o tempo necess´ ario para a resoluc¸˜ ao do problema n˜ ao ´ e pr´ atico, como por exemplo milhares de anos). N˜ ao estamos a tentar resolver um problema sem soluc¸˜ ao mas sim a tentar melhorar a sua complexidade. Existem v´ arios problemas de renderizac¸˜ ao que s˜ ao bons candidatos para serem resolvidos de forma quˆ antica. Apesar de existirem algumas propostas te´ oricas para alcanc¸ar isso mesmo, aqui ´ e apresentada uma soluc¸˜ ao pr´ atica. Este trabalho d´ a um primeiro passo em aplicar a computac¸˜ ao quˆ antica a uma das operac¸ ˜ oes mais fundamentais da renderizac¸˜ ao: ray casting. Esta t´ ecnica permite computar visibilidade entre 2pontos num modelo 3D do mundo que ´ e descrito por um conjunto de primitivas. O algoritmo retorna, para um dado raio, qual a primitiva que este interseta mais pr´ oxima da sua origem. Sem uma estrutura espacial de acelerac¸˜ ao, a complexidade desta operac¸ ˜ ao ´ eO(N). O principal objetivo desta dissertac¸˜ ao ´ e usar o algoritmo de Grover, um algoritmo quˆ antico de procura, para melhorar a complexidade deste problema. O algoritmo permite uma acelerac¸˜ ao quadr´ atica possibilitando uma avaliac¸˜ ao de visibilidade para primitivas n˜ ao estruturadas em O(√N)passos. Devido a limitac¸ ˜ oes tecnol´ ogicas associadas com os atuais computadores quˆ anticos, tivemos a necessidade de simplificar a estrutura do nosso problema e, neste trabalho, a configurac¸˜ ao geom´ etrica ´ e limitada a retˆ angulos e raios paralelos (projec¸˜ ao ortogr´ afica). Palavras-chave: computac¸˜ ao quˆ antica, algoritmo de Grover, complexidade, ray casting. CONTENTS 1 introduction 1 1.1Contributions 3 1.2Document Structure 3 2 state of the art/related work 5 3 quantum computing overview 7 3.1Fundamentals 7 3.1.1Qubits and Superposition 7 3.1.2Gates and Circuits 8 3.1.3Reversibility 11 3.1.4Measurements 11 3.2Grover’s Algorithm 12 4 ray casting 17 4.1Geometric setup and quantum circuits 17 4.1.1Geometric Setup 18 4.1.2Generating the bounds 19 4.1.3The oracle 21 4.1.4Inversion about the average 23 4.1.5Overall circuit 24 4.2Single Solution 25 4.2.1Algorithm 25 4.2.2Results 28 4.3Multiple Solutions 33 4.3.1Occlusion 34 4.3.2Visibility 40 4.4On a Real Quantum Machine 44 5 conclusion 48 5.1Prospect for future work 48 LIST OF FIGURES Figure 1Single qubit gates. Representation, as a quantum circuit, of the (a) X or NOT gate, (b) alternate representation of the X or NOT gate, (c) Z gate and (d) Hadamard gate. 9 Figure 2Two possible representations of the CNOT gate in a quantum circuit. 9 Figure 3Representation of the CZ gate in a quantum circuit. (a) Because both control and target qubits can be exchanged, both these representations can be used. (b) Since both qubits are exchangeable, we can also adopt this simpler representation. 10 Figure 4CNOT equivalent with 2Hadamards and 1CZ. 10 Figure 5Representation of the Toffoli gate in a quantum circuit. 11 Figure 6Initial state. 14 Figure 7Application of the oracle. 14 Figure 8Application of the diffusion operator. 15 Figure 915 Figure 10 15 Figure 11 Diagram of the cases of ray casting studied. 18 Figure 12 Geometric setup for the 2D or non-overlapping case. 19 Figure 13 (a) Quantum circuit for ”copying” a state (|0ior |1i), (b) quantum circuit representing an AND gate and (c) quantum circuit representing an OR gate. 20 Figure 14 Quantum circuit encoding the maxxcoordinates in the qubits bi.21 Figure 15 Quantum circuit for the oracle. 21 Figure 16 Quantum circuit for the Grover’s diffusion operator for the case of 3-qubit primitive indeces. 24 Figure 17 Quantum circuit of the algorithm. (iis not necessarily the same for p,band aux, it just represents that the quantum registers have multiple qubits) 24 Figure 18 Reference images obtained with the Qiskit simulator for the single solution case. The geometry in (a) is [(0, 1, 0, 1),(2, 2, 0, 3),(3, 3, 1, 1),(3, 3, 3, 3)] and in (b) is [(1, 3, 1, 2),(6, 6, 1, 4),(0, 3, 7, 7),(7, 7, 0, 0),(1, 2, 4, 5),(4, 4, 0, 2),(4, 4, 4, 7),(7, 7, 5, 7)] 29 Figure 19 Results retrieved with the Qiskit simulator for each pixel in the geometry [(0, 1, 0, 1),(2, 2, 0, 3),(3, 3, 1, 1),(3, 3, 3, 3)] with 2048 shots. 30 1.2. Document Structure 4 computing necessary to understand this work, like qubits, gates, quantum circuits, and a section describing Grover’s algorithm. Chapter 4is where we present the work we’ve done; a first section entails the more theoretical aspects our work and the next sections detail the results obtained. Finally, Chapter 5concludes this dissertation and provides some possibilities for future work. 2 STATE OF THE ART/RELATED WORK This chapter reviews some important work done regarding the theme of this dissertation. This work is based on the use of Grover’s Algorithm, a quantum search algorithm created in 1996 by Lov Grover [3]. In 2001, Andrew Glassner discussed quantum computing in his notebook [7–9] stating that anything involving searching for a minimum or maximum is a good candidate for quantum algorithms because Grover’s algorithm can speed this up significantly. He presents two possible contenders for this kind of technique, the first being the Z-buffer problem. To solve it, a superposition over all the polygons and respective depth would be created and Grover used to identify the minimum depth. The other contender is ray tracing and for this a superposition over all spheres and respective parameters (a,b,c)would be created; equation at2+bt +c=0 would then be solved simultaneously for all spheres and Grover used to locate the minimum positive t. For both problems a quadratic advantage is obtained over an unordered classical search. In their 2009 book [10], Marco Lanzagorta and Jeffrey Uhlmann describe the use of Grover’s algorithm for a number of computational geometry problems, including nearest neighbor queries, object-object intersection, Z-buffering, ray tracing, radiosity and level of detail, among others. In a more recent related work, Simona Caraiman [11] also proposes to apply Grover’s algorithm to the Z-buffer and ray tracing problems, including algorithms for both. Two important works for this dissertation are the ones used to solve the multiple solution occlusion and visibility problems. Michel Boyer et al. [12] present a way to determine the number of iterations of Grover’s algorithm necessary to achieve almost certainty of finding the answer when the number of solutions in unknown. They also present a way to count the number of solutions beforehand so that the number of times Grover’s algorithm needs to be applied is easily calculated. Durr and Hoyer [13] demonstrate a quantum algorithm for finding the minimum, which we’ll need to find the primitive with the minimum depth. A more practical and experimental work is the problem is addressed by Johnston [14]. The author performs pixel level supersampling by resorting to the quantum amplitude estimation algorithm to numerically integrate sub pixel samples through a combination of a quantum algorithm and a classical lookup table. This improved results compared to those 6 obtained with Monte Carlo integration for the same number of samples. These results are obtained using a simulator, an IBM five qubit machine, and a photonic quantum computer. This paper focused on supersampling pixels based on a known underlying signal, whereas our work computes this signal from a scene description. All the above cited works, except the last, maintain the discussion at the algorithmic and complexity analysis levels. No simulation, implementation or execution of the proposed algorithms is performed and no real experimental results are presented. In this dissertation we present an actual implementation and practical results for the ray casting problem. Our results are retrieved from the IBM Q Experience by IBM where they provide simulators for quantum machines and also real quantum machines where we can submit our circuits.1Other existing platforms of cloud-based quantum computing are Forest by Rigetti Computing, which includes a programming language, development tools and example algorithms.2, Azure by Microsoft which is a diverse set of quantum services, ranging from pre-built solutions to software and quantum hardware3, Quantum in the Cloud by The University of Bristol, which consists of a quantum simulator and a 4-qubit optical quantum system4, Quantum Playground by Google, which features a simulator with a simple interface, its own scripting language with debugging and 3D quantum state visualization features5, Quantum Inspire by Qutech6, Forge by QC Ware7, among others. 1https://www.ibm.com/quantum-computing/ 2https://www.rigetti.com/systems 3https://azure.microsoft.com/en-gb/services/quantum/ 4http://www.bristol.ac.uk/physics/research/quantum/engagement/qcloud/ 5https://opensource.google/projects/quantum-computing-playground 6https://www.quantum-inspire.com 7https://forge.qcware.com 3 QUANTUM COMPUTING OVERVIEW This chapter will present the notions in quantum computing necessary to understand this work. In a first section, the notions and properties of quantum computing will be addressed, alongside quantum gates and their representation. A second section will be dedicated to Grover’s algorithm. 3.1 fundamentals 3.1.1Qubits and Superposition Classical computers are made up of bits that, at any given moment, can represent a zero or a one. But a quantum computer works with qubits (quantum bits). The qubit is the basic unit of quantum information – the quantum version of the classical binary bit. A qubit can represent a zero or a one as well, but also a superposition of these two basis states. Thus, 1qubit can be in a superposition of 2states, 2qubits can be in a superposition of 4states, 3qubits in a superposition of 8states, etc. Each of these states has an associated amplitude. The probability of a state being measured is its amplitude squared, thus the sum of all the states’ amplitudes squared must equal to 1. |qi=α|0i+β|1i α,β∈C |α|2+|β|2=1 Generally speaking, if we have a quantum computer with nqubits, we have a superposition of N=2nbasis states (a classic computer can only be in one of these states at a single time): |Ψi=N−1 ∑ i=0 αi|ii αi∈C N−1 ∑ i=0|αi|2=1 3.1. Fundamentals 8 Any computational operation over this superposition will simultaneously act over the 2n states, in what is referred to as exponential quantum parallelism. This means that applying a function f(.)once to superposition |Ψieffectively results in a new superposition |Ψ0i containing all N=2nvalues of f(|Ψi). 3.1.2Gates and Circuits Whereas with classical circuits signals flow along the circuit, with quantum circuits, time flows along the circuit, from left to right – qubits do not flow, rather gate operations are applied onto the qubits. The building blocks of quantum circuits are quantum gates, like classical logic gates are for conventional digital circuits. In a quantum gate the number of input qubits is always the same as the output qubits because the operations have to be reversible (See section 3.1.3). A gate acting on nqubits is represented by a 2n×2nunitary matrix and the general quantum state of a qubit can be represented by a linear superposition of its two orthonormal basis states: |0i= 1 0 |1i= 0 1  These two orthonormal basis states span the two-dimensional linear vector (Hilbert) space of the qubit and are denominated the computational basis. A very simple quantum gate is the Pauli-X gate. This gate acts on a single qubit and is the equivalent of the NOT gate for classical computers. It maps |0ito |1iand |1ito |0i. It is also commonly designated as bit-flip and it’s represented by the Pauli-X matrix: X= 0 1 1 0  To obtain the result of a gate applied to a qubit we multiply the vector and the matrix. X|0i= 0 1 1 0  1 0 = 0 1 =|1i As we can see, the NOT gate changed the state |0ito |1i. Another Pauli gate is the Pauli-Z gate. This gate leaves the basis state |0iunchanged and maps |1ito −|1i. 3.1. Fundamentals 9 Z= 1 0 0−1  A very important quantum gate is the Hadamard gate. This gate also acts on a single qubit and it’s used to create superposition. Its matrix is the following: H=1 √2 1 1 1−1  It maps |0ito 1 √2(|0i+|1i)and |1ito 1 √2(|0i−|1i), which means that a measurement of this qubit has the same probability of yielding a 0 or a 1. The next figure shows the representation of the single qubit gates mentioned above: (a) (b) (c) (d) Figure 1: Single qubit gates. Representation, as a quantum circuit, of the (a) X or NOT gate, (b) alternate representation of the X or NOT gate, (c) Z gate and (d) Hadamard gate. Transitioning to 2-qubit gates, a crucial quantum gate is the Controlled-NOT (CNOT) gate (also known as Controlled-X gate). This gate acts by flipping the second qubit (target qubit) if and only if the first qubit (control qubit) is |1i. It is represented in Figure 2and its matrix is defined as: CNOT =       1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0        (a) (b) Figure 2:Two possible representations of the CNOT gate in a quantum circuit. 3.1. Fundamentals 10 There is also the Controlled-Z gate, presented in Figure 3, and, in this case, the control and target roles can be interchanged as this gate is symmetrical. It induces a sign shift for states where both qubits are |1i, thus any qubit can be said to be the control. Its matrix is given by: Controlled −Z=       1 0 0 0 0 1 0 0 0 0 1 0 000−1        (a) (b) Figure 3: Representation of the CZ gate in a quantum circuit. (a) Because both control and target qubits can be exchanged, both these representations can be used. (b) Since both qubits are exchangeable, we can also adopt this simpler representation. An important fact about these gates is that the CX (CNOT) operation can be described in terms of a CZ gate and 2Hadamard gates (Figure 4). The X gate can be decomposed as a sequence of three single qubit gates (2Hadamards and 1CZ) in the following way: X=HZH. Thus, the CX gate can be decomposed as: CX = (I⊗H)CZ(I⊗H). When the control is |0i, the two Hadamard gates cancel each other and, when it is |1i, the combination of gates acts as a NOT [15]. Figure 4:CNOT equivalent with 2Hadamards and 1CZ. Another very useful gate is the Toffoli gate. This gate acts on 3qubits and it’s also known as the CCNOT gate. It works like the CNOT but with 2control qubits; if both these qubits are set to |1i, the third qubit (target qubit) is inverted, otherwise it stays unchanged. This gate, presented in Figure 5, has to be constructed using the single and 2-qubit gates presented above and it can be used with ncontrol qubits. 3.1. Fundamentals 11 Figure 5:Representation of the Toffoli gate in a quantum circuit. 3.1.3Reversibility Quantum mechanics’ laws require that all operations performed on qubits be unitary and reversible. A unitary operation ensures that the norm of the vector of basis states coefficients αiis maintained and equal to 1 after the transformation; this is required since the vector of αi’s is in fact a probability distribution thus the sum of probabilities of all possible outcomes of any event always equals 1. No information gets lost on the transition from one configuration to another. Reversibility is a consequence of the unitary requirement and means that, given the outputs of the transformation, its inputs can be known. From the ending point we can reach the starting point: the computation is reversible. We can check if an operation is reversible by multiplying a matrix representing an operation by its conjugate transpose. If it equals the Identity matrix then the operation is unitary, and therefore, reversible. Summing up, a matrix Uis unitary if U×U†=U†×U=I. Checking with the Pauli-X matrix we can see that the operation is indeed reversible: X×X†= 0 1 1 0 × 0 1 1 0 = 1 0 0 1 =I Reversibility has several consequences at the circuit level: all quantum gates, which operate over qubits, must have the same number of inputs and outputs; this often results in circuits with a larger number of gates and more qubits than would be required of their classical counterpart. Information is never destroyed, since the computation can be reversed. 3.1.4Measurements Even though the quantum computation evolves on an exponentially large state space computing all solutions simultaneously, this space is not accessible. The superposition state holds until the moment of a measurement. When a measurement on the computational basis is made the result is always a zero or a one for each qubit. Measurements can be made using other bases using quantum gates to change the basis of the qubits. Upon measurement, the superposition |Ψicollapses into one basis state |ii, among all basis states 3.2. Grover’s Algorithm 12 included on |Ψi, with probability |αi|2. Contrary to quantum operations, a measurement is irreversible - all the information on the superposition is lost with a measurement and the register then behaves as classical data. The role of quantum algorithms is to maximize the probability of measuring the desirable states within a superposition and to postpone measurements (i.e., reading quantum data) until the last step of the algorithm. 3.2 grover’s algorithm Created in 1996 by Lov Grover [3], Grover’s Algorithm is a quantum algorithm that performs a search through an unstructured set of N=2nelements to find a unique item that satisfies a certain condition. It does this using just O(√N)operations which represents a quadratic gain over the O(N)complexity of a classical algorithm. Unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts, Grover’s algorithm provides ”only” a quadratic speedup. However, even quadratic speedup is considerable when Nis large. The search is called “unstructured” because we are given no guarantees as to how the database is ordered. If we were given a sorted database, for instance, then we could perform binary search to find an element in logarithmic time. Instead, we have no prior knowledge about the contents of the database. With classical circuits, we cannot do better than performing a linear number of queries to find the target element. Like many quantum algorithms, Grover’s algorithm is probabilistic. This means that it gives the correct answer with a probability of less than 1. Though there is technically no upper bound on the number of repetitions that might be needed before the correct answer is obtained, the expected number of repetitions is a constant factor that does not grow with N. The setup of the problem is as follows: For nqubits and N=2nelements, let f:{0, 1, ..., 2n−1} → {0, 1}such that f=     0 if x6=x∗ 1 if x=x∗ The algorithm returns, with high probability, the unique state x∗∈ {0, ..., N−1}: f(x∗) = 1. The first step of the Grover’s algorithm is to create a uniform superposition over all basis states by applying Hadamard gates on our qubits: 3.2. Grover’s Algorithm 13 |si=ˆ H|0i=1 √N N−1 ∑ x=0|xi The second step of the algorithm is to apply the oracle. The oracle is made up of unitary operations and is going to mark the state we want to find. It marks the state by flipping its amplitude. The oracle can be defined as a unitary matrix ˆ Othat acts on the states in the following way: ˆ O|xi= (−1)f(x)|xi We see that if |xiis an unmarked item, the oracle does nothing to the state. However, when we apply the oracle to the basis state |x∗i, it maps ˆ O|x∗i=−|x∗i. Thus, after applying the oracle, our superposition state looks like this: ˆ O|si=1 √N ˆ O N−1 ∑ x=0|xi=1 √N  ∑ x6=x?|xi!−|x?i  The superposition state stays the same except the state we want to find that has its amplitude negated. The next step is to increase this state’s amplitude. The procedure is called amplitude amplification and it raises the amplitude of the marked item, which shrinks the other items’ amplitude, so that measuring the final state will return the right item with near-certainty. This is performed by an operator ˆ Dcalled Grover’s diffusion operator. It is defined as: ˆ D=2|sihs|− ˆ I This algorithm has a nice geometrical interpretation in terms of two reflections, which generate a rotation in a two-dimensional plane. The only two special states we need to consider are the state we’re looking for, |x?i, and the uniform superposition |si. These two vectors span a two-dimensional plane in the vector space CN. The states |siand |x?iform a basis of this subspace but they’re not orthogonal, their inner product is 1 √2n. We can define a state |s00ithat is orthogonal with |x∗iby subtracting off the |x∗icomponent of |si. This way their inner product is zero. However, |s00iisn’t normalized, its inner product with itself isn’t equal to 1. This is how we get to |s0i, which it’s parallel to |s00i, and perpendicular to |x∗ibut has been normalized. 4.1. Geometric setup and quantum circuits 20 p1p0b3b2b1b0 P00 0 0 0 0 1 P10 1 0 1 0 1 P21 0 1 0 0 1 P31 1 1 1 1 0 Table 1:Table depicting the binary representation of the coordinates minxand the primitives Pi;pi are the qubits representing the indices of the primitives and biare the qubits representing the minx coordinates of the primitives. b3=P2+P3=p1p0+p1p0=p1 b2=P1+P3=p1p0+p1p0=p0 b1=P3=p1p0 b0=P0+P1+P2=p1p0+p1p0+p1p0=p1p0+p0=p1p0+p1p0+p0=p1+p0 The complexity of these operations was not studied in depth in this work although, in the future, its calculation is important to understand if it doesn’t lose the complexity advantage of Grover’s algorithm over classical search algorithms. After having this representation of minxencoded in the quantum register |bi, which we designate the bounds, it’s needed to represent this as a quantum circuit, and for that we need to build the quantum circuits equivalent to the above simplified Boolean expressions. (a) (b) (c) Figure 13: (a) Quantum circuit for ”copying” a state (|0ior |1i), (b) quantum circuit representing an AND gate and (c) quantum circuit representing an OR gate. In Figure 13 we see how we can build the quantum circuits to apply the Boolean operations necessary to represent the coordinates as Boolean expressions. The circuit in (a) is a CNOT gate and works by changing the target qubit to |1iif the control qubit is |1iand keeps the target qubit unchanged, meaning |0i, if the control qubit is |0i; note that both qubits become entangled, meaning that a transformation on one state will change the other state as well. In (b) we have a Toffoli gate which works as an AND gate; if and only if both 4.1. Geometric setup and quantum circuits 21 control qubits are |1ithe target qubit changes to |1i, which is exactly what an AND gate does. And finally we have the representation of an OR gate; an OR gate can be defined as an AND gate by negating the inputs and the output of the AND gate, which is what is represented in (c). With this we can know build a circuit that encodes the maxxcoordinates in the qubits bi(Figure 14). This is done for every coordinate, (minx,maxx,miny,maxy,z); circuits to generate bounds with more complex Boolean expressions may require additional, auxiliary, qubits. Figure 14:Quantum circuit encoding the maxxcoordinates in the qubits bi. 4.1.3The oracle Now we’ll take a look at the oracle. We know that a ray (x,y)intersects a primitive if minx≤x≤maxx∧miny≤y≤maxyand this is the oracle’s job. Figure 15:Quantum circuit for the oracle. 4.1. Geometric setup and quantum circuits 22 If we follow Figure 15 we see the oracle encoded in the ge and le operators that compare the bounds with the ray’s coordinates (x,y), which are hardwired into the circuit. The process described in the previous section to generate the bounds is encoded in the {m|M}{X|Y}operators. Here, we have 2options: using different qubits for each of the primitives’ coordinates or reusing the same qubits for all primitives. The former would require more qubits (4times more, 5times more if the zcoordinate is also taken into account), the latter allows for using much less qubits, but increases the circuit depth, since each of the coordinates has to be generated, compared to the ray’s xand yvalues and then reverted. For this work we selected the latter, since the number of qubits that can be used, on both the simulator and the real machines, is rather limited. Comparison results for xand yare stored onto aux22and aux21respectively (which have been negated, this will be addressed later) after applying the lex,gex,ley,geyoperators which change the aux2 qubits’ state if, for example, the minxcoordinate of a primitive is lower or equal than the ray’s xcoordinate (lex). These 2resulting qubits are then anded together onto aux20, using a Toffoli gate. The latter will thus be |1ifor the primitives intersected by the ray and |0ifor the remaining (the whole circuit is on a superposition over all possible states of |pi:4basis states in this example). After each of the comparison operators, the bounds generator operator appears again: this is required to reverse the state computed onto |bi, resetting its value to |00ibefore it is used again for the next computation. Such is the nature of quantum reversible computing: all computations have to be undone before the qubits can be used again by some other operator. Finally, a rotation over the Zaxis is applied to |piconditioned to |aux20ibeing |1i, thus flipping the sign of the coefficients of those primitives which intersect ray (x,y). After the above described circuit, the state of |aux2ihasn’t been reversed to |000i. However, all ancillary qubits have to be reversed into the original state. This implies repeating the whole circuit in reversed order. The last Toffoli gate in Figure 15 reverses the state of |aux20i; this is followed by a complete repetition of the remaining of the circuit, in order to reverse |aux21iand |aux22i– these are not depicted here due to space constraints. This oracle is valid for the single solution and multiple solution occlusion problems, but in the case of the multiple solution visibility problem the zcoordinate enters the oracle’s calculations for the intersection because, additionally to the conditions already mentioned, the depth of the ray must be lower than a current depth. This adds more blocks (similar to the ones already shown but regarding the zcoordinate) to the oracle circuit in Figure 15. 4.1. Geometric setup and quantum circuits 23 4.1.4Inversion about the average After the solution has been marked by the oracle, the inversion about the average is performed, using Grover’s diffusion operator, to increase the amplitude of the marked state, thus increasing its probability of being measured. Let’s take a closer look to the Grover’s diffusion operator ˆ D. As we’ve seen before, this operator is defined as ˆ D=2|sihs|− ˆ Ibut this doesn’t really give us any clues about how to implement ˆ Dusing common quantum gates. It turns out to be much simpler to figure this out if we slightly rewrite ˆ D. Instead of writing ˆ Das a reflection about |si, we can write it as reflection about |0ibut preceded and followed by a Hadamard gate applied to each of the qubits. This equivalence is not immediately obvious, so we can start by dividing this operator into 2simpler operators as shown in the next equation: ˆ D=2|sihs|− ˆ I=ˆ H(2|0ih0|− ˆ I)ˆ H=2ˆ H|0ih0|ˆ H | {z } =|sihs|? −ˆ Hˆ Iˆ H |{z} ˆ I From the equation above, we clearly see that ˆ Hˆ Iˆ H=ˆ Ibecause ˆ His its own inverse. This is looking closer to the original expression for ˆ Dbut we still need to prove the equivalence of the other part of the operator. The first piece, ˆ H|0i, is clearly equal to the vector |si, so what we really need to show is h0|ˆ H=hs|. To prove this equivalence, we’ll take an arbitrary vector |vi. Applying ˆ Hfollowed by taking the inner product with h0|to the vector |viyields a scalar, h0|ˆ H|vi=h0|Hvi, and we want to show that this scalar is equivalent to the inner product of the uniform superposition |siwith |vi,h0|Hvi=hs|vi. We’ll show this by using a property of ˆ H.ˆ His a unitary operation, thus its conjugate transpose is itself and from the properties of the conjugate transpose we have that, for a matrix ˆ Aand vectors |xiand |yi,hx|Ayi=hA†x|yi. Putting all this together we get: h0|Hvi=hH†0|vi=hH0|vi=hs|vi proving that the Diffusion operator is indeed a reflection about |0ipreceded and followed by a Hadamard gate: ˆ D=2|sihs|− ˆ I=ˆ H(2|0ih0|− ˆ I)ˆ H. This is useful because it’s much more obvious how to implement this reflection about |0i than it is to implement the reflection about |si. Let’s consider what the reflection about |0i does to different inputs: 4.1. Geometric setup and quantum circuits 24 2|0ih0|0i− ˆ I|0i=2|0i1−|0i=|0i 2|0ih0|xi− ˆ I|xi=2|0i0−|xi=−|xi We see from the above equation that if we give the input |0i, the reflection about |0iis just going to give |0iand if we give some input |xidifferent than |0iwe put a negative sign in front of that vector. Given this information, we need to negate the amplitude of every state except the zero state, or the negative, which is to negate the amplitude of the zero state. The quantum circuit for the Grover’s diffusion operator is presented in Figure 16 [18]. Figure 16:Quantum circuit for the Grover’s diffusion operator for the case of 3-qubit primitive indeces. 4.1.5Overall circuit Figure 17: Quantum circuit of the algorithm. (i is not necessarily the same for p,band aux, it just represents that the quantum registers have multiple qubits) The overall and most simplified circuit of this quantum ray tracer is represented in Figure 17. Here we see the steps of the algorithm clearly: (1) application of Hadamard gates; (2) application of oracle; (3) application of Grover’s diffusion operator (Gdo in the figure) (last 2 steps are applied rtimes); (4) measurement. 4.2. Single Solution 25 4.2 single solution This section addresses the case where no more than one primitive projects to each pixel, therefore, for each primary ray, and thus for each quantum query, there are zero solutions or only one. The important points to consider are: (i) the number of solutions is known (t=1), which is fundamental for calculating the number of Grover’s iterations (t=0 will be handled as a failure to find a solution); (ii) the occlusion (”is the ray intersected?”) and visibility (”which primitive does the ray intersect?”) problems are the same, since the ray intersects only one primitive. 4.2.1Algorithm Grover’s algorithm is used to identify intersections between a given ray (x,y)and the geometric primitives. These algorithms assume there are N=2nprimitives indexed from 0, ..., N−1 using an n-qubit quantum register labelled |pi; the quantum register |biis prepared with the coordinates of the primitives, thus there are n+bqubits plus auxiliary qubits, with b=dlog2(max(maxx,maxy))e(the closest upper integer of the log2of the maximum between maxxand maxy). The first step of the algorithm is to do a superposition over the qubits representing the primitives |pi. The next step is to apply the oracle and the diffusion operator rtimes. Lastly, a measurement of the quantum register representing the primitives is done. These steps are described in Algorithm 1. Algorithm 1Q RayCast: quantum algorithm for ray (x,y),Nprimitives and riterations Superposition over the primitives IDs: |pi=H⊗n|0i⊗n r=bπ 4√Nc for riterations do Grover’s oracle {Algorithm 2} Grover’s diffusion operator end for ID ←Measure |pi return ID This algorithm will run for each ray and, in each execution, new quantum and classical registers are created alongside a new quantum circuit. 4.2. Single Solution 26 As for the oracle, the algorithm is presented below, regarding the diffusion operator, its algorithm is simply to add Hadamard, CX and CZ gates as discussed in Section 4.1.4and shown in Figure 16. Algorithm 2Oracle for ray (x,y)intersection with Nprimitives |Hinti ← |1i;|Vinti ← |1i;|intersecti ← |0i minx:|pi|bi=mX |pi|0i⊗nb Negate Hint if x≥b; revert |bi maxx:|pi|bi=MX |pi|0i⊗nb Negate Hint if x≤b; revert |bi miny:|pi|bi=mY |pi|0i⊗nb Negate Vint if y≥b; revert |bi maxy:|pi|bi=MY |pi|0i⊗nb Negate Vint if y≤b; revert |bi |intersecti=|Hinti∧|Vinti Flip the primitive’s coefficient sign if |intersecti=|1i:|pi= (−1)|intersecti|pi Revert |Hinti,|Vintiand |intersecti Algorithm 2presents the oracle. We saw its circuit representation in Figure 15. We see we start by initializing the |Hintiand |Vintiqubits with the value |1i(these qubits are the aux22 and aux21qubits respectively, presented in Figure 15). The |intersectiqubit is initialize with |0iand corresponds to the aux20qubit in Figure 15. The negation of |Hintiand |Vinti is done because, if a ray intersects the primitive, it has to check 2conditions whose result is stored in the |Hintiand |Vintiqubits. If it checks both, it will result in negating the qubits twice, setting them back to their original value |1i. If a primitive doesn’t check the vertical or horizontal condition (or both), meaning |Hintior |Vintiis set to |0i(or both), the |intersectiqubit will remain |0i. In the case where the number of primitives is not a power of 2and the geometry has to be filled with ”false” primitives, meaning, primitives with numbers that make an intersection impossible to occur, the first number is bigger than the second, both |Hintiand |Vintiqubits will have the value |0iand the |intersectiqubit will remain |0ias expected. The qubits never stay unchanged from |1ibecause they always check one condition of the vertical/horizontal dimension (min or max). The last line of the algorithm reverts these qubits to their original state so they can be used again. After the execution of Algorithm 1, the probability of reading the ID of the primitive that intersects the ray, the success probability (ps), is sin2((1+2r)θ)with θ=sin−11 √N (Page 15). For N>4 this probability is close to, but less than, 1. Upon measurement three different cases can occur: 4.2. Single Solution 27 1. the intersecting primitive is measured; 2. a non-intersecting primitive is measured, but in fact the ray intersects another primitive; 3. a non-intersecting primitive is measured and in fact there is no intersection (all primitives have a uniform probability of 1 Nof being measured). To solve this issue we have Algorithm 3. Algorithm 3calls quantum Algorithm 1and then verifies whether the ray intersects the measured primitive using the function veri f y intersection which compares, in a classical and very straightforward way, the ray’s coordinates with the coordinates of the primitive obtained as the result. This is a hybrid algorithm, since the classical code calls a quantum program. If the measured primitive is not intersected, the quantum algorithm is executed again. If after csuch iterations no measured primitive intersects the ray, then that pixel is treated as not occluded. Algorithm 3Hybrid algorithm for the non overlapping case (single solution) for all pixels (x,y)on the image plane do intersected = false iteration =0 r=bπ 4√Nc while not intersected and (iteration <c) do ID = Q RayCast(x,y, primitives, r){Algorithm 1} intersected = verify intersection(x,y, ID) iteration ++ end while end for To discover the probability, or certainty, of the pixel not being occluded, let’s start by defining the probability of a measurement being a success or a failure. A success is when the result yields an intersection and a failure is when the results yield no intersection (we can see a success as a 1 and a failure as a 0). We have already defined that the probability of a successful measurement is ps, thus the probability of a failed measurement is 1 −ps. With an accurate number of Grover’s iterations, the probability of success is really high, making the probability of a failure very low. The probability of obtaining a successful measurement after a failed one is (1−ps)psand after 2failed ones is (1−ps)(1−ps)ps, thus the probability of obtaining a successful result after cfailed measurements is (1−ps)cps. This probability is really low and decreases with each measurement because if there hasn’t been a success, it’s really unlikely that there will be one. We can now conclude that, after 4.2. Single Solution 28 c−1 measurements returning non-occlusion, the probability of measuring an occlusion at the c-th measurement is ps,c=1−(1−ps)c−1psaccording to the geometric distribution and this probability is really high, because with each measurement, if there hasn’t been a success, it’s more and more likely to not have one after each measurement. With this, we can define the probability, after cfailed measurements, of the ray not being occluded. This will be equal do the sum of the probability of the pixel not being occluded in each measurement: ps,c=ps+ c−1 ∑ j=1 ps(1−ps)j This probability increases with the number of measurements; the more measurements we do, the more certain we are that there isn’t indeed an intersection. Because this is a probabilistic algorithm, we are never 100% certain of the result, but with a good number of Grover’s algorithm iterations we can be close to that value. Note that within this work’s context, verifying whether a given ray intersects a specific primitive is assumed to be O(1): the goal of the quantum approach is to reduce the number of evaluations of the veri f y intersection function, not the cost of each such evaluation. Repeating the algorithm a few times, does not have any material impact on quadratic speedup for large N. 4.2.2Results Each scene has a given geometry. This geometry is defined as a list in which each element represents a primitive. As mentioned in page 26, if the number of primitives is not a power of 2, the list is filled with ”false” primitives until the number of primitives is a power of 2. The length of this list is the number of primitives in the scene. A primitive is also represented as a list. As mentioned in Section 4.1.1, this list has 5elements: (minx,maxx,miny,maxy,z), representing the limits of the primitive, as well as its depth (in this case that’s not relevant). Figure 18 presents the images obtained with the Qiskit simulator for 2geometric configurations (scenes) with 4and 8primitives, respectively. The numbers identify the primitives, whereas the dots depicted in each pixel represent the number of iterations required to evaluate the pixel, c, due to evaluating non intersecting primitives. When there is no intersection, the algorithm will run the maximum allowed number of iterations. From Figure 18 we see that the intersecting primitive was always measured on the first iteration of Algorithm 3, 4.2. Single Solution 29 (a) (b) Figure 18:Reference images obtained with the Qiskit simulator for the single solution case. The geometry in (a) is [(0, 1, 0, 1),(2, 2, 0, 3),(3, 3, 1, 1),(3, 3, 3, 3)] and in (b) is [(1, 3, 1, 2),(6, 6, 1, 4),(0, 3, 7, 7),(7, 7, 0, 0),(1, 2, 4, 5),(4, 4, 0, 2),(4, 4, 4, 7),(7, 7, 5, 7)] although in a second run with geometry (b), 2 measurements were needed to find some primitives. For the geometry in (a), since N=4 and t=1 (number of solutions), the probability of success (on a non noisy environment such as the simulator) is 1, therefore having r=1 would be enough as is shown below. Figure 19 presents the results with 2048 shots in the simulator for each pixel with the 4x4geometry of Figure 18. We see that, for this case, where t=N 4, we have sin2θ=t N⇔ sin2θ=1 4⇔θ=sin−1q1 4⇔θ=π 6. With Grover’s iterations r=1, the exact probability of measuring the correct answer is sin2(r+1 2)θ=sin2(1+1 2)π 6=sin2π 2=1 (Page 26), meaning a solution is found with certainty after a single iteration. In Figure 20, we have the histogram for pixel (4, 1)in the 8x8geometry of Figure 18 for 2048 shots. Because here we have t=N 8, the probability of measuring the right primitive is not 100%, although it is really close. In this case rwas set to 2, and, following the same calculations done for the previous case, the probability of measuring the correct answer is 0.945, which is extremely close to the probability obtained. The tables below present some characteristics of the circuits, for different geometries, that are important to understand the viability of the execution of this algorithm on a real quantum machine with today’s technology, such as, the total number of qubits, the depth of the circuit and the total number of gates. These statistics where found using qiskit’s built-in functions when the circuits were run in the simulator. 4.3. Multiple Solutions 36 The probabilistic nature of the algorithm and the importance of the random sampling step are clearly demonstrated by the number of iterations required to find an occluding primitive. Some pixel’s results were found with 0 iterations by random sampling and other pixels require arbitrarily 1 or 2 iterations (with an unreported number of Grover iterations). In the figure above we can also see that the pixels that didn’t show an occlusion when they should have, are pixels with an overlap of primitives thus the number of Grover’s iterations may be less accurate. (a) (b) (c) (d) (e) (f) Figure 23:Results for the multiple solution occlusion case with c=3. Afterwards, cwas increased to 3 and the results are shown in Figure 23. We can see that the results have improved and all the primitives occluded are shown almost every time, only 2out of 6runs have an error on a single pixel. In the cases a primitive is not measured and there is an intersection, there is an overlap, as in the previous case (c=2). We continued to increase cand with 4 iterations the results were 100% accurate and no primitive needed more than 3repetitions to be found as an occluding primitive, as seen in Figure 24. 4.3. Multiple Solutions 37 (a) (b) (c) Figure 24:Results for the multiple solution occlusion case with c=4. We verify that the results weren’t 100% accurate for a lower value of c. The fact that we’re dealing with small numbers (N=8) hinders Grover’s algorithm accuracy because the calculated number of iterations ris meant for very large numbers. This contributes to those failed results in some attempts. In Table 7is presented the growth of the depth of the circuit and the number of gates according to the increase of the number of repetitions of Grover’s algorithm, r, that this algorithm calculates in each iteration. This geometry used 11 qubits. Avg depth Avg #gates r=12408 4210 r=24806 8405 r=37146 12475 Table 7:Growth of depth and number of gates depending on number of iterations of Grover’s algorithm rin a 4x4scene. As we can observe, every time ris increased, the depth and number of gates increases in the same amount as expected, because with each increasing rwe are repeating almost the whole circuit and those 2 quantities will increase in the same amount. We also ran the algorithm for a scene with coordinates from 0 to 7. Figure 25 shows the results obtained and Table 8shows the depth and number of gates of the circuits used to obtain the results. This geometry used 15 qubits. 4.3. Multiple Solutions 38 (a) (b) (c) (d) Figure 25:Results for the multiple solution occlusion case, with an 8x8scene. From Figure 25, we see that we only obtained 100% accurate results with c=4. In the other 2cases, c=2 and c=3, there was one pixel with an incorrect result. Both incorrect results occurred in a pixel with more than one intersection. Regarding Table 8, as in the previous case, every time rincreases, the depth and number of gates increase in the same amount. In Table 9is presented the comparison between the 4x4and 8x8geometries, in regards to the depth and number of gates of the circuits. There’s an increase of approximately 1,7 times of the depth and 1,8times of the number of gates from one case to the other. 4.3. Multiple Solutions 39 Avg depth Avg #gates r=14006 7646 r=28024 15325 r=312060 23047 Table 8:Growth of depth and number of gates depending on number of iterations of Grover’s algorithm rin a 8x8scene. r=1r=2r=3 Avg depth Avg #gates Avg depth Avg #gates Avg depth Avg #gates 4x42408 4210 4806 8405 7146 12475 8x84006 7646 8024 15325 12060 23047 Table 9:Comparison between the 4x4and 8x8scenes. To illustrate the importance of getting the number of Grover iterations right with the Q Search algorithm, we’ve created a geometry, shown in Figure 26, where we have pixels with 1,2and 3different primitives intersecting with the ray. (a) z=0(b) z=1(c) z=2 Figure 26:Scene with geometry [(1, 2, 0, 0, 0),(0, 1, 2, 2, 0),(1, 1, 0, 3, 1),(3, 3, 1, 3, 1),(1, 3, 2, 2, 2)]. In this first case (Figure 27), pixel (2, 0), there is only 1solution, primitive 0. We observe that with 1iteration of Grover’s algorithm, r=1, we can obtain the correct answer, but if we do a second run of the algorithm we obtain the same correct result with a higher probability. In Figure 28, below, we have the case of a pixel having 2intersecting primitives. Here we have the case where t=N 4(t=2 and N=8) and we can see the probabilities are totally distributed by the 2intersecting primitives. However, if we do 2iterations of Grover’s, we end up with a uniform distribution and can’t get any good results. 4.3. Multiple Solutions 40 (a) (b) Figure 27:Results for pixel (2, 0)with r=1and r=2. (a) (b) Figure 28:Results for pixel (3, 2)with r=1and r=2. Finally, we present in Figure 29 the case with 3intersecting primitives (pixel (2, 0)). With r=1, the 3primitives show a greater probability than all the others, yet, with r=2 the probabilities are all flipped and the primitives we wanted to find become the ones with the lowest probabilities. With these 3figures we are able to have a better understanding of how the correct or incorrect number of Grover’s iterations influences the results obtained. Calculating and using the right amount of Grover’s iterations is fundamental to gather correct results. 4.3.2Visibility Contrary to the occlusion problem, where we just wanted to know if a ray was occluded, in this case, we want to know, among all primitives intersected by the ray, which one is closer to its origin. In order to compute which primitive, if any, is visible along each pixel, the minimum depth (zcoordinate) has to be evaluated. This means we’ll need to update 4.3. Multiple Solutions 41 (a) (b) Figure 29:Results for pixel (1, 2)with r=1and r=2. our oracle algorithm, given in Algorithm 2, with depth data to include this new evaluation. The new oracle is presented in Algorithm 5. Algorithm 5Oracle for ray (x,y)intersection with Nprimitives and depth <minZ |Hinti ← |1i;|Vinti ← |1i;|Dinti ← |0i;|intersecti ← |0i minx:|pi|bi=mX |pi|0i⊗nb Negate Hint if x≥b; revert |bi maxx:|pi|bi=MX |pi|0i⊗nb Negate Hint if x≤b; revert |bi miny:|pi|bi=mY |pi|0i⊗nb Negate Vint if y≥b; revert |bi maxy:|pi|bi=MY |pi|0i⊗nb Negate Vint if y≤b; revert |bi z:|pi|bi=Z|pi|0i⊗nb Negate Dint if z≤b; revert |bi |intersecti=|Hinti∧|Vinti∧|Dinti Flip the primitive’s coefficient sign if |intersecti=|1i:|pi= (−1)|intersecti|pi Revert |Hinti,|Vinti,|Dintiand |intersecti Besides generating the primitives’ bounds and comparing them with the ray’s coordinates, now the primitives’ depths are also generated and compared with the current minimum depth; the oracle will only flip a primitive’s coefficient sign if the 5conditions (xand yminimum and maximum values and depth – z– value) are satisfied. This extension to the oracle’s algorithm translates in the addition of one more aux2 qubit in the circuit of Figure 15 and one more set of boxes for the lezand Zoperations. 4.3. Multiple Solutions 42 We have a function that verifies if a primitive has really been intersected but now we need to test if that primitives’ depth is lower than the current minimum depth. For that, we have Algorithm 6. If the current primitive has been intersected, the algorithm will save that result if it is the first obtained intersected primitive, or, if other primitives have been intersected, it will save the result if its depth is lower than the current minimum. Algorithm 6Min: Minimum depth algorithm intersected = verify intersection (x,y, ID, geom) if intersected then if (depth[ID] <pZ and there was one intersection =1) or there was one intersection =0then there was one intersection =1 pZ =depth[ID] p=ID iteration ++ continue end if end if if (there was one intersection =1) then oracle circuit = Algorithm 5 else oracle circuit = Algorithm 2 end if The Min algorithm also changes the variable there was one intersection which decides which oracle is going to be executed. If this variable is 0, it means that there is no primitive marked as intersected and the oracle that will run in the next iteration is the oracle without the comparison of the zcoordinate because the next primitive to be marked as intersected (and its depth) will be automatically saved. If the variable is 1, it means that there has been 1primitive marked as intersected and we have to run the oracle with the comparison of the depths because know we have a value for z. To achieve a Q SearchMin algorithm we use an approach based on Durr et al. [13] and it is given as Algorithm 7. The algorithm is based on the Q Search algorithm (Algorithm 4) but incorporating the Min algorithm (Algorithm 6). This algorithm will run ctimes and doesn’t stop when intersected = true like the other algorithms, because here, even if we find one primitive (intersected = true), there may be more with a lower depth, so we need to keep searching. The algorithm starts by executing the first 2steps of the Q Search algorithm: measuring 1primitive randomly and verifying if it is an intersection (this second step is hidden as Min’s first step). Afterwards, the Min 4.3. Multiple Solutions 43 Algorithm 7Q SearchMin: Quantum minimum algorithm p=−1 pZ =2n bounds qbs iteration =0 l=0 d=1.3 there was one intersection =0 while iteration <cdo ID = Q SampleUniformDistribution(primitives) Min(x,y,pZ, primitives){Algorithm 6} l=l+1 S=min(dl,√N) r=rand(1, ..., S) ID = Q RayCast (x,y, primitives, r){Algorithm 1} Min(x,y,pZ, primitives){Algorithm 6} end while algorithm is called to check if the primitives’ depth is lower than the current. If the Min algorithm has found an intersecting primitive with a lower depth than the current, it will skip the rest of the code in the loop and start a new iteration (continue command) meaning we have found a correct primitive with random sampling and don’t need to run the oracle in this iteration. Up until here we haven’t run the oracle, we just chose a random primitive. After these steps, we carry out the next steps of the Q Search algorithm: calculating the number of times the Grover’s algorithm will run and applying Grover’s algorithm (Q RayCast). Next, we verify the intersection and see if the primitive’s depth is lower than the current with the Min algorithm. We’ve taken the same scene from the previous case (Figure 21) and ran Algorithm 7in the simulator. The result are presented in Figure 30. Analyzing the result, we see that they’re 100% correct with the number of iterations, c, at 3; for every pixel with an intersection, the primitives with the lowest depth have been correctly measured. Table 10 shows the depth and number of gates of the circuits used for this geometry. We still see the values increasing by 2when ris doubled. We also see that these numbers show a big difference before and after the value of zis set to the value of the depth of a primitive. This is caused due to the choice of the oracle. When an intersection has not been found, the executed oracle is the one in Algorithm 2which doesn’t account for the depth data, thus needing less calculation, therefor fewer gates and circuit depth. When an intersection has 4.4. On a Real Quantum Machine 44 Figure 30:Results for the multiple solution visibility case. already been found, the oracle to be executed in the one in Algorithm 5which requires more calculations. Before z After z Avg depth Avg #gates Avg depth Avg #gates r=12410 4211 2870 5010 r=24748 8289 5685 9915 Table 10:Depth and number of gates for the visibility case. 4.4 on a real quantum machine To attempt to execute this algorithm on a real quantum machine, several things have to be considered. The machine used for the execution was the 20 qubit IBM Q Poughkeepsie quantum device. The circuits have to be mapped onto the real machine, which has limited connectivity among physical qubits, as shown in Figure 31. This restriction implies that more gates have to be added in order to swap logical qubits among physical qubits, such that non connected qubits can still be entangled. This, in addition to an already large executable circuit gate count and depth, results in a noisy circuit. Adding the fact that execution times must be kept short due to qubits dephasing and limited coherence times among qubits, a long circuit is going to make it difficult to attain good results. 4.4. On a Real Quantum Machine 45 Figure 31:Connectivity of the qubits in the IBM Q Poughkeepsie real quantum machine. To allow execution on a real machine, a simpler circuit was prepared for the scene depicted in Figure 32; each primitive has coordinates equal to its ID, therefore the operators mX,mY,MX,MY that generate the primitive bounds are not required. The ray coordinates can be compared directly with the primitive ID and the bounds representation |biis not required (compare with Figure 15). Figure 32:Geometry of the scene to execute on the real quantum machine. The table above presents the depth and number of gates used to run the circuit on the real quantum computer. We can check that we’ve managed to reduce these numbers in