#LyX 1.1 created this file. For more info see http://www.lyx.org/ \lyxformat 2.16 \textclass article \language default \inputencoding latin1 \fontscheme default \graphics default \paperfontsize default \spacing single \papersize Default \paperpackage a4 \use_geometry 1 \use_amsmath 0 \paperorientation portrait \leftmargin 1in \topmargin 0.5in \rightmargin 1in \bottommargin 0.75in \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \defskip smallskip \quotes_language english \quotes_times 2 \papercolumns 1 \papersides 1 \paperpagestyle default \layout Standard \series bold Document type: \series default Proposal, pre-submission. \layout Standard \series bold Agency: \series default NSF/CISE/EIA \layout Standard \series bold Program: \series default 01-95/QuBIC - Quantum and Biological Inspired Computing \layout Standard \series bold Title: \series default \emph on Dawn of a New Field: Quantum Computer Systems Engineering \layout Standard \series bold PI: \series default Michael Frank (UF/Eng/CISE) \layout Standard \series bold Date: \series default Started 6/22/2001. Due 6/29/2001. LaTeX run of \latex latex \backslash today \latex default . \layout Standard \latex latex \backslash nocite{Lo-etal-98,Leff-Rex-90,Qgol,sch} \layout Standard \latex latex \backslash cleardoublepage \layout Standard \latex latex \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \backslash setlength{ \backslash parskip}{0pt} \layout Section* B. Project Summary \latex latex \backslash vspace{-8pt} \layout Standard The traditional field of \emph on computer systems engineering \emph default (abbreviated CSE in this document) is concerned with the complete, integrated design and analysis of general-purpose (or special-purpose) computing systems. This field is highly interdisciplinary, in that it can include considerations of technology across all levels from circuit and communication architectures through processor design, chip packaging, multiprocessor system design, programming systems, and software. It can involve a broad range of engineering considerations such as performance, power, cost, and manufacturability. \layout Standard In our perception, the field of quantum computing is presently lacking a corresponding systems engineering discipline. This is perhaps not surprising, since quantum computing is still in its infancy, and quantum processors of useful capacity have not yet been built. However, the device physics work needed for the implementation of scalable quantum computing has been progressing rapidly \begin_inset LatexCommand \cite{Wineland-et-al-94,Cirac-Zoller-95,Pellizzari-et-al-95,Cory-etal-96,Gershenfeld-Chuang-97,Loss-DiVincenzo-98,Cory-etal-98,Mooij-etal-99,Blatter-etal-99,Kane-00,Hu-Sarma-01,Privman-etal-01,Privman-Mozyrsky-01} \end_inset , and if the historical trends of Moore's law continue, we can reasonably expect that manufacturable bit-devices will reach the scales at which quantum effects are dominant within at most the next 20-50 years. At that point, whatever bit-device technology is in use will necessarily (we argue) have many, if not all, of the characteristics (see \begin_inset LatexCommand \cite{DiVincenzo-00} \end_inset ) needed for scalable quantum coherent computing. Furthermore, such quantum technology may be available even sooner, if research on macroscopic qubit implementations ( \emph on e.g. \emph default , in superconductors \begin_inset LatexCommand \cite{Mooij-etal-99,Blatter-etal-99,Privman-etal-01} \end_inset ) and on error correction algorithms \begin_inset LatexCommand \cite{Preskill-97} \end_inset proceeds rapidly. \layout Standard Once there is a manufacturable, scalable device technology for quantum computing , it will then be necessary to engineer the architecture and software of computers consisting of enormous numbers of these devices. But rather than waiting for the device physicists and manufacturing process engineers to complete their work, we should get a head start at working out solutions to the anticipated computer engineering problems. If a mature quantum computer engineering discipline is already well developed by the time quantum bit-devices are practical, then the development of commercializable quantum computer product lines will be greatly accelerated, to the benefit of practical applications throughout society. \layout Standard To promote this goal, we propose initiating a program of research at UF to build the foundations of a new field of \emph on quantum computer systems engineering \emph default . This will involve work in the following areas: \layout Enumerate \series bold High-level device models \series default that hide the complex details of quantum device physics and manufacturability within a small set of engineering parameters that influence systems design, such as peak frequency, maximum packing density, energy leakage rates, entropy generation rates, decoherence rates, and cost. (See \latex latex { \backslash S} \latex default C.I.a below.) \latex latex \backslash setlength{ \backslash itemsep}{0pt} \layout Enumerate \series bold High-performance, distributed simulators \series default for quantum circuit architectures and quantum algorithms, with accompanying visualization tools. (See \latex latex { \backslash S} \latex default C.I.b.) \layout Enumerate \series bold \emph on Asymptotically tight \emph default physically-realistic models \series default of scalable, parallel quantum machines (previously outlined in \begin_inset LatexCommand \cite{memom5,Frank-99,Frank-99b} \end_inset ). These models would take into account all the relevant fundamental physical constraints, including relativistic limits on communication and thermodynamic limits on entropy removal, and yet offer the highest possible asymptotic performance on all problems. ( \latex latex { \backslash S} \latex default C.I.c.) \layout Enumerate \series bold Practical architectures \series default (equal in asymptotic efficiency to the underlying model) that provide a convenient programming model for quantum processing elements in scalable systems. ( \latex latex { \backslash S} \latex default C.I.d.) \layout Enumerate \series bold Natural high-level programming languages \series default built on our architecture. (See \latex latex { \backslash S} \latex default C.I.e.) \layout Enumerate \series bold Efficient parallel quantum computer algorithms \series default for a variety of natural and important problems of interest in computer science and elsewhere. For example, our group at UF has significant expertise in image processing and compression \begin_inset LatexCommand \cite{Schmalz-etal-00,Ritter-Wilson-01} \end_inset , which would be investigated as a potential class of candidate applications. ( \latex latex { \backslash S} \latex default C.I.f.) \layout Enumerate Concepts for the design of appropriate \series bold multi-tasking, multi-user operating systems \series default for parallel quantum computers. ( \latex latex { \backslash S} \latex default C.I.g.) \layout Enumerate The work at all levels will permit a parameterized system \series bold cost-performance analysis \series default and thorough \series bold design optimization \series default ( \latex latex { \backslash S} \latex default C.I.h.) \layout Standard We have already started working on many of these areas, and our group has significant expertise that can be brought to bear towards the completion of these goals. \layout Standard \latex latex \backslash cleardoublepage \layout Section* C. Project Description \latex latex \backslash vspace{-8pt} \layout Standard We begin with a semi-technical discussion of the long-term goals for our quantum computing research program. This research program is ambitious, realistic, and many-faceted. In \latex latex { \backslash S} \latex default C.II, we will indicate which specific aspects of this larger project we plan to emphasize within the scope of the 3-year award being proposed. \latex latex \backslash vspace{-8pt} \layout Subsection* C.I. Technical Discussion \latex latex \backslash vspace{-8pt} \layout Standard We discuss the technical aspects of our planned development of a quantum computing systems engineering discipline, proceeding from the foundational, low-level components of computing systems, to the highest-level, most abstract components (see Fig. \latex latex ~ \latex default \begin_inset LatexCommand \ref{f:stack} \end_inset ). \latex latex \backslash vspace{-8pt} \begin_float fig \layout Standard \align center \begin_inset Figure size 357 327 file QC-Stack.epsi width 3 60.00 flags 5 \end_inset \latex latex \backslash vspace{-8pt} \layout Caption \begin_inset LatexCommand \label{f:stack} \end_inset Somewhat like in ISO's standard Open Systems Interconnection model for networkin g systems \begin_inset LatexCommand \cite{OSI} \end_inset , we can break down the problem of physically-realistic quantum computer systems engineering into a stack consisting of concepts at different layers, from the bottommost foundational layers closest to the physics, up to the higher-level abstractions and artifacts that are the direct subject of systems analysis. The design at each layer depends on the concepts, definitions, and characterist ics at the layer below. Traditional qubit and quantum gate models are not suitable for systems design since they lack important physical parameters such as size, cost, power, and error rates. Our extended models allow us to realistically build up engineering designs for higher-level programming structures and algorithms, and then optimize the design all the way back down to the lowest level. \end_float \layout Subsubsection* C.I.a. Device Abstraction \latex latex \backslash vspace{-8pt} \layout Standard The first step in building up a high-level computer systems engineering discipline is to provide a usable foundation for systems analysis. We thus propose to set up an abstraction barrier to insulate the systems engineer from always having to worry about details of the physical operation of the low-level components of the system. \layout Standard In quantum computing, the now-standard abstraction for representing the state space of small quantum physical systems is the \emph on qubit \emph default . The qubit represents any two-state quantum system, but systems having more states can be represented satisfactorily using collections of qubits. \layout Standard Similarly, the standard abstraction of low-level \emph on operations \emph default on qubits is the \emph on quantum logic gate \emph default . The theory of quantum gates, pioneered by David Deutsch in \begin_inset LatexCommand \cite{Deutsch-89} \end_inset and developed over a period of several years \begin_inset LatexCommand \cite{Deutsch-et-al-95,DiVincenzo-95a,Barenco-95} \end_inset , culminating in the discovery \begin_inset LatexCommand \cite{Barenco-et-al-95a} \end_inset that 1-bit quantum gates, together with a single classical reversible 2-bit gate, comprise a complete gate set for quantum computing \latex latex . \latex default This means that any quantum logic network can be composed of such gates when appropriately interconnected, similarly to how any classical logic network can be composed using 2-input NAND gates. \layout Standard Qubits and quantum gates provide a sufficient foundation for quantum logic, but computer systems engineering (CSE) requires more than just a digital logic foundation. Typical concerns in the engineering of real computing systems include such characteristics as speed, power consumption, and error rates, none of which are addressed by digital logic alone. Additionally, real qubits are associated with a physical location in space, interact only locally, and require explicit mechanisms for their interconnectio n. \layout Standard Therefore, for systems engineering purposes, the description of a primitive quantum computer's components as being qubits and quantum gates must be augmented by some additional parameters that summarize the low-level physical characteristics of these components (in a given device technology), which impact these important systems considerations. These parameters include: \layout Enumerate \series bold Gate transition time. \series default Every non-null quantum gate operation requires some non-zero minimum time for its completion. The times for different gates in a system may vary, but it usually suffices for systems-level analysis to take an average or worst-case time among all gates in the system as being characteristic of all gates. In any event, there is not expected to be a large amount of variation between the minimum transition times of different gates in a system. \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Enumerate \series bold Physical location and velocity. \series default Qubits must be implemented as real physical objects located in 3-D space. Their relative location is relevant to communication latency concerns. Some qubits in a system ( \emph on e.g. \emph default , photons) may be moving relative to the rest of the system ( \begin_inset Quotes eld \end_inset flying \begin_inset Quotes erd \end_inset qubits \begin_inset LatexCommand \cite{DiVincenzo-00} \end_inset ) in order to enable fast communications; the velocity of such qubits also impacts communications latency and entropy flux density. \layout Enumerate \series bold Maximum packing density. \series default The maximum density at which devices (transistors or quantum gates) and state-bearing components (bits or qubits) can be packed in two and three dimensions is actually an important consideration for computing systems design, because it affects the minimum achievable distances between the components, which (due to the speed-of-light limit) determines the minimum communication latencies. Latency is not so important for uniprocessor machines, but it is a key concern in large-scale parallel systems. This remains true in quantum computers, since quantum mechanics does \emph on not \emph default allow faster-than-light communication. \layout Enumerate \series bold Energy leakage rates. \series default Any real physical object in a nonequilibrium system dissipates energy (in some form) into its surroundings at a nonzero rate. Energy leakage is an especially significant concern in nano-scale systems, because at these scales, the potential-energy barriers that usually prevent leakage are much narrower and also lower (due to energy density constraints) than in larger-scale systems. The decreased height of the barriers increases rates of leakage due to thermal fluctuations. Thermal leakage can be suppressed exponentially in the inverse of the absolute temperature, and therefore can be effectively eliminated by sufficient cooling. However, even if thermal leakage is eliminated, quantum tunneling presents another leakage mechanism which is not suppressed by cooling, and is further exacerbated by the small width (as well as height) of the potential barriers in nanometer scale systems. Still, if states with sufficiently high energy barriers are utilized, it may be possible to achieve reasonably low leakage rates in even atomic-scale systems. Certainly, this is the case if state information is encoded in interatomic bond configurations. This is illustrated by the frequent need in chemistry to use catalysts to lower energy barriers and facilitate chemical reactions that would otherwise occur extremely slowly. \begin_deeper \layout Standard Energy leakage is an important systems concern, because it generates entropy that must be removed from the system (entropy cannot be \begin_inset Quotes eld \end_inset un-generated \begin_inset Quotes erd \end_inset due to the second law of thermodynamics). The generation of entropy implies a corresponding loss of free energy which must be compensated by introducing new free energy from outside. The transport of entropy and free energy, in turn, affects overall system design because there are various technological and fundamental limits to the flux density at which entropy and energy can be transported in a system with bounded temperatures and energy densities. We do not expect that any future technology will ever allow \emph on unbounded \emph default temperatures and energy densities, since all known material structures break down ( \emph on e.g. \emph default , melt or vaporize) at high temperatures. Therefore, in designing a computing system, one must explicitly make room for pathways to transport entropy out of the system. This affects inter-component distances, and thus communications latencies. Even today, the task of providing sufficient cooling and power to VLSI circuits significantly impacts the design of high-performance microprocessors, their packaging, and computer enclosures. \layout Standard Therefore, a device model useful for systems engineering will need to include leakage parameters. Bit (or qubit) storage elements in a given technology (at a given temperature) can be well characterized by a constant leakage rate. Active devices can be characterized by a constant leakage rate, and a per-opera tion energy dissipation (in case there is a transient increase in dissipation rate during device operation). \emph on Adibatic \emph default operations, by definition, have a per-operation dissipation that scales inversely with transition time \begin_inset Formula \( t \) \end_inset , which itself may be a system design variable, implying that there is an important device parameter \begin_inset Formula \( k_{E}=Et \) \end_inset (the \begin_inset Quotes eld \end_inset energy coefficient \begin_inset Quotes erd \end_inset ) that gives the constant energy-time product that characterizes this dissipatio n term \begin_inset Formula \( E \) \end_inset . (Incidentally, this parameter has the same physical dimensions as angular momentum, or Planck's constant, but we do not yet know if this connection has any physical significance. Planck's constant has been shown \emph on not \emph default to be a lower bound on \begin_inset Formula \( k_{E} \) \end_inset \begin_inset LatexCommand \cite{Likharev-82} \end_inset .) \end_deeper \layout Enumerate \series bold Entropy generation rates. \series default As we mentioned in the previous item, entropy removal is a significant concern in computer systems engineering. The dissipation of a small amount of energy \begin_inset Formula \( E \) \end_inset causes an amount \begin_inset Formula \( E/T \) \end_inset of entropy to be generated, where \begin_inset Formula \( T \) \end_inset is the temperature of the component's immediate surroundings. This entropy increase can be minimized by maximizing \begin_inset Formula \( T \) \end_inset . We assume any technology has temperature limits, so entropy generation can only be minimized by raising the cooling system's temperature up to a certain point, as heat transfer to the cooling system becomes more difficult. \latex latex \latex default Note also that keeping a high temperature to minimize entropy generation from energy leakage is somewhat at odds with keeping a low temperature to minimize thermally-induced leakage. However, if thermal leakage is the only source of dissipation, then low temperatures are favored, because thermal leakage goes down exponentially with inverse temperature. Another important source of energy dissipation is irreversible bit operations \begin_inset LatexCommand \cite{Landauer-61} \end_inset which dissipate at least \begin_inset Formula \( kT\ln 2 \) \end_inset energy ( \begin_inset Formula \( k \) \end_inset being Boltzmann's constant) and therefore generate at least \begin_inset Formula \( k\ln 2 \) \end_inset entropy \latex latex --- \latex default a constant regardless of operating temperature, so adjusting temperature does not help eliminate this source of entropy generation. \begin_deeper \layout Standard However, \emph on reversible \emph default operations do avoid this particular source of entropy generation \begin_inset LatexCommand \cite{Landauer-61,Bennett-73} \end_inset , and quantum gate operations are one type of reversible operation. A major focus of our past and future research \begin_inset LatexCommand \cite{Frank-99,Frank-99b} \end_inset is in characterizing the system-level design tradeoffs between the entropy generation caused by irreversible operations, and the overhead of the extra operations and space-time storage requirements required for reversible operation. In quantum computers, the requirement for reversibility in order to maintain quantum coherence significantly affects the shape of this tradeoff in quantum algorithms. \end_deeper \layout Enumerate \series bold Error rates / decoherence rates. \series default In any computer, the rate at which individual bit-devices experience random errors in their intended logical state is an important system-level considerati on, because it impacts the need for digital error-correcting mechanisms and robust architectures and algorithms. Error rates are actually very closely related to rates of energy dissipation and entropy generation. The occurrence of a logical error is a form of energy leakage. In order for a device to mistakenly change states, energy (in some form, such as electrons), must \begin_inset Quotes eld \end_inset leak \begin_inset Quotes erd \end_inset from the intended region of state space to an unintended region. Thus, rates of energy leakage between normal states and error states impacts error rates. Also, independently of how much was energy was transferred to cause the error, the unintended change in the machine's logical state represents an increase in \emph on logical \emph default entropy, which is really just a special case of physical entropy. So, error rates impact entropy generation rates. Finally, entropy generation itself is the critical event that causes \emph on quantum decoherence \emph default , which is essentially the dissipation of a quantum probability mass (wave packet) beyond the bounds of a restricted state space in which portions of the wave packet could have been brought together in a controlled way to cause desired interference effects. \begin_deeper \layout Standard Decoherence rates can be characterized by a rate of decoherence events per unit time for a static data component (qubit), and by a rate of decoherence events per operation for an active device (quantum gate). These rates can be further decomposed into rates for logic errors (bit flips) and phase errors (sign errors in the amplitude) \begin_inset LatexCommand \cite{Calderbank-Shor-95} \end_inset . These separate error rates influence the design of quantum error correction algorithms, an important systems-level concern for applications that require quantum coherence. \end_deeper \layout Enumerate \series bold Per-device cost \series default under a given manufacturing process is a key consideration in systems-level design. In particular, the relative cost of manufactured devices and free energy will significantly affect the values of architectural parameters that should be chosen in order to minimize the total (system manufacture plus operation) cost for a given application. For example, some applications will be more energy-limited than others. Thus, depending on the device cost and the expected operational lifetime of the system, it may make sense to use more parallel devices, each individuall y operating more slowly (and so adiabatically dissipating less energy) than in other applications that are less energy limited. \layout Standard \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.I.b. Quantum Logic Emulation and Visualization \latex latex \backslash vspace{-8pt} \layout Standard After one has a high-level model of logic devices including systems engineering parameters, the next step in computer systems engineering is to determine the number of such devices required to build various intermediate-level spatial and/or temporal structures, such as functional units or operation sequences needed for common medium-level operations such as integer arithmetic. A realistic count of the device operations required to perform higher-level operations is required in order to derive an aggregate estimate of the amount of system resources (space, time, power, cooling) that are required. \layout Standard In order to derive accurate estimates of these device counts, our group is already actively carrying out work to investigate these medium-level computing structures. This summer, using existing funding \begin_inset LatexCommand \cite{Siemens-proj,ippd} \end_inset , we have hired a bright undergraduate research assistant to implement a quantum logic simulator in Java. This work, which has already begun, is planned to eventually include the following features: \layout Enumerate A spacetime-efficient sparse representation of quantum superpositions, based on eliminating explicit representation of all states having zero amplitude. (Such states dominate whenever classical subroutines are used in quantum algorithms.) \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Enumerate A straightforward simulation technique for arbitrary quantum logic networks. \layout Enumerate Classes implementing all the important varieties of quantum logic gates discussed in the literature , all in terms of primitive gates, as described in \begin_inset LatexCommand \cite{Barenco-et-al-95a} \end_inset . \layout Enumerate Classes implementing higher-level quantum operations, such as reversible arithmetic \begin_inset LatexCommand \cite{Vedral-et-al-95} \end_inset , the quantum Fourier transform \begin_inset LatexCommand \cite{Shor94,Coppersmith-94,Griffiths-Niu-95} \end_inset , and quantum error-correction algorithms \begin_inset LatexCommand \cite{Calderbank-Shor-95,Preskill-97} \end_inset , in terms of quantum circuit algorithms found in the literature. \layout Enumerate Classes implementing high-level quantum algorithms, such as the Shor algorithm [cite], as well as a number of classical reversible algorithms of interest. Classical reversible computing is interesting because it can reduce entropy generation \begin_inset LatexCommand \cite{Bennett-73} \end_inset and can be implemented even in present-day VLSI technology \begin_inset LatexCommand \cite{Younis-Knight-94,Younis-94,Frank-etal-98a} \end_inset ; it does not require the low decoherence rates needed for true quantum computing. \layout Enumerate A linear-space (but potentially less time-efficient) simulation technique we have developed that is analogous to the Feynman path integral, or to Cramer's transactional interpretation \begin_inset LatexCommand \cite{Cramer-86} \end_inset . This option may be preferable (more efficient overall) for large simulations that would otherwise exceed available computer memories and therefore be I/O-limited. \layout Enumerate A parallel/distributed simulation technique we have developed that is based on mapping different portions of the quantum state space to different machines on the network. Portions of a quantum wave packet are communicated (using internet packets) to the machines representing the part of state space to which that wave packet is traveling. Essentially, the entire quantum computation is reduced to a data-flow on the network. Synchronization between alternate transmission paths is not necessary due to the linearity of quantum mechanics. The technique can be easily pipelined, leading to high resource utilization. It is also compatible with the path-integral approach in case the memory available on the grid is a limiting factor. \layout Enumerate Execution of the distributed quantum computer simulator on the OCEAN \begin_inset LatexCommand \cite{ocean} \end_inset , the market-based distributed computer infrastructure we are developing. A separate proposal for OCEAN funding \begin_inset LatexCommand \cite{OCEAN-prop} \end_inset was submitted by us and other colleagues to the NSF/CISE/ANIR/STI program last week. \layout Enumerate A refined version of a technique we developed in 1996 for dynamic visualization of the dynamic evolution of quantum computations (see Fig.\SpecialChar ~ \begin_inset LatexCommand \ref{f:shor} \end_inset ). This technique allows the user to watch the movement of amplitude through the machine's configuration space as the computation proceeds. The state spaces of selected multi-qubit machine registers are translated into coordinate axes in a 1, 2, or 3-dimensional space, with a color-wheel representation of amplitudes. The resulting visualization is rendered onto a graphics display and animated in real time as the simulation proceeds, gate by gate. This visualization tool is both a helpful pedagogical instrument, and a useful tool for gaining scientific insight into the workings of quantum algorithms. \layout Enumerate Using the simulator, carry out a careful counting and characterization of the number of quantum gate-operations required to implement various higher-leve l architectures and algorithms, and an accounting of the total energy, etc. This data will be an important input to our higher-level systems design work. \layout Standard \latex latex \backslash vspace{-8pt} \layout Standard \begin_float fig \layout Standard \align center \begin_inset Figure size 426 471 file visualization.epsi flags 11 \end_inset \layout Caption \begin_inset LatexCommand \label{f:shor} \end_inset Our visualization technique for quantum computations, applied to the Shor factoring algorithm in two dimensions. Example for factoring \begin_inset Formula \( n=33 \) \end_inset . Machine states are projected onto a space defined by the values of two machine registers, \begin_inset Formula \( a \) \end_inset and \begin_inset Formula \( b \) \end_inset . Our new simulator will animate this visualization continuously as individual quantum gate operations are applied. (a) The machine state after generation of a uniform superposition over possible values of \begin_inset Formula \( a \) \end_inset . (b) The state after the modular exponentiation step of Shor's algorithm, \begin_inset Formula \( b=x^{a}\bmod n \) \end_inset ; here \begin_inset Formula \( x=5 \) \end_inset . (c) The state after performing a quantum Fourier transform over register \begin_inset Formula \( a \) \end_inset . At this point, \begin_inset Formula \( a \) \end_inset can be measured to obtain information about \begin_inset Formula \( n \) \end_inset 's factors. (d) A 256-point color-wheel representation for complex-valued state amplitudes. \end_float \layout Paragraph* Polynomial-Space Simulation of Quantum Computers \layout Standard A widespread misconception is that classically simulating a quantum computer having \begin_inset Formula \( n \) \end_inset qubits requires, in the worst-case, \begin_inset Formula \( \Omega (2^{n}) \) \end_inset bits of classical storage, in order to track the amplitudes of all \begin_inset Formula \( 2^{n} \) \end_inset basis states. Actually, storing all states simultaneously isn't necessary. In a technique inspired by Feynman's path integral formalism, only \begin_inset Formula \( O(nt) \) \end_inset bits of classical state are required to simulate \begin_inset Formula \( t \) \end_inset primitive gate operations in an \begin_inset Formula \( n \) \end_inset -qubit quantum computer. The basic idea is to iterate through possible final states, determining their amplitudes via accumulation of a sum of amplitudes over all paths leading from the initial state. The space savings arises because only one such path need be represented at any given time. However, this more space-efficient algorithm does still require exponential time (bounded by \begin_inset Formula \( e^{O(t)} \) \end_inset ). Nevertheless, the elimination of the large space requirement means that in an academic research setting, where long computer runs may be easier to obtain than massive amounts of storage, the use of this algorithm may slightly increase the size of quantum computations that we can feasibly simulate. \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.I.c. Physically Realistic Models of Parallel Quantum Computation \latex latex \backslash vspace{-8pt} \layout Standard Our quantum circuit simulator will allow as to build and test quantum circuits for simple functional units within a quantum computer. But they cannot directly tell us about the behavior of more complex quantum computations, due to the fundamental intractability of simulating quantum systems on classical machines \begin_inset LatexCommand \cite{Feynman-82} \end_inset . So, in order to plan larger-scale quantum computations, we need a well-structur ed theoretical model of scalable, parallel universal quantum computation. We already know how to define such a model, based on insights gained from our earlier work on scalable, parallel universal classical reversible computati on \begin_inset LatexCommand \cite{Frank-etal-98a,Frank-99} \end_inset . The essence of such a model is simply a 3-D universal reversible cellular automaton, with the added feature that certain automata states cause the transformation of a local cellular neighborhood to proceed via a unitary transformation chosen from a universal set, rather than via only a classical reversible computation. This simple universal parallel quantum computer model can then serve as a foundation for the design and scaling analysis of more easily programmable scalable, parallel, quantum computer architectures. \layout Standard Furthermore, in order to ensure that our models are truly physically realistic, we plan to incorporate within them the constraints imposed by consideration of the engineering parameters mentioned in Section C.I.a above \latex latex --- \latex default rates of leakage, decoherence, entropy generation, \emph on etc. \emph default In addition to necessitating error correction, these parameters have the additional affect of forcing processing elements to be spread out somewhat in comparison to their most compact possible configuration in order to provide sufficient area for the removal of entropy generated within the machine, despite constraints on entropy flux. These issues were explored in more detail in \begin_inset LatexCommand \cite{Frank-99} \end_inset in the context of classical reversible computing \latex latex --- \latex default but in quantum computers these thermodynamic issues are essentially unchanged. \layout Standard The quantum circuit simulator discussed in the previous section can be used to test computations in our 3-D spatial model \latex latex \latex default with \latex latex \latex default large numbers of qubits \latex latex --- \latex default but only in cases where the degree of quantum parallelism at any time is kept reasonably small. \latex latex \backslash vspace{-8pt} \layout Paragraph* Classical Plus Quantum Parallelism. \layout Standard We now illustrate the need for models of quantum computation that incorporate both quantum and classical parallelism by analyzing the minimum asymptotic time complexity of algorithms for a certain class of problems, under models incorporating various combinations of quantum and classical parallelism. \layout Standard We choose as our example problem class the \emph on unstructured search problem \emph default , in which a black-box function \begin_inset Formula \( f \) \end_inset is provided, and one is required to find an input value \begin_inset Formula \( x \) \end_inset of the function that produces a given output \begin_inset Formula \( y=f(x) \) \end_inset , assuming for simplicity that there is exactly one such input \begin_inset Formula \( x \) \end_inset . We assume that the space of possible inputs \begin_inset Formula \( x \) \end_inset has \begin_inset Formula \( N \) \end_inset elements. To simplify the analysis, we assume that each function evaluation requires \begin_inset Formula \( \Theta (1) \) \end_inset time, and that function evaluations are carried out using a \begin_inset Formula \( \Theta (1) \) \end_inset -size mechanism which can be reproduced \emph on en masse \emph default as needed, but which cannot be feasibly transformed to a mechanism for computing the pre-images of given output values \begin_inset Formula \( y \) \end_inset . Note that this black-box model is a reasonable approximation to the actual situation with a typical NP-complete problem, where candidate solutions \begin_inset Formula \( x \) \end_inset of a given size can be checked rapidly using a short algorithm, but there is no known algorithm that can quickly find solutions (and thus the algorithm for computing \begin_inset Formula \( f \) \end_inset might as well be a black box). \layout Standard An aside: Contrary to a widespread misunderstanding, this particlar black-box model is \emph on not \emph default a very good model of looking up entries in a database, since a database (even a quantum one) having \begin_inset Formula \( N \) \end_inset \emph on arbitrary \emph default (as opposed to correlated) entries will be of size \begin_inset Formula \( \Theta (N) \) \end_inset (not \begin_inset Formula \( \Theta (1) \) \end_inset as in our model), due to the bounded entropy densities of physical systems \begin_inset LatexCommand \cite{Bek81} \end_inset . In fact, the entire field of quantum statistical mechanics, a cornerstone of modern physics, revolves around the observation that the entropy content of physical systems is bounded by the log-volume of the system's \emph on classical \emph default phase space (measured in Planck units). This log-volume scales only \emph on linearly \emph default with the number of particles. So, for example, \begin_inset Formula \( n \) \end_inset qubits can only store \begin_inset Formula \( O(n) \) \end_inset bits of random classical information; they \emph on cannot \emph default , for example, store the \begin_inset Formula \( \Theta (2^{n}) \) \end_inset independent bits which would be needed to encode a database of \begin_inset Formula \( 2^{n} \) \end_inset arbitrary entries. For this and other reasons, we view Grover's characterization of his algorithm as addressing \begin_inset Quotes eld \end_inset database search \begin_inset Quotes erd \end_inset as being a somewhat misleading picture of its potential real-world applications \latex latex --- \latex default another reason being that in an ordinary commercial database, a simple index sufficies to reduce lookup time to \begin_inset Formula \( \Theta (1) \) \end_inset (modulo communications requirements), thereby obviating the whole problem. We therefore choose the more abstract and neutral term \begin_inset Quotes eld \end_inset unstructured search \begin_inset Quotes erd \end_inset for this problem instead. \layout Standard Let us now consider various combinations of classical and quantum parallelism. (Some of the below results were first developed by Dr.\SpecialChar ~ Frank in 1997 shortly after Grover presented his algorithm.) \layout Enumerate \series bold No classical or quantum parallelism. \series default Requires \begin_inset Formula \( \Theta (N) \) \end_inset expected time, since one can do no better than to try possible inputs in an arbitrary sequence until a solution is found. \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Enumerate \series bold No classical, but quantum parallelism. \series default Grover's algorithm takes \begin_inset Formula \( \Theta (\sqrt{N}) \) \end_inset time, and this has furthermore been proven \begin_inset LatexCommand \cite{Zalka-97} \end_inset to be asymptotically optimal. However, one should keep in mind that the runtime analysis does not apply if there is a constant lower bound on error rates (errors per operation or per unit time) within the machine, since in that case there is an asymptotic ally divergent overhead factor that is incurred by known fault-tolerant error-correction algorithms \begin_inset LatexCommand \cite{Preskill-97} \end_inset . Thus we propose to accurately analyze the performance of specific quantum algorithms in a realistic model based on known algorithms for quantum error correction. \layout Enumerate \series bold Classical but no quantum parallelism. \series default Assume there are \begin_inset Formula \( M \) \end_inset classical serial processors that can simultaneously explore different portions of the search space. Processors are \begin_inset Formula \( \Theta (1) \) \end_inset size, so due to the speed-of-light limit it will take \begin_inset Formula \( \Theta \left( M^{1/3}\right) \) \end_inset time merely to communicate the input to the computation (the desired value ) to all \begin_inset Formula \( M \) \end_inset processors from whatever point it originates, when the processors are arranged in a spherical configuration around the origin that minimizes communication time. Each processor takes time \begin_inset Formula \( \Theta (N/M) \) \end_inset to search its portion of the possible inputs, so the total time will be \begin_inset Formula \( \Theta \left( M^{1/3}+N/M\right) \) \end_inset . Since \begin_inset Formula \( M^{1/3} \) \end_inset is increasing in \begin_inset Formula \( M \) \end_inset while \begin_inset Formula \( N/M \) \end_inset is decreasing in \begin_inset Formula \( M \) \end_inset , this sum is of least order for fixed \begin_inset Formula \( N \) \end_inset when \begin_inset Formula \( M^{1/3}\asymp N/M \) \end_inset (notation meaning, when the two quantities are of the same asymptotic order). Rearranging, we have \begin_inset Formula \( M^{4/3}\asymp N \) \end_inset or \begin_inset Formula \( M\asymp N^{3/4} \) \end_inset . With \begin_inset Formula \( M=\Theta \left( N^{3/4}\right) \) \end_inset , the total time is then \begin_inset Formula \( \Theta \left( N^{1/4}+N^{1/4}\right) =\Theta \left( N^{1/4}\right) \) \end_inset . Note that this is a factor of \begin_inset Formula \( N^{1/4} \) \end_inset times faster than with quantum parallelism! However, this analysis ignores thermodynamic constraints. We can also show that including a constant temperature bound gives time order \begin_inset Formula \( N^{5/16} \) \end_inset , an improvement of \begin_inset Formula \( N^{3/16} \) \end_inset over case 2. Furthermore, including a constant minimum error rate gives time order \begin_inset Formula \( N^{1/2} \) \end_inset , which coincidentally is the same as in the quantum case. \layout Enumerate \series bold Classical and quantum parallelism. \series default Now each processor can use Grover's algorithm on its part of the search space, and take only \begin_inset Formula \( \Theta \left( \sqrt{N/M}\right) \) \end_inset time for its search. Minimizing \begin_inset Formula \( \Theta \left( M^{1/3}+\sqrt{N/M}\right) \) \end_inset gives \begin_inset Formula \( M=N^{3/5} \) \end_inset and total time order \begin_inset Formula \( N^{1/5} \) \end_inset . This is better than with either quantum or classical parallelism by itself. We can also show that adding a temperature constraint gives time \begin_inset Formula \( N^{5/24} \) \end_inset (still better), and adding a constant minimum error rate gives time \begin_inset Formula \( N^{1/4} \) \end_inset , which happens to be the same as in the classical case with no bounds on temperatures or error rates. However, this analysis still does not take into account the algorithmic overheads for quantum error correction, only the classical thermodynamic overheads for error-entropy removal. The proposed work would detail and complete the full analysis. \layout Standard We observe that classical and quantum parallelism taken together seem to offer greater asymptotic performance in realistic models than either type of parallelism taken alone. This observation motivates our study of quantum models that also utilize classical parallelism. \layout Standard Although the above analyses do not yet take quite all of the relevant physical constraints into account, the results obtained so far lead us to believe that a fuller analysis will continue to show an advantage (though a polynomiall y smaller one) for both types of parallelism taken together. \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.I.d. Quantum Instruction Set Architectures \latex latex \backslash vspace{-8pt} \layout Standard As our model of parallel computation is elaborated, we plan to leverage our expertise in designing classical reversible computer architectures [cites] to design a comparable quantum instruction set architecture and a corresponding microarchitectural implementation. \layout Standard In addition to providing all the ordinary classical reversible instructions that can be found in a design such as our PISA architecture \begin_inset LatexCommand \cite{Vieri-95,Vieri-96,Frank-96b,memom8,Vieri-99,Frank-99,Frank-99b} \end_inset , the quantum instruction set will also provide special quantum instructions. For example, some instructions might perform a bitwise 1-qubit quantum gate operation in parallel across all qubits in a given machine register, or on a selectable subset of the bits. We would also like to incorporate standard DSP (digital signal processing) operations such as FFTs (fast Fourier transforms) as primitives supported by our instruction set. The quantum Fourier transform used in Shor's algorithm would be another important primitive, as would quantum error correction operations. \layout Standard We would also like the architecture to include such powerful emerging architectu ral features as an FPGA-type capability for programmable custom circuits \begin_inset LatexCommand \cite{xilinx} \end_inset , programmable lookup tables for SIMD operations \begin_inset LatexCommand \cite{Margolus-97,Margolus-00} \end_inset , and the capability to program custom data flows among functional units \begin_inset LatexCommand \cite{raw} \end_inset . \layout Standard After specifying the architecture, we would then create a microarchitectural implementation by embedding the interconnection structure of our functional units into the parallel 3-D spatial quantum cellular automaton simulator which we will have developed by that point. \layout Standard Our design will be intractable to simulate on a classical computer when executing programs that utilize more than a small amount of quantum parallelism , since it is generally intractable to simulate quantum systems on classical machines. However, in test programs where the amount of quantum parallelism at any time is kept reasonably small, our simulator will be sufficiently capable of simulating all of the functions of our architecture, despite the very large number of qubits that will be used in our design. \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.I.e. High-Level Quantum Programming Languages \latex latex \backslash vspace{-8pt} \layout Standard Naturally, one would also like to have high-level quantum programming languages so that one could specify complex quantum algorithms using a textual representa tion that is more concise and easily readable than assembly language for a low-level machine instruction set. Several proposals for high-level quantum programming languages already exist \begin_inset LatexCommand \cite{Baker-96,Omer-98,Sanders-Zuliani-99,Omer-00} \end_inset . We intend to either choose one of these languages, or define a new language using the best ideas from the existing languages, and then develop a compiler for the language that targets our simulated quantum architecture. This will allow us to run high-level test programs on our simulated quantum architecture. As always, the degree of quantum parallelism that can be feasibly simulated in these tests should be small. Nevertheless, we expect to be able to satisfactorily validate the language, compiler, and architecture. \layout Standard Note that we have already accomplished the corresponding line of research for the case of classical reversible languages \begin_inset LatexCommand \cite{memom8,Frank-99,Frank-99b} \end_inset , which can be viewed as a special case of quantum languages. \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.I.f. Parallel Quantum Algorithms \latex latex \backslash vspace{-8pt} \layout Standard Finally, the above-described architecture would be conceived as a single-process or architecture to be used within a scalable 3-D mesh of identical processing nodes (as described in \begin_inset LatexCommand \cite{memom5,Frank-etal-98,Frank-Knight-98,Frank-99} \end_inset ). As discussed previously, the most efficient algorithms for many problems would generally be algorithms that used both classical and quantum parallelism. We would develop such algorithms for various applications, such as Grover's unstructured search problem \begin_inset LatexCommand \cite{Grover-96} \end_inset , and for image processing and compression applications of interest at UF \begin_inset LatexCommand \cite{Schmalz-97,Schmalz-etal-00,Ritter-Wilson-01} \end_inset . \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.I.g. Quantum Computer Operating Systems \latex latex \backslash vspace{-8pt} \layout Standard Another interesting related research problem is to determine what type of operating system would be appropriate for a computer architecture that supports the option of quantum parallelism. Issues of support for multithreading and I/O take on some challenging aspects in the context of quantum computing. For independent quantum or classical processes time-sharing a machine's underlying resources, there is no fundamental difficulty. However, if a computation utilizing quantum parallelism needs to communicate to another process, or to the outside world, the situation becomes more complex, and issues of entanglement and wavefunction collapse need to be taken into account. We propose to explore these issues, and outline the kinds of high-level functionality that it makes sense for a quantum computer OS to perform. However, a detailed, full-featured OS design is not necessary in order to pursue the rest of our proposed research program. Applications can run on bare hardware. \layout Standard \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.I.h. System Scaling Analysis & Design Optimization \latex latex \backslash vspace{-8pt} \layout Standard In the above sections, we have described device models, circuit simulators, and design tasks that can feasibly be accomplished for architectures, programmi ng languages, and application algorithms, before the first significant quantum computer is built. This design work would set the stage for a meaningful, detailed, and physically -realistic analysis of the asymptotic performance characteristics of parallel quantum algorithms. We propose to account for all of the important real-world engineering considera tions, such as communications delays, power and cooling requirements, and overhead from error correction and reversible computation. \layout Standard This analysis, in turn, can be fed back through the entire system design process, to optimize the choices of system design parameters at all levels so as to maximize performance-per-cost for a given (special-purpose or general-purpose) application. Optimizing each level's parameters given the optimizations already taking place at higher levels allows one to propagate the system-level performance considerations all the way down to the design parameters at the lowest level. This will allow us to derive a utility function which would describe performanc e-per-cost in high-level applications, on the original parameter space that we started with for our lowest-level devices \latex latex --- \latex default individual qubits and quantum gates. \layout Standard This utility function will then be available as a principled basis for the design optimization of the low-level components. This would allow device physicists and manufacturing process engineers to know how best to trade off, for example, manufacturing cost against decoherence rates, if their goal is to achieve the highest overall utility for overall system applications, given the rational design optimizations that will be made at all of the higher levels. \layout Standard The utility function on the device parameter space is expected to have the earliest impact on real-world quantum computer design, as it would guide the device physicists towards the best device designs. As device technologies improve, examination of our higher-level designs and analysis will then inform manufacturers whether the system performance/cost attainable using a new device is high enough to launch a competitive product line. If so, the manufacturer can proceed to use our optimized systems design and software tools (such as compilers), or more generally our design techniques and methods, to begin the manufacture of a high-quality line of complete quantum computing systems almost immediately after the low-level device technology is available. \layout Standard Ultimately, the impact of our proposed research would be to allow quantum device physicists and process engineers to quickly focus on optimum design goals, and to allow manufacturers to quickly design products. This combination of effects could potentially speed the development of practical, well-designed quantum computers by a number of years, yielding potentially billions of dollars in economic benefit. \layout Standard We are not so bold as to expect that we will be the only ones to pursue this sort of engineering path: indeed we view it as somewhat obvious, and feel that quantum computer engineering will in subsequent decades become a major field of study. However, we feel that our experience in designing classical reversible computing systems at all levels, and our well-grounded understanding of quantum computing, uniquely qualifies us to initiate this line of research. We intend to devote much effort towards guiding large numbers of people within the device physics, process design, and computer engineering communities to work towards the rational ends proposed in this research. Our role as individual researchers is initiating research directions, elaborati ng and disseminating technical aspects of the proposed research, and thereby educating the wider community about the above-described, natural outline for the new field of quantum computer systems engineering that we propose to help found. \latex latex \backslash vspace{-8pt} \layout Subsection* C.II. Statement of Work to be Undertaken \latex latex \backslash vspace{-8pt} \layout Standard The previous section describes the long-term goals of our research program. In this section, we describe the specific work to be undertaken with this award. \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.II.a. Objectives and Significance \latex latex \backslash vspace{-8pt} \layout Standard In this section, we indicate our plan for the objectives to be pursued under the scope of this award, organizing them chronologically by quarter-year. After each year's objectives we state the significance of that year's work. Items are annotated with a tentative selection of the researchers primarily responsible for each objective. \layout Itemize \series bold Year 0 \series default (before award period) \latex latex \backslash setlength{ \backslash itemsep}{-4pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \begin_deeper \layout Itemize \series bold ~3rd quarter 2001 \series default (2 months, Jul.-Aug.): \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \begin_deeper \layout Itemize \emph on (Frank) \emph default Publish earlier results on classical reversible architectures, languages, and systems analysis with several conference and journal articles. \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Itemize \emph on (Frank, student) \emph default Publish earlier results with Motter on numerical stability of reversible simulations of quantum mechanics (which has possible relevance to the new simulator work). \layout Itemize \emph on (Frank, Schmalz) \emph default Finish characterization of quantum bit-device abstraction suitable for systems analysis. Determine & tabulate parameter values for various qubit implementations proposed in the literature. Publish results. \layout Itemize \emph on (Frank, student) \emph default Implement first version of Java-based quantum circuit simulator & visualization tool (naive algorithm, not distributed). Test using Shor & Grover algorithms and quantum mechanics simulations. Publish. \end_deeper \end_deeper \layout Itemize \series bold Year 1 \series default (4th qtr. 2001 - 3rd qtr. 2002) \begin_deeper \layout Itemize \series bold ~4th qtr. 2001 \series default (4 months, Sep.-Dec.) \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \begin_deeper \layout Itemize \emph on (Frank) \emph default Complete and publish modeling and analysis of classical plus quantum parallelis m, outlined in section C.I.c above. Publish. \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Itemize \emph on (Frank, student 1) \emph default Improve quantum circuit simulator: Implement distributed version and path-integ ral option. Publish. \layout Itemize \emph on (Schmalz, student 2) \emph default As a test application, develop reversible and quantum versions of previously-de veloped image & signal processing primitives such as FFTs, convolutions, etc.; test on circuit simulator; publish. \end_deeper \layout Itemize \series bold 1st qtr. 2002 \series default (Jan.-Mar.) \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \begin_deeper \layout Itemize \emph on (Frank) \emph default Re-teach course on \begin_inset Quotes eld \end_inset Physical Limits of Computing \begin_inset Quotes erd \end_inset \begin_inset LatexCommand \cite{PhysLim} \end_inset (last taught Spr. 2000), which covers reversible computing, quantum computing, and their impact on systems engineering. Assign student projects to experiment with reversible & quantum machine simulators. Publish course materials via the web. \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Itemize \emph on (Frank, student 1) \emph default Generalize the PISA reversible architecture \begin_inset LatexCommand \cite{Vieri-95,Vieri-96,Frank-96b,memom7,Vieri-99,Frank-99,Frank-99b} \end_inset to support quantum primitive operations. Investigate quantum versions of emerging architectural features such as FPGAs, cellular automata machines, and reprogrammable systolic arrays \begin_inset LatexCommand \cite{Margolus-97,Margolus-00} \end_inset . Publish. \layout Itemize \emph on (Frank, Schmalz, student 2) \emph default Design & implement quantum microarchitecture incorporating both general-purpose and signal-processing capabilities. Test on simulator. Publish. \end_deeper \layout Itemize \series bold 2nd qtr. 2002 \series default (Apr.-Jun.) \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \begin_deeper \layout Itemize \emph on (Frank) \emph default Continue teaching course (through early May). \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Itemize \emph on (Frank, student 1) \emph default Generalize R reversible high-level language compiler \begin_inset LatexCommand \cite{memom8} \end_inset to a new language (to be dubbed \begin_inset Quotes eld \end_inset Q \begin_inset Quotes erd \end_inset ) that supports quantum primitives. Publish. \layout Itemize \emph on (Frank, Schmalz, student 2) \emph default Reimplement test algorithms (Shor, Grover, quantum mechanics simulation, image processing) in new Q programming language. Test under simulator. Publish. \end_deeper \layout Itemize \series bold 3rd qtr. 2002 \series default (Jul.-Sep.) \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \begin_deeper \layout Itemize ( \emph on Frank, Schmalz, students) \emph default Develop parallelized versions of test algorithms to run on a mesh of the processors we have designed. Test on simulator. \end_deeper \end_deeper \layout Itemize \series bold Year 2 \series default (4th qtr. 2002 - 3rd qtr. 2003) \begin_deeper \layout Itemize \series bold 4th qtr. 2002 \series default (Oct.-Dec.) \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \latex default - ( \emph on Frank, Schmalz, students) \emph default Integrate a quantum error correction scheme into our architecture. Publish. \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Itemize \series bold 1st qtr. 2003 \series default (Jan.-Mar.) \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \emph on \latex default - (Frank, Schmalz, students) \emph default Develop realistic asymptotic scaling analysis for cost-performance of our sample applications on our parallel architectural model, in terms of device and system-design parameters. Publish. \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Itemize \series bold 2nd qtr. 2003 \series default (Apr.-Jun.) \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \latex default - ( \emph on Frank, Schmalz, students) \emph default Refine above scaling analysis to include numerical values for all constant factors. Publish. \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Itemize \series bold 3rd qtr. 2003 \series default (Jul.-Sep.) \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \latex default - \latex latex \latex default ( \emph on Frank, Schmalz, students) \emph default Back-propagate the system-level cost-performance scaling analysis to determine how to optimize the system design parameters at all levels, given the cost-perf ormance optimizations to be applied at the levels above. Publish. \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \end_deeper \layout Itemize \series bold Year 3 \series default (4th qtr. 2003 - 3rd qtr. 2004) \begin_deeper \layout Itemize \series bold 4th qtr. 2003 \series default (Oct.-Dec.) \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \emph on \latex default - \emph default \latex latex \emph on \latex default (Frank, Schmalz, students) \emph default Given the above work, derive the utility function over the quantum bit-device parameter space that maximizes system-level cost-performance on the types of test applications we have explored. Publish this result and a description of the methodology used, for the benefit of the quantum device physics community. \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Itemize \series bold 1st qtr. 2004 \series default (Jan.-Mar.) \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} - \emph on \latex default (Frank) \emph default Again teach course integrating these research results, like in year 1. This time, student projects can utilize the new parallel machine model (not just the serial one). \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Itemize \series bold 2nd qtr. 2004 \series default (Apr.-Jun.) \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \emph on \latex default - \emph default \latex latex \emph on \latex default (Frank) \emph default Continue teaching course. \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \emph on \latex default - (Frank, Schmalz, students) \emph default Develop concepts for multi-user, multi-tasking operating systems for our quantum computer architecture. \layout Itemize \series bold ~3rd qtr. 2004 \series default (2 months, Jul.-Aug.) \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \emph on \latex default - \emph default \latex latex \emph on \latex default (Frank, Schmalz, students) \emph default Develop additional test applications for our architecture; characterize how different types of applications impact the utility function over the device design space. \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \end_deeper \layout Standard \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.II.b. Relation to Longer-Term Goals \latex latex \backslash vspace{-8pt} \layout Standard Beyond the above-listed objectives, our longer-term goal is to assist in establishing quantum computer engineering as a major field of study. The above work will lay much of the basic foundation for this field. The most important work to be performed includes: \layout Enumerate The device physics, engineering, and manufacturing process design work needed to build the quantum bit-devices that optimize the system-level cost-performanc e function revealed by our research. \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Enumerate Other systems engineering work, relating to thermal and materials engineering of cooling systems, optimization of interconnection systems, packaging and structural integrity, component accessibility for maintenance or replacemen t, \emph on etc. \emph default Our work only lays the foundation for the design of the bit devices and the computing structures. We do not propose these other system design areas, except in the sense that our models ensure that our quantum computation structures will scale realistically with respect to thermodynamic and communications constraints. These constraints will be integrated into our models and analysis. \layout Enumerate Systems design work for additional special-purpose applications. \layout Enumerate Analysis of processor architecture concepts lying outside our design space. For example, while our architecture might include parameterizable tradeoffs between the amount of space devoted to certain known programming models, such as traditional instruction sets and reconfigurable logic, it will not anticipate alterative architectures that may support programming models that have not been conceived. However, our general system engineering methodology should be adaptable to any possible programming architecture. \layout Standard \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.II.c. Relation to State of Field and Work in Progress Elsewhere \latex latex \backslash vspace{-8pt} \layout Standard Of course, there are by now many major groups working on the field of quantum computation in general. A sampling of a few of the most well-known ones includes: Oxford's Centre for Quantum Computation Buhrman which includes early pioneer David Deutsch \begin_inset LatexCommand \cite{Oxford-site} \end_inset ; the DARPA-funded Quantum Information and Computation collaboration among Caltech, MIT, and USC \begin_inset LatexCommand \cite{QUIC-site} \end_inset ; the DARPA-funded NMR quantum computing collaboration involving Stanford, Berkeley, MIT, and IBM \begin_inset LatexCommand \cite{Stanford-site} \end_inset ; Buhrman, Tromp, Vitanyi \emph on et al. \emph default 's group at CWI in Amsterdam \begin_inset LatexCommand \cite{Buhrman-site} \end_inset ; and the Laboratory for Theoretical and Quantum Computing at the University of Montreal \begin_inset LatexCommand \cite{Montreal-site} \end_inset . However, essentially all of the existing groups focus either on the fundamental theory of quantum computing & quantum information, or on the experimental physical realization of low-level (few-qubit) quantum devices, rather than on the higher-level systems design & engineering focus that we are proposing. So we seem to be filling a mostly-empty niche. \layout Standard There are a few exceptions: Kevin Obenland's Ph.D. dissertation under Al Despain at USC \begin_inset LatexCommand \cite{Obenland-98} \end_inset made significant strides in the area of quantum circuit simulation, including error modeling and error correction. We intend to leverage some of this work, updating it in the new context of our spatial physical device model, and construct and test higher-level architectural components using methodologies similar to Obenland's. \layout Standard John Hayes and Igor Markov at the University of Michigan recently started a new DARPA-funded project \begin_inset LatexCommand \cite{Hayes-Markov-01} \end_inset to develop logic synthesis tools and testing methodologies for quantum computers. We don't intend to focus on these areas, per se, but this work could be a useful complement to our own. Dr.\SpecialChar ~ Markov has agreed to informal collaboration to share simulation and design tools. Our undergraduate student DoRon Motter, who worked with us at UF on quantum mechanics simulations \begin_inset LatexCommand \cite{Motter-00} \end_inset , is now a graduate student at Michigan and has been working with Markov. \layout Standard Benjamin and Johnson at the University of Oxford have a paper \begin_inset LatexCommand \cite{Benjamin-Johnson-98} \end_inset in which they introduce a cellular architecture for computing computing that is similar in spirit to the kind of parallel spatial model we proposed to develop in section C.I.c above. However, the Benjamin-Johnson model does not include all of the parameters that need to be included for systems engineering purposes, and it is two-dimens ional rather than three-dimensional. We also believe that a much denser and more compact cellular architecture can be developed. Another interesting quantum CA model that we are drawing ideas from is that of Yepez \begin_inset LatexCommand \cite{Yepez-99} \end_inset ; however, it is specialized for fluid dynamics simulation, rather than being intended as a universal model. \layout Standard On the topic of applications, there has been almost no work yet on developing image processing or computer vision algorithms for quantum computers. In fact, so far we have found only two papers. In \begin_inset LatexCommand \cite{Vlasov-96} \end_inset , Vlasov begins to explore some interesting quantum image recongition algorithms , and Hattori \emph on et al. \emph default \latex latex \backslash \latex default follow up on this work in \begin_inset LatexCommand \cite{Hattori-etal-00} \end_inset . But these two papers are just a start, and, we believe, only scratch the surface of the potential applications of quantum computing in image and signal processing and in computer vision that we wish to investigate. \latex latex \backslash vspace{-8pt} \layout Subsection* C.III. General Plan of Work \latex latex \backslash vspace{-8pt} \layout Standard We have already detailed our planned activities in section C.I, and our planned work schedule in C.II.a. Here are some additional points. \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.III.a. Activities to be Undertaken \latex latex \backslash vspace{-8pt} \layout Standard The work can be roughly divided into architecture work, applications work, and analytical work. We describe this breakdown and our qualifications to do the described work. \latex latex \backslash vspace{-8pt} \layout Paragraph Architectural work. \layout Standard Dr.\SpecialChar ~ Frank will have primary responsibility for supervising the architectural work, described in more detail in sections C.I and C.II.a above. This will include: \layout Enumerate Design and implementation of quantum circuit simulators. \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Enumerate Development of machine models and architectures to support systems analysis. \layout Enumerate Design and testing of programming systems: architectural components & languages. \layout Standard Dr.\SpecialChar ~ Frank has significant background relevant to this work. During his graduate work at MIT, Dr.\SpecialChar ~ Frank learned computer architecture and systems engineering principles in courses and talks by Dr. William J. Dally (now at Stanford). He went on to join the MIT Reversible Computing Project \begin_inset LatexCommand \cite{Mikes-rc-page,AI-rc-site} \end_inset , where he studied quantum computing \begin_inset LatexCommand \cite{mpf-qc} \end_inset ; built the world's first reversible instruction set implementation \begin_inset LatexCommand \cite{Frank-Rixner-96} \end_inset and the first scalable, universal, parallel, fully-reversible processor \begin_inset LatexCommand \cite{Frank-etal-98a} \end_inset ; helped design the first asymptotically efficient RISC-style reversible instruction set \begin_inset LatexCommand \cite{memom7,Frank-99} \end_inset ; proposed scalable, physically realistic models of computing \begin_inset LatexCommand \cite{memom5} \end_inset ; proved new separations and lower bounds in complexity theory for reversible computing \begin_inset LatexCommand \cite{Frank-Ammer-97,Frank-Ammer-01} \end_inset ; designed & implemented the first C-like reversible programming language \begin_inset LatexCommand \cite{memom8,Frank-99} \end_inset ; performed a systems-level scaling analysis of reversible machines, which established for the first time that they can outperform conventional machines \begin_inset LatexCommand \cite{Frank-etal-98,Frank-Knight-98} \end_inset ; and tied all this material together into the first comprehensive Ph.D. thesis on reversible computing \begin_inset LatexCommand \cite{Frank-99} \end_inset . Since his graduation in 1999, Dr.\SpecialChar ~ Frank has been working at the University of Florida to initiate collaborations in (classical reversible) adiabatic circuits and quantum computing with faculty in the CISE, ECE, Physics, and Math departments \begin_inset LatexCommand \cite{proposals,rev-people} \end_inset , while teaching courses in discrete math \begin_inset LatexCommand \cite{discrete} \end_inset , computer organization & architecture \begin_inset LatexCommand \cite{computer-org} \end_inset , and the physical limits of computing \begin_inset LatexCommand \cite{PhysLim} \end_inset . Meanwhile, he has also been making informal notes on more optimized reversible circuits and more sophisticated systems analysis, work which would written up and subsumed within the effort proposed here. \latex latex \backslash vspace{-8pt} \layout Paragraph Applications work. \layout Standard Dr.\SpecialChar ~ Schmalz will have primary responsibility for supervising the applications work, particularly aspects relating to the design of quantum image and signal processing applications, with support from Dr.\SpecialChar ~ Frank in the area of more traditional quantum computing applications. Our suite of test applications will include: \layout Enumerate Shor's factoring algorithm \begin_inset LatexCommand \cite{Shor94} \end_inset . \latex latex \backslash setlength{ \backslash itemsep}{0pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Enumerate Grover's algorithm for unstructured search \begin_inset LatexCommand \cite{Grover-96} \end_inset . \layout Enumerate Algorithms for simulation of quantum physical systems \begin_inset LatexCommand \cite{Feynman-82,BoghTay96,Abrams-Lloyd-97} \end_inset . \layout Enumerate Basic image processing and image algebra operations based on earlier work by UF \begin_inset LatexCommand \cite{Schmalz-97,Schmalz-etal-00,Ritter-Wilson-01} \end_inset , with applications as supported by research results in implementing these basic operations. \layout Standard Dr.\SpecialChar ~ Mark Schmalz (co-PI) specializes in image and data compression, image and signal processing (ISP), and computer vision (CV). In this proposed project, Dr.\SpecialChar ~ Schmalz would apply his expertise in ISP/CV and performance analysis to (a) translate basic ISP/CV operations to the proposed reversible/quantum architecture, and (b) measure and analyze performan ce of a wide variety of image-related operations and metrics within this framework. Such research is of key importance to rapidly expanding areas of technology including Internet video, telemedicine, and distance learning. The proposed effort leverages a decade of epxerience at UF in porting image processing and compression algorithms to a wide variety of sequential and parallel workstations, massively parallel processors, digital signal processors , and adaptive or reconfigurable computing systems \begin_inset LatexCommand \cite{Ritter-Wilson-01,Schmalz-etal-00} \end_inset . Performance of these image algorithms would be analyzed in terms of computation al error, as well as space and time complexity \begin_inset LatexCommand \cite{Schmalz-97,Schmalz-etal-00} \end_inset , and fed back into the overall system optimization analysis. \layout Standard We will begin with simple image and signals processing operations such as pointwise arithmetic, image sum or maximum, and convolution with linear or nonlinear kernels. If this research proves feasible, we propose to extend the results to support more complex image processing operations. Because we propose to use image algebra, which is computationally complete and has a small operator set, the extension of quantum image operations to realistic applications is feasible in principle. \latex latex \backslash vspace{-8pt} \layout Paragraph Analytical work. \layout Standard Drs. Frank and Schmalz will work together on analytical aspects of this project. This includes: \layout Enumerate Deriving analytical expressions for system-level cost/performance of our architectures, in terms of low-level device parameters and architectural parameters. \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Enumerate Deriving analytical expressions for the optimal values of system-level architect ural parameters in terms of lower-level parameters. \layout Enumerate Back-propagating the optimization of the system-level cost/performance to determine a utility function over the parameter space at all lower levels, including the device level. \layout Enumerate Incorporating considerations of data compression, error analysis, and error correction at all levels in the architecture and applications. This includes issues from quantum error correction at the low-level, to image error correction and lossy compression at the applications level. \layout Standard \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.III.b. Experimental Methods and Procedures \latex latex \backslash vspace{-8pt} \layout Standard Experiments in the proposed project center around simulation of our architecture s using our quantum circuit simulator. We will develop distributed versions of our simulator for faster simulation of large circuits. Such distributed simulations may be written to use the OCEAN distribution computation market project which has been recently proposed \begin_inset LatexCommand \cite{OCEAN-prop} \end_inset . The basic experimental methodology will be to code a quantum algorithm, then run a given simulation of the algorithm using a range of input sizes and settings of architectural parameter values. The resulting data points will be graphed and compared with theoretical graphs predicted by our analytical models of our quantum architectures. Rigorous analytical and statistical comparison will allow us to validate both the designs and the models. The simulator itself will be validated by checking that test programs run as predicted and produce correct outputs. \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.III.c. Plans for Preservation, Documentation, and Sharing of Research Products \latex latex \backslash vspace{-8pt} \layout Standard All software, design details, and publications produced by the project will be made permanently publicly available through the UF CISE department's web server. In addition, all major results will be archived via journal submissions. \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.III.d. Informal Collaborations \latex latex \backslash vspace{-8pt} \layout Standard The following researchers at other departments at UF and at other universities have agreed to informal collaboration on this project. \layout Description Douglas\SpecialChar ~ Cenzer\SpecialChar ~ (UF,\SpecialChar ~ Math\SpecialChar ~ dept.) works on computability and complexity theory in models for logic, including logic programming, artificial intelligence, graph theory and analysis. He is interested in the implications of quantum computing formathematical logic, complexity and recursion theory ( \emph on cf. \emph default \begin_inset LatexCommand \cite{Svozil-94a} \end_inset ). He is collaborating informally with us in the study of new universal parallel models of quantum computation (such as \begin_inset LatexCommand \cite{Benjamin-Johnson-98} \end_inset ). \latex latex \backslash vspace{-8pt} \layout Description Jeff\SpecialChar ~ Krause\SpecialChar ~ (UF,\SpecialChar ~ Chemistry\SpecialChar ~ dept.) is interested in electron magnetic resonance and other proposed experimental realizations of quantum computing. We will consult with him regarding the realism of our proposed abstract models of quantum bit-devices. \latex latex \backslash vspace{-8pt} \layout Description Igor\SpecialChar ~ Markov\SpecialChar ~ (U.\SpecialChar ~ Michigan,\SpecialChar ~ EECS\SpecialChar ~ dept.) was recently funded by DARPA to develop logic synthesis tools for quantum circuits, as well as quantum algorithms for logic synthesis of classical circuits \begin_inset LatexCommand \cite{Hayes-Markov-01} \end_inset . He has agreed to collaborate informally with our project, to, for example, apply his quantum circuit synthesis and optimization techniques to our design components, and share simulation tools for quantum circuits. \layout Standard \latex latex \backslash vspace{-8pt} \layout Subsection* C.IV. Broader Impacts of Proposed Activity \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.IV.a. Integration of Research and Education \latex latex \backslash vspace{-8pt} \layout Standard This research will be highly integrated with our educational work, due to: \layout Enumerate PI Frank's bi-yearly course on \emph on Physical Limits of Computation \emph default \begin_inset LatexCommand \cite{PhysLim} \end_inset , which was very popular among both CISE and ECE students (last year it quickly filled its 50-student enrollment limit) and among both graduate and undergraduate students. The course received extremely high evaluations from both groups. The course covers both reversible and quantum computing, and includes student group projects that experiment with these concepts. (For example, last year one group simulated Grover's algorithm.) These projects will be able to make use of the simulator tools, architectural components, and language compilers that we will be developing. \latex latex \backslash setlength{ \backslash itemsep}{-3pt} \backslash setlength{ \backslash parsep}{0pt} \backslash setlength{ \backslash partopsep}{0pt} \backslash setlength{ \backslash topsep}{0pt} \layout Enumerate Both Frank and Schmalz are heavily involved in the CISE department's Senior Design course, CIS4914 \begin_inset LatexCommand \cite{srproj} \end_inset \latex latex --- \latex default the ABET-approved capstone senior design course required of all engineering students in our department. Dr.\SpecialChar ~ Schmalz organizes the course, and offers project topics, and Dr.\SpecialChar ~ Frank supervises several dozen individual projects annually. Many of Dr.\SpecialChar ~ Frank's students' senior projects already have been in the area of reversible and/or quantum computing \begin_inset LatexCommand \cite{rev-people} \end_inset . The results of this research would directly feed in to improve the resources available to these students, and the quality of the resulting projects. Additionally, many senior projects would in turn feed back to contribute to this research. \layout Enumerate Dr.\SpecialChar ~ Frank is in the process of writing a textbook \emph on Reversible Computing: From Theory to Engineering \emph default to be published by MIT Press \begin_inset LatexCommand \cite{Frank-Vieri-02} \end_inset , based on Dr.\SpecialChar ~ Frank's Ph.D. thesis and the results of his recent systems engineering research. The book is already planned to include major portions on reversible computer systems engineering, and can easily be modified to include the quantum computing aspects of this work. \layout Enumerate Dr.\SpecialChar ~ Frank and Dr. Schmalz both regularly teach the undergraduate computer organization course at UF, CDA3101 \begin_inset LatexCommand \cite{computer-org} \end_inset , and Dr.\SpecialChar ~ Frank will also teach the graduate computer architecture course starting this Fall. Dr.\SpecialChar ~ Frank's reversible computing work is already feeding into these courses, in the form of a reversible MIPS simulator written by one of his Masters' students, which will be used in the undegraduate course. Dr.\SpecialChar ~ Frank also plans to incorporate a significant treatment of systems engineerin g principles, and a few lectures on reversible and quantum architectures, into his graduate architecture course this Fall. As the quantum architectures proposed in this project are developed, they will help improve the maturity of the quantum computing coverage in the graduate architecture course. \layout Enumerate Dr.\SpecialChar ~ Schmalz has also taught at UF a three-semester course series in cryptology, which includes one semester concentrating in quantum cryptography and quantum computing. \layout Standard \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.IV.b. Participation by Underrepresented Groups \latex latex \backslash vspace{-8pt} \layout Standard Dr.\SpecialChar ~ Frank has always encouraged participation by women, minorities, and other underrepresented groups on his research projects. He also serves in UF's University Minority Mentoring Program, and he works to help ensure diversity in the student body through his role on the CISE department's graduate committee. This committee strives to ensure, for example, that women and students from underrepresented nations (unfortunately, among graduate students, the U.S. is underrepresented!) are especially encouraged to attend the UF CISE graduate program. Dr.\SpecialChar ~ Frank has supervised a wide diversity of students on his own projects, and will continue to do so in the future. For example, last year he supervised a senior highest-honors project by an African-American student, DoRon Motter, who made a major theoretical contribution \begin_inset LatexCommand \cite{Motter-00} \end_inset to the study of reversible simulations of quantum mechanics. \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.IV.c. Enhancements to Infrastructure for Research and Education \latex latex \backslash vspace{-8pt} \layout Standard The quantum computer simulators and architectural components we develop will be made freely, publicly available as they are developed through our group's web site \begin_inset LatexCommand \cite{rcgroup} \end_inset , and publicized at conferences, so that other researchers, instructors, and students at other universities who are interested in quantum computing can benefit from these tools for use in their own projects. \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.IV.d. Dissemination of Results \latex latex \backslash vspace{-8pt} \layout Standard As outlined in the objectives list above, we are planning to regularly produce papers on all stages of this work. We will balance conference publications (to educate the community) with journal articles (to archive the resutls). We intend to strongly encourage all graduate students involved in this project to contribute to these publication efforts. \latex latex \backslash vspace{-8pt} \layout Subsubsection* C.IV.e. Potential Benefits to Society at Large \latex latex \backslash vspace{-8pt} \layout Standard Since scalable quantum computing is still likely one or two decades distant, the benefits to society will be long-term. However, it is hoped that by providing guidance to device physicists and quantum computer engineers, this research will significantly speed the advance of quantum computing, perhaps accelerating its practical implementation by several years. By speeding the arrival of the new applications (particularly quantum physical simulations for drug design, materials engineering, and molecular nanotechnolog y) that will be enabled by practical quantum computing, this research is projected to have enormous societal benefits. We estimate offhand that the potential value to society of speeding the eventual development of quantum computers by several years is probably at least in the billions of dollars. \latex latex \backslash vspace{-8pt} \layout Subsection* C.V. Results from Prior NSF Support \latex latex \backslash vspace{-8pt} \layout Standard Neither PI has had NSF support in the last 5 years. However, Dr.\SpecialChar ~ Frank held an NSF graduate fellowship from 1993-1995, the first 2 years of which he used for his Masters' work on decision-theoretic AI \begin_inset LatexCommand \cite{Frank-94} \end_inset , and the last year of which he used while working briefly on DNA computing at MIT. It happened that the technique for universal computing with DNA which Frank developed during that period was forced to be reversible due to fundamental thermochemical reasons, and so, during the course of this work, Frank became familiar with the field of reversible computing, which led him to pursue the more practical (non-biological) line of reversible computer engineering research that he conducted during his Ph.D. studies and is continuing now (discussed in \latex latex { \backslash S} \latex default C.II.a above). Thus, this graduate NSF support led, if indirectly, to a Ph.D. thesis and to many interesting published results \begin_inset LatexCommand \cite{Frank-94,Frank-Knight-98,Frank-etal-98,Frank-etal-98a,Frank-99} \end_inset and available web materials, and to the concept for the quantum computing work which we are now proposing. \layout Standard \latex latex \backslash cleardoublepage \layout Standard \begin_inset LatexCommand \BibTeX[plain]{shortstr,refs,qcstr,qc,mpf,mit,rcthy,thermcomp,image,physcomp,websites,entropy,ca} \end_inset \the_end