Quantum Computation

Kristian Dolghier

Professor Pavan Pillalamarri

April 4th, 2021

Quantum vs Standard Computations

Standard computation is based entirely on logic gates. A logic gate is a logical operation that is performed on a set of inputs that produces a certain output. For the sake of brevity, we will be considering ideal logic gates which have instant rise times and unlimited fan-out.

Modern logic gates use CMOS logic which uses MOSFET devices that have both n channel and p channels. All standard logic gates are based on a system where there are two states, either a 1 or a 0 state. The four base logic gates are the 'Buffer', 'NOT', 'AND', and 'OR' types. The 'Buffer' logic gate just states that the input is equivalent to the output. The Boolean algebra is simply A between A and B so where the input is 1, the output is 1. The 'NOT' type is the opposite of the buffer where the input is proportional to the opposite of the output such as the input is 1 and the output is then 0. The Boolean Algebra is ¬A.The 'AND' type is where both A and B must be 1 to receive an output of 1. The boolean algebra is where A∧B=1 if A=B=1, and A∧B=0 otherwise. The 'OR' type is symbolized by the boolean algebra A∨B=0 if A=B=0, and A∨B=1 otherwise. Additionally, there are 'NAND', 'NOR', 'XOR', and 'XNOR' types which are symbolized by the boolean algebra A↑B, A↓B, A⊕B, and A⊙B respectively. [7]

To visually see the input and output, please see the following graphs.

The basis of all standard computation and logical circuits is based on these fundamental ideas.

Let's look at a NAND gate in CMOS logic:

What is shown below is the circuit diagram of this logic gate. The transistors in series model an AND and the transistors in parallel model an OR gate. If the A and B inputs are high, then the bottom transistors will conduct forming a path between the Output and Vss (ground). This will bring the output low. If the input to A and B is low then the PMOS transistors will conduct forming a path from Vdd to Output and bring the output high. If only A or B is low, then One of the NMOS transistors will conduct and one of the PMOS circuits will conduct. Thus a path is formed from Vdd and the output brings the output high. [2]

Being a former Intel Employee, I worked directly in the Dry Etch department and received much hands on experience with etching. It was difficult to understand how etching certain patterns can create a transistor and how these patterns can perform computations. To put it briefly, this is how a transistor is made. Initially, a photoresist must be applied to a field oxide which was grown on a p type substrate. This photoresist is then removed in certain areas using lithography. A certain wavelength of light passes through a reticle which dictates where the photoresist must be removed. After the photoresist is removed, a certain dry etch process is followed depending on the necessary width, and metal that is being etched. Following an etch of the oxide layer, an n-Well must be made.[1] This is done by diffusing n-type impurities into the p type substrate. Following this process, we can remove the oxide layer with hydrofluoric acid and then again deposit an oxide layer and a polysilicon layer on the whole wafer via chemical deposition. These layers are moved except in areas where they are needed. Following this, we again form an oxidation layer and remove a certain area of it where n+ and p+ sources and drains are needed. The final cross section should look like Figure 2 and the top down physical layout is in Figure 3. [2]

Figure 2: Cross section of 2 transistors in a CMOS gate

Figure 3 : Layout of NAND circuit

This is what all modern computation and computing is based off of. Trillions of transistors make up every CPU and each transistor is one of several logic gates that all form an ability for computation. All of these logic gates are based on boolean logic and as such Boolean logic can explain the various algorithms that are used. For instance, to multiply two numbers, the CPU can use Wallace trees or a Dadda Multiplier algorithm to most efficiently add the partial products in a single cycle.[8] Quantum computing uses completely different algorithms that cannot be explained with Boolean logic. It is interesting that quantum computing can be done, albeit extremely inefficiently, by standard computational algorithms, but the nature of how quantum computing works allows a process that would take billions of years to take place in seconds. The battle in speed is partially based upon the algorithms that use these quantum logic gates. These quantum algorithms can be much less time consuming for certain computations, and can even solve problems that no classical computer could solve in a feasible amount of time.

Where a normal classical is based on bits, a quantum circuit is based on qubits. As mentioned, bits have 2 states being 0 and 1 which are transferred between two levels of low DC voltage. A qubit is similar, where they usually take the value of 0 or 1, but they can also be a superposition of both. Qubits can be the spin of an electron, the number of electrons, polarization of a photon, electron localization, or any other quantum criteria where one state represents a |0⟩ and a |1⟩. [3] Additionally, the act of measuring the output of a qubit can destroy its coherence and disturb the state of superposition. A qubit can hold up two bits of information. To reiterate, qubits use Dirac notation where:

There are many quantum gates with different logic behind each gate. Some of these gates act on a single qubit ,on two qubits, or more than two qubits. All quantum logic gates are unitary matrices and it should be known that the number of quantum gates is uncountable.

Let us look at an example of a Controlled NOT gate (CNOT). CNOT is a quantum logic gate that acts on two qubits, and performs the NOT operation on the second qubit only when the first qubit is |1⟩. CNOT will transform the quantum state a|00⟩+b|01⟩+c|10⟩+d|11⟩ into a|00⟩+b|01⟩+c|11⟩+d|10⟩. [3]

Another valuable gate is the Hadamard (H) gate that acts on a single qubit. It maps the basis set |0⟩ and |1⟩ to(|0⟩ +|1⟩)/(2^.5) and (|0⟩ -|1⟩)(2^.5) respectfully. [6] This is very important as it makes a measurement that has equal probabilities of both 1 or 0 and creates a superposition between them. It is represented by the matrix:

Since there is an infinite amount of quantum gates, there are many ways to show different computations. For instance, there are universal quantum gates which states that any set of gates can be reduced or transformed to any other universal gate. For instance, the CNOT gate and another gate called sqrt(SWAP) are both universal two-qubit gates that can be transformed into each other. Where the circuit representation of a CNOT and sqrt(SWAP) are shown as [6]:

,respectfully. Where the matrix representation of the SWAPgate is shown as [6]:

These two can easily be transformed to one and another as shown in this circuit representation. [6]

This is one of the factors that is interesting for quantum computing, however the most useful portion is the reversibility of these computations. In standard computation, you cannot tell what the input is purely from knowing the output. All quantum logic gates are reversible and the composition of multiple gates is also reversible. This is intriguing in the context of running algorithms in reverse as their unitary inverse to do the same computation using the other process. Where we have a quantum fourier transform, the inverse quantum fourier transform can be done as well. However, the knowledge of knowing the input from the output is independent of this reversibility and is used in many quantum algorithms.

For instance, let us look at Grover's Algorithm in its solution to the black box system. The black box is any function of a system that separates the input from the output and can be (Omega) used to obfuscate the input.

The steps of the algorithm are as follows.

where |s⟩states the uniform superposition over all states. [5]

Then we have operator Us=2|s⟩⟨s| - I ; this operator is known as the Grover diffusion operator.

Also, we have a subroutine called Uomega acts as

Or can act similar to a NOT gate for multiple qubits

Or simply,

Knowing this, the steps of the algorithm is initialize the system to the state |s⟩as mentioned. Then we perform the Grover iteration r(N) times. The function r(N) is asymptomatically O(N^.5) where N is the size of the functions domain. [5] The Grover iteration is performed by applying the operator Uw then applying the operator Us. Then we measure (omega) and the result will be eigenvalue λw.[5] This result will not be 1, as there is no upper bound by which the calculations must be done until the correct answer is achieved. However, the number of iterations does not grow with N. From the eigenvalue λw, w can be obtained. The quantum circuit representation is as shown: [5]

As can be seen, we use an H gate and other quantum gates in the process of this algorithm. There are many other quantum algorithms, but this is an example of one and how it finds a solution to a problem that may not necessarily be found using quantum computation. It is intriguing how this uses the reversibility of quantum logic gates as a process, but not necessarily the reversibility of the gates themselves to find the input.

For quantum computation, there are many obstacles in the way of making this process more streamline. Qubits, just by the quantum nature of them, are difficult to scale efficiently and still be able to read independently from one another. Additionally, it is difficult to read these qubits currently as it is not efficient to read the spin of a certain electron. However, the main issue is quantum decoherence. This can be viewed as the loss of information from a system into the environment. A particle is said to be coherent if there exists a defined phase relation between its different states. If the particle was perfectly isolated, it would remain coherent forever, but due to outside factors, the environment and time cause decoherence. An electron is defined by a wave function which is a probabilistic representation of the electron's nature.

Decoherence provides a framework for apparent wave function collapse. This is where components of the wavefunction decouple and are lost to the surrounding environment. This is irreversible and non unity and is the main complication with quantum computing.We can cool down the qubits of 20 millikelvins as some scientists have done, but a simple stray cosmic ray can corrupt the superposition and render the computation moot.[4] Due to this there is a probability that decoherence will happen over time which is independent from decoherence from rotation, repolarization or dissipation.[4] There is a possibility that we can make some quantum algorithms operable, but we can mitigate this if the use of error correction can correct errors faster than the system introduces them via decoherence. However, this is only possible if, due to the Quantum threshold theorem, the probability of error is at most ε where we use using

.[3]

Overall, there are many factors involved in making quantum computing more time efficient, more dense and resistant to decoherence. Currently, our best quantum computer has 84 qubits which allows for more difficult computations that can only be done with more qubits. The nature of the algorithms for quantum computing and the reversibility allow us to solve problems that were previously unsolvable and use much more efficient algorithms. This form of computation is the future, but the process for making a qubit based cpu will likely be completely independent of the current dry etching used for our logic gates.

Works Cited

[1] *, Name. "CMOS Fabrication Using N-Well and P-Well Technology." ElProCus, 18 Apr. 2019, www.elprocus.com/the-fabrication-process-of-cmos-transistor/.

[2] Voinigescu, Sorin (2013). High-Frequency Integrated Circuits. Cambridge University Press. p. 164. ISBN 9780521873024.

[3] Nielsen, Michael A.; Chuang, Isaac L. (June 2012). Quantum Computation and Quantum Information (10th anniversary ed.). Cambridge: Cambridge University Press. ISBN 9780511992773. OCLC 700706156

[4] Beau, M.; Kiukas, J.; Egusquiza, I. L.; del Campo, A. (2017). "Nonexponential quantum decay under environmental decoherence". Phys. Rev. Lett. 119 (13): 130401. arXiv:1706.06943. Bibcode:2017PhRvL.119m0401B. doi:10.1103/PhysRevLett.119.130401. PMID 29341721. S2CID 206299205.

[5] Grover, Lov K. (1996-07-01). "A fast quantum mechanical algorithm for database search". Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing. STOC '96. Philadelphia, Pennsylvania, USA: Association for Computing Machinery: 212-219. doi:10.1145/237814.237866. ISBN 978-0-89791-785-8.

[6] Aharonov, Dorit (2003-01-09). "A Simple Proof that Toffoli and Hadamard are Quantum Universal". arXiv:quant-ph/0301040.

[7] Jaeger, Microelectronic Circuit Design, McGraw-Hill 1997, ISBN 0-07-032482-4, pp. 226-233

[8] Townsend, Whitney J.; Swartzlander, Jr., Earl E.; Abraham, Jacob A. (December 2003) [2003-08-06]. "A Comparison of Dadda and Wallace Multiplier Delays" (PDF). SPIE Advanced Signal Processing Algorithms, Architectures, and Implementations XIII. The International Society. doi:10.1117/12.507012.