Please download to get full document.

View again

of 71
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report

Presentations & Public Speaking


Views: 7 | Pages: 71

Extension: PDF | Download: 0

Related documents
AFRL-IF-RS-TR Final Technical Report December 26 QUANTUM COMPUTING AND HIGH PERFORMANCE COMPUTING General Electric Global Research APPROVED FOR PUBLIC RELEASE; DISTRIBUTION UNLIMITED. STINFO COPY AIR FORCE RESEARCH LABORATORY INFORMATION DIRECTORATE ROME RESEARCH SITE ROME, NEW YORK NOTICE AND SIGNATURE PAGE Using Government drawings, specifications, or other data included in this document for any purpose other than Government procurement does not in any way obligate the U.S. Government. The fact that the Government formulated or supplied the drawings, specifications, or other data does not license the holder or any other person or corporation; or convey any rights or permission to manufacture, use, or sell any patented invention that may relate to them. This report was cleared for public release by the Air Force Research Laboratory Rome Research Site Public Affairs Office and is available to the general public, including foreign nationals. Copies may be obtained from the Defense Technical Information Center (DTIC) (http://www.dtic.mil). AFRL-IF-RS-TR HAS BEEN REVIEWED AND IS APPROVED FOR PUBLICATION IN ACCORDANCE WITH ASSIGNED DISTRIBUTION STATEMENT. FOR THE DIRECTOR: /s/ EARL M. BEDNAR Work Unit Manager /s/ JAMES A. COLLINS, Deputy Chief Advanced Computing Division Information Directorate This report is published in the interest of scientific and technical information exchange, and its publication does not constitute the Government s approval or disapproval of its ideas or findings. REPORT DOCUMENTATION PAGE Form Approved OMB No Public reporting burden for this collection of information is estimated to average hour per response, including the time for reviewing instructions, searching data sources, gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden to Washington Headquarters Service, Directorate for Information Operations and Reports, 25 Jefferson Davis Highway, Suite 24, Arlington, VA , and to the Office of Management and Budget, Paperwork Reduction Proect (74-88) Washington, DC 253. PLEASE DO NOT RETURN YOUR FORM TO THE ABOVE ADDRESS.. REPORT DATE (DD-MM-YYYY) DEC TITLE AND SUBTITLE 2. REPORT TYPE Final QUANTUM COMPUTING AND HIGH PERFORMANCE COMPUTING 3. DATES COVERED (From - To) Apr 6 Oct 6 5a. CONTRACT NUMBER FA875-5-C-58 5b. GRANT NUMBER 5c. PROGRAM ELEMENT NUMBER 6. AUTHOR(S) Kareem S. Aggour, Robert M. Mattheyses, Joseph Shultz, Brent H. Allen and Michael Lapinski 5d. PROJECT NUMBER NBGQ 5e. TASK NUMBER 5f. WORK UNIT NUMBER 7 7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) General Electric Global Research Research Circle Niskayuna NY SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) AFRL/IFTC 525 Brooks Rd Rome NY DISTRIBUTION AVAILABILITY STATEMENT APPROVED FOR PUBLIC RELEASE; DISTRIBUTION UNLIMITED. PA# PERFORMING ORGANIZATION REPORT NUMBER. SPONSOR/MONITOR'S ACRONYM(S). SPONSORING/MONITORING AGENCY REPORT NUMBER AFRL-IF-RS-TR SUPPLEMENTARY NOTES 4. ABSTRACT GE Global Research has enhanced a previously developed general-purpose quantum computer simulator, improving its efficiency and increasing its functionality. Matrix multiplication operations in the simulator were optimized by taking advantage of the particular structure of the matrices, significantly reducing the number of operations and memory overhead. The remaining operations were then distributed over a cluster, allowing feasible compute times for large quantum systems. The simulator was augmented to evaluate a step-by-step comparison of a quantum algorithm s ideal execution to its real-world performance, including errors. To facilitate the study of error propagation in a quantum system, the simulator s graphical user interface was enhanced to visualize the differences at each step in the algorithm s execution. To verify the simulator s accuracy, three ion trap-based experiments were simulated. The simulator output closely matches experimentalist s results, indicating that the simulator can accurately model such devices. Finally, alternative hardware platforms were researched to further improve the simulator performance. An FPGA-based accelerator was designed and simulated, resulting in substantial performance improvements over the original simulator. Together, this research produced a highly efficient quantum computer simulator capable of accurately modeling arbitrary algorithms on any hardware device. 5. SUBJECT TERMS Quantum Computing, FPGA, Quantum Computer Simulator, Paralelize 6. SECURITY CLASSIFICATION OF: 7. LIMITATION OF 8. NUMBER 9a. NAME OF RESPONSIBLE PERSON ABSTRACT OF PAGES a. REPORT U b. ABSTRACT U c. THIS PAGE U UL 7 Capt Earl Bednar 9b. TELEPHONE NUMBER (Include area code) Standard Form 298 (Rev. 8-98) Prescribed by ANSI Std. Z39.8 Table of Contents. PROJECT GOALS.... Enhance Existing Quantum Computer Simulator....2 Verify Simulator s Accuracy Against Experimental Data....3 Simulate Quantum Simulator on an FPGA SIMULATOR OVERVIEW State Representation and the Master Equation Evaluating Algorithms in Quantum express Input Algorithm Simulation Output SUMMARY OF KEY ACCOMPLISHMENTS DETAILS OF KEY ACCOMPLISHMENTS Performance Enhancement via Matrix Multiplication Optimizations Test Cases Multiplication Optimizations Optimization Results Port to High Performance Computing Cluster Density Matrix Distribution Distributed Simulation Ideal vs. Actual Density Matrix Comparisons Visualizing Matrix Differences Simulator Verification Experimental Data Collection Modeling Experiments in the Simulator Results Analysis Field Programmable Gate Array-Accelerated Simulation FPGA Hardware & Tools FPGA Design Design Limitations Testing Procedure Results CONCLUSIONS Proposed Future Work ACKNOWLEDGEMENTS REFERENCES...62 Appendix A FPGA Floating Point Formats...64 i Table of Figures Figure : Sample State XML Configuration File...5 Figure 2: Sample Algorithm XML Configuration File for 3 Qubit Test Case...6 Figure 3: Sample Gate XML Configuration File...6 Figure 4: Simulation Without Decoherence Function...7 Figure 5: Simulation With Decoherence Function...9 Figure 6: Sample Decoherence Matrix in XML... Figure 7: Sample Noise in XML... Figure 8: 3 Qubit Test Case...3 Figure 9: 5 Qubit Test Case...3 Figure : 7 Qubit Test Case (Shor s Algorithm)...4 Figure : 3 Qubit Inverse Fourier Transform for 7 Qubit Test Case...4 Figure 2: Non-Optimized, No Decoherence Matrix Simulation...6 Figure 3: Standard No Decoherence Matrix Simulation...8 Figure 4: Canonical Density Matrix Multiplication, N = 4, g = Figure 5: Density Matrix Permutation Algorithm...2 Figure 6: First Portion of 7 Qubit Shor s Algorithm...2 Figure 7: First Portion of 7 Qubit Shor s Algorithm with Permutation...2 Figure 8: Phase Decoherence Matrix Simulation Algorithm...23 Figure 9: Simulation Performance Improvement...25 Figure 2: Quantum express Connected to Either a Local or Remote Server...26 Figure 2: Script to Start Web Server on Head Node (startwebserver.sh)...26 Figure 22: Script to Start a Cluster Node (startnode.sh)...27 Figure 23: XML Configuration for Head Node to Find Cluster Nodes (nodes.xml)...27 Figure 24: Cluster Node Communication...28 Figure 25: Density Matrix Column Division Example, N = 4, g = Figure 26: Density Matrix Row Division Example, N = 4, g = Figure 27: Distributed Simulation Algorithm...3 Figure 28: Distributed Simulation Times vs. Number of Nodes...3 Figure 29: Distributed Simulation Improvements Compared to Non-Distributed Implementation...32 Figure 3: Decoherence Simulation Performance Improvement from Original Implementation...33 Figure 3: Example Matrix Difference Visualizations, N = Figure 32: Ideal vs. Actual Matrix Calculation XML Parameter...35 Figure 33: Deutsch-Jozsa Algorithm []...37 Figure 34: Experimental Implementation of the Deutsch-Jozsa Algorithm []...37 Figure 35: GUI View of the Deutsch-Jozsa Circuits...38 Figure 36: Grover Algorithm [2]...4 Figure 37: Experimental Implementation of the Grover Algorithm [2]...4 Figure 38: GUI View of a Grover Circuit...42 Figure 39: Experimental Implementation of the Semi-classical QFT Algorithm..43 Figure 4: GUI View of the Semi-classical QFT Circuit...44 Figure 4: FPGA & GPP Simulator Architecture...5 ii Figure 42: Architecture of Original GPP Implementation...5 Figure 43: Architecture of FPGA Implementation...52 Figure 44: Iteration Reduction in Evaluating Master Equation for Gate Size g = Figure 45: Iteration Reduction in Evaluating Master Equation for Gate Size g = Figure 46: Un-Optimized Pipeline...54 Figure 47: Optimized Pipeline...54 Figure 48: DIMETalk Diagram for the FPGA Accelerator...56 Figure 49: Speed-up of FPGA vs. Single Processor GPP Implementation...58 Figure 5: Floating Point Formats...64 iii Table of Tables Table : Simulation Times Before Optimization...5 Table 2: Post-Optimization Simulation Times...24 Table 3: Decoherence Improvement from Original Implementation...24 Table 4: Distributed Simulation Times...3 Table 5: Distributed Simulation Time Improvement Compared to Non-Distributed Simulation...3 Table 6: Distributed Simulation Time Comparison...32 Table 7: Decoherence Improvement from Original Implementation...33 Table 8: Ideal vs. Actual Heatmap Default Cutoffs...34 Table 9: Constant and Balanced Functions...37 Table : Deutsch-Jozsa Simulator Results with No Noise...39 Table : Grover Simulator Results with No Noise...42 Table 2: Semi-classical QFT Simulator Results with No Noise...45 Table 3: Simulation Maximum Absolute Probability Error with No Noise (%)...45 Table 4: Experimental and Simulation Fidelities (%)...46 Table 5: Minimum Gate Noise for Comparable Experimental and Simulation Fidelities...47 Table 6: Precision Comparison for 3 Qubit Test Case...59 Table 7: Precision Comparison for 5 Qubit Test Case...59 iv . PROJECT GOALS This effort is based on a quantum computer simulator designed and developed by GE Global Research (GEGR) and Lockheed Martin (LM) from 22 through 24. The simulator, Quantum express (QX), is capable of accurately simulating any quantum algorithm on any quantum hardware device and is capable of simulating errors from both hardware device imperfections and decoherence.. Enhance Existing Quantum Computer Simulator The first obective of this research was to enhance QX, improving its efficiency and increasing its functionality. These enhancements began with researching improvements in the matrix multiplication algorithms used for simulating gate operations. Next, GEGR ported QX to Rome Labs high performance-computing environment to significantly increase the performance of the system and the number of qubits that can be simulated by exploiting parallelism. Finally, QX was enhanced to simulate, in parallel, the algorithm's execution in both ideal and actual circumstances. Representing the state of the system under both conditions and visualizing the difference at each step can provide important capabilities for studying the effects of errors and error propagation in a quantum system. Increasing the simulator s functionality and improving its performance through these approaches will enable the investigation of error correction schemes, which will allow researchers to quantify the amount of error correction required to develop a large-scale quantum computer with high fidelity..2 Verify Simulator s Accuracy Against Experimental Data The second goal of this proect was to verify the simulator s accuracy by comparing its results to published data from experimental quantum computers. Ion trap quantum computers were chosen for the comparison, for two main reasons. First, they are one of the most promising implementations of quantum computers, with a vigorous research community. Second, the existing Quantum express simulations were based on nuclear magnetic resonance, and testing against ion trap experiments would both be an independent validation and extend the existing library of simulations. The main steps involved in this validation were: Identification of published experiments Acquisition of experimental data Modeling of the experiments in Quantum express Comparison of the simulation and ideal results Comparison of the simulation and experimental results.3 Simulate Quantum Simulator on an FPGA The final goal of this effort was to research alternative hardware platforms to improve the performance of the quantum computer simulator. The application of Field Programmable Gate Arrays (FPGAs) to this problem could significantly increase both the speed of quantum simulation runs and the number of qubits that could be simulated, providing a very promising route to improve the applicability of quantum computer simulation to the general quantum computing research community. GEGR selected a specific FPGA device and associated memory model to be simulated, and then developed an FPGA-based simulation of the Quantum express engine. This FPGA simulation was used to determine efficient data mappings for quantum algorithm simulations, in order to minimize memory contention and gain the greatest possible acceleration in the simulator s performance. 2. SIMULATOR OVERVIEW Quantum Computing (QC) research has gained momentum due to several theoretical analyses that indicate that QC is significantly more efficient at solving certain classes of problems than classical computing []. While experimental validation will be required, the primitive nature of today s QC hardware only allows practical testing of trivial examples. Thus, a robust simulator is needed to study complex quantum computing issues. Most QC simulators model ideal operations and cannot predict the actual time required to execute an algorithm, nor can they quantify the effects of errors in the calculation. GE Global Research and Lockheed Martin ointly developed a QC simulator, Quantum express, that models a variety of physical hardware implementations. Quantum express (QX) also allows for the simulation of errors in a quantum computer. Errors typically arise from two sources: ) hardware device imperfections, and 2) decoherence (the natural tendency of a quantum system to interact with its environment and move from an ordered state to a random state). Both of these sources of error can be simulated. Most quantum computer simulators are designed to simulate a single algorithm, most commonly Shor s factoring algorithm, on a single type of hardware. QX can be used to implement any quantum algorithm running on any type of hardware, and can report proected algorithm execution times on the quantum device. QX has a flexible architecture that can be configured entirely through XML files. This enables researchers to explore new algorithms and gate architectures insilico before they can be physically realized, without having to write any code. QX has been developed entirely in Java.4.2 using obect-oriented design paradigms. It is platform independent, and has been successfully executed in Windows, UNIX, and Linux environments [2]. 2. State Representation and the Master Equation Most quantum computer simulators deal only with pure states and thus cannot accommodate direct error simulation. QX uses the density matrix quantum state representation and time evolution according to a master equation, allowing us to naturally simulate the effects of decoherence. The simulator s ability to accommodate decoherence does come at a price, however. In the density matrix representation, a state of N qubits is represented by a 2 N x2 N square matrix 2 instead of a 2 N -element vector. Because QX uses the density matrix representation, it cannot handle as many qubits as a pure-state simulator could. In the absence of decoherence, a state vector (i.e., a general superposition) evolves in time during a single operation according to a Schrödinger equation [3]: d i h ψ = H ψ, () dt where the matrix H is known as a Hamiltonian, which is some linear Hermitian operator, and ħ is a physical constant known as Planck s constant. An operator (represented as a matrix) is called Hermitian if it is equal to its own transposed complex-conugate. The vector ψ, known as a ket, is the complex vector associated with state ψ. In the presence of decoherence, and with some approximations, the evolution is described more generally by a master equation such as [4]: d h ρ = i[ H, ρ] [ V,[ V, ρ]], (2) dt where square brackets denote commutators (the commutator of two matrix operators A and B is denoted [A,B]) defined as: [ A, B] = AB BA (3) and ρ is a density matrix, a natural way of representing a statistical distribution of states. For a pure state (a completely known superposition), the density matrix has the form [4]: ρ = ψ ψ, (4) where ψ is the complex conugate (also referred to as the bra ) of ψ. denotes the outer product of the ket and bra. A state remains pure (no decoherence) if V= in (2), in which case the master equation is equivalent to the Schrödinger equation from (). Otherwise, the master equation describes, in a statistical sense, the decohering influence of the environment. 2.2 Evaluating Algorithms in Quantum express 2.2. Input Quantum express requires two primary inputs: () a state file and (2) an algorithm file. In the state file a base must be specified, indicating whether the states of the system represent qubits (base 2), qutrits (base 3), or more. While this document will always refer to qubits (2 N ), it should be understood that QX can also handle qutrits (3 N ) and other higher-order base states, at the user s ψ ψ 3 discretion. The initial state of the system is represented by a vector of 2 N elements (again, presuming base 2), where N is the number of distinct qubits. The base and initial states of Quantum express are specified in an extensible Mark-up Language (XML) file using the World Wide Web Consortium s (W3C 2) Mathematical Mark-up Language (MathML) specification. This file contains sets of vectors defining both the initial states and states of interest. These states are effectively identical in construction, except the initial states also have probability values associated with them indicating the probability that the initial system is in that state. States of interest are defined for the purpose of allowing QX to observe certain states. At any time during the execution of an algorithm, the system can be evaluated to determine the probability of it being in each of these observed states. At the end of the execution of an algorithm, the probabilities of each of the states of interest are displayed to give an indication of the final superposition of the system. An excerpt from a state configuration file for a base 2, 3 qubit system can be seen in Figure. From this figure, we can see that the vectors for both the initial and interest states are complex with 2 3 = 8 elements per vector. quantum-states class com.quantum.system.qx.quantumsystemqx /class base 2 /base qu-number 3 /qu-number initial-states state !-- + -- id + /id vector cn type= complex-cartesian sep/ /cn cn type= complex-cartesian sep/ /cn cn type= complex-cartesian sep/ /cn cn type= complex-cartesian sep/ /cn cn type= complex-cartesian sep/ /cn cn type= complex-cartesian sep/ /cn cn type= complex-cartesian sep/ /cn cn type= complex-cartesian sep/ /cn /vector probability /probability /state /initial-states interest-states state !-- -- id /id vector cn type= complex-cartesian sep/ /cn cn type= complex-cartesian sep/ /cn cn type= complex-cartesian sep/ /cn cn type= complex-cartesian sep/ /cn cn type= complex-cartesian sep/ /cn cn type= complex-cartesian sep/ /cn cn type= complex-cartesian sep/ /cn 4 cn type= complex-cartesian sep/ /cn /vector /state state !-- -- id /id vector cn type= complex-cartesi
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks