Fundemental of Quantum Computing
Quantum Logic - Qubit A qubit (or quantum bit) is the quantum mechanical analogue of a classical bit. Unlike the traditional computing system which the bit only represented one state (either 1 or 0), qubit can represented both state simultaneously because of the concept in quantum mechanics called superposition.
Superposition
- Concept : a fundamental principle in quantum mechanics that allows qubits to exist in multiple states simultaneously.
- Representation: the state of quantum particle can be visualized form a form called Bloch Sophere and Bloch Circle as an arrow pointing in 3D space. If the arrow points up, it represents the 0 state; if it points down, it represents the 1 state. However, in superposition, the arrow can point in any direction, signifying a combination state of 0 and 1 like the following formula($\alpha, \beta$ is the probability for the state): $$ \Psi = \alpha\vert0\rangle + \beta\vert1\rangle$$
- Measurement: when we want to measure a qubit, it collapses into one of the basis states (0 or 1) with a probability determined by the direction of the arrow. The more upward the arrow points, the higher the probability of measuring 0. So the measured direction would determined the result of the qubit’s state.
Entanglement
- Definition: is a phenomenon that qubits become correlated and are no longer independent entities. When qubits are entangled, the state of one qubit is directly related to the state of another, even if they are physically separated. No matter how fair between these two entangled qubits pair.
- Influence: entangled qubits exhibit correlated probability distributions. Changing the state of one qubit affects the probability distribution of the entire system, making the qubits interdependent. Bcause of the probabilities become correlated, leading to a joint probability distribution for all possible states.
Interference
- Definition: to the constructive or destructive combination of probability amplitudes during computations. It aims to enhance the probability of obtaining the correct answer while diminishing the probabilities of incorrect outcomes.
Algorithms
- Shor’s algorithm a prime factorization algorithm that can search an unsorted database quadratically faster than classical algorithms, but heaven’t be implemented in real quantum computer.
- Grover’s Algorithm a search algorithm that can search an unsorted database quadratically faster than classical algorithms with time complexity in $O(\sqrt{n})$.
IBM Quantum Learning
Gates and Circuits qubits are not really “inputs” in the classical circut. The quantum circuit represents time running from left to right. The “wires” represent the sequence of operations. The wires of the circuit diagram could correspond to a single qubit, and each gate corresponds to a change in the spin or polarization of the qubit. So that the output states may be entangled, meaning we may not be able to write them as a product of individual qubit states
Reversibility Since the gate operation note $\hat{U}$ is a linear transformation(represented as matrices) and is unitary, so the quautum computer is reversiable. The only operator that is not reversible is the operation of measurement. During measurement, the quantum state collapses to one of the basis states
Single-Qubit Gates
NOT(X) Gate
The NOT gate or X gate, also known as a bit flip gate, flips $\vert0\rangle$ and $\vert1\rangle$:$$\begin{aligned}X\vert0\rangle = \vert1\rangle\ ,X\vert1\rangle=\vert0\rangle \end{aligned} $$
Y Gate
The Y gate swaps the amplitudes of $\vert0\rangle$ and $\vert1\rangle$, multiplies each amplitude by $i$ direction , and negates the amplitude of $\vert1\rangle$. It is a phase shift and bit flip gate: $$\begin{aligned}Y\vert0\rangle = i\vert1\rangle\ ,Y\vert1\rangle = -i\vert0\rangle\end{aligned}$$
- Z Gate
The Z gate negates the amplitude of $Z\vert1\rangle$. It is a phase shift gate: $$\begin{aligned}Z\vert0\rangle = \vert0\rangle\ ,Z\vert1\rangle = -\vert1\rangle\end{aligned}$$
Pauli Gates
Physicists usually prefer to use this notation, while computer scientists prefer X, Y, Z. Both of them are interchangeable.Hadamard(H) Gate
The Hadamard gate, H, allows us to create superpositions. H applied to $\vert0\rangle$ or $\vert1\rangle$ gives the following output: $$\begin{aligned}H\vert0\rangle = \frac{1}{\sqrt{2}}(\vert0\rangle + \vert1\rangle) = \vert+\rangle\H\vert1\rangle = \frac{1}{\sqrt{2}}(\vert0\rangle - \vert1\rangle) = \vert-\rangle \end{aligned}$$ also, H converts the z-basis into the x-basis.Phase Gate
The phase gate rotates the phase of the $\vert1\rangle$ state by an angle $\phi$ about the z-axis in the Bloch sphere.Note the when $\phi = \pi/2$ or $\pi/4$, there are special gates called S($\pi$/4) and T gates respectively.
Two-Qubit Gates
- Controlled NOT (CNOT) Gate: The controlled NOT (CNOT) gate flips the second qubit (target qubit) only if the first qubit (control qubit) is in the $\vert1\rangle$ state
- SWAP Gate: The SWAP gate swaps two qubits
Three-Qubit Gates
Fredkin Gate: The Fredkin gate (controlled SWAP or CSWAP gate) is a three-qubit gate that performs a controlled SWAP. If the first qubit is $\vert0\rangle$, then nothing happens;while if the irst qubit is $\vert1\rangle$, then the SWAP gate is implemented on qubits 2 and 3.
Input Output $C$ $I_1$ $I_2$ $C$ $O_1$ $O_2$ 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 Toffoli Gate: The Toffoli gate (controlled controlled-NOT or CCNOT gate) is a three-qubit gate that applies the NOT gate to the third qubit (target) only if both of the first two qubits ($\vert C_1\rangle, \vert C_2\rangle$) are $\vert 1\rangle$, $\vert C_1\rangle, \vert C_2\rangle$ and $\vert t\rangle$ inputs are transformed to $\vert C_1\rangle, \vert C_2\rangle$ and $\vert t\bigoplus C_1 \cdot C_2\rangle$. Toffoli can implement AND (fix the 3rd input to 0), NOT (fix the 1st and 2nd input to 1) and NAND (fix the 3rd input to 1).
Truth table for the Toffoli gate:
Input Output $C_1$ $C_2$ $t$ $C_1$ $C_2$ $t\bigoplus C_1 \cdot C_2$ 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0
Measurement: Measurement takes a quantum state and collapses it to one of the basis states. Sinece the represents a qubit where a superposition is $$ \Psi = \alpha\vert0\rangle + \beta\vert1\rangle$$ We measure $\vert0\rangle$ with probability $\vert \alpha^2 \vert$, or $\vert1\rangle$ with probability $\vert \beta^2 \vert$. The collapse is considered to be instantaneous.
- Bell State Circuit Bell state is a specific quantum states of two qubits that represent the simplest examples of quantum entanglement. Bell state circuit creates one of the Bell entangled states, which needs two-qubit gates. And creates an entangled state of three qubits called a Greenberger-Horne-Zeilinger (GHZ) state. An entangled state of three or more particles is called multipartite entanglement.
Paper Reading
Basic Info.
Extending C++ for Heterogeneous Quantum-Classical Computing
Motivation and Problem Definition :::info Propose a language extension which targeting on physical and virtual quantum computing backends enables heterogeneous quantum-classical programming,compilation, and execution in a single-source context. ::: Solution Proposal :::info Beacauce of the current quantum-classical programming toolchain lack in some form with regards to tight integration of HPC resources with quantum co-processors.The author describe a mechanism that seeks to fill this void in the quantum scientific computing software stack.The hierarchy of the stack is below:
It contains QCOR, Clang, and XACC three parts. QCOR implements the specification put forward in by building upon the XACC quantum programming framework with accomplished via extension of core Clang plugin interfaces.Finally incorporated it into main quantum computing hardware vendors. :::
Detail about Each Part
XACC
- Three extensible layered architecture
- Frontend as a Compiler that maps kernel source strings to instances of the IR.
- Middle-end exposes extension points defining the quantum IR which composed of Instruction and CompositeInstruction service interfaces for gate model computing, especialy for concrete quantum gates and composites of those gates.The middle-end also exposes an IRTransformation service interface for the general transformation of CompositeInstructions.
- Backend(Accelerator) as an extensible interface for injecting physical and virtual quantum computing backends.
- Allocation of quantum memory (a register of qubits) called the AcceleratorBuffer.
- Compilation optimization and placement routines will be injected as implementations of the IRTransformation.
- Kernels in qcor will have a corresponding CompositeInstruction instance that will be generated by variants of the Compiler service.
Clang Plugins
- Frontend for the LLVM compiler infrastructure, converting C++ source code into LLVM’s IR.
- Extend key points of the preprocessing workflow with custom plugin implementations instead of making core, permanent modifications to the core of Clang or LLVM. => Easy to maintain and more flexible.
- Proposed two new plugin interface
- SyntaxHandler
Allows embedding of domain-specific languages into C++ function definitions.The team leverages this plugin interface to translate our quantum kernel expressions to valid C++ API calls.
How the Clang SyntaxHandler works
Step 1 Using blalanced-delimiter matching to extracted the function body (collecting all tokens prior to the closing “}”).The the function body would not be valid. Step 2 The token stream is then provided to the syntax-handler plugin along with information about the already-parsed function declarator (contain the function name & arguments). Step 3 The plugin then return a replacement text stream (subjected to tokenization) for function
- SyntaxHandler
Allows embedding of domain-specific languages into C++ function definitions.The team leverages this plugin interface to translate our quantum kernel expressions to valid C++ API calls.
QCOR for heterogeneous quantum-classical quantum computing that leverages a shared memory model and an asynchronous task-based execution model. => ensures quantum kernel domain specific languages (invalid code with respect to other compilers) are mapped to appropriate and valid sub-types of the QuantumKernel abstraction.
- Three abstractions (operators, optimizer and objectvefunction ) for composing hybrid variational algorithms and the taskInitiate() call for asynchronous execution.
Runtime Quantum Kernel Annotated with a ** qpu ** attribute, return void, and can take any arguments(at least one). The function body can contain quantum code expressions written in any available quantum language. Provides a QuantumKernel class that follows the familiar CRTP(curiously recurring template pattern) and is intended to serve as a super-type for concrete kernel implementations. The design strategy for sub-types is to inherit from QuantumKernel.
Quantum Runtime Provides a class API for compiler and runtime developers to execute low-level quantum gate instructions on the specified quantum backend. Also provides an extensible hardware abstraction layer enabling typical quantum instruction execution. Promotes the utility of different models of quantumclassical integration: 1. remote, near-term: Be implemented to queue gate instructions as their corresponding API call is invoked. 2. feed-foword
NISQ(the main model for quantum computing) provides a submit() call that flushes the internal representation, sending the entirety of its contents to be executed on the compiled backend. Its API represents a public interface for constructing XACC IR instances.
FTQC(the team proposed for various qubit’s situation) is to support quantum hardware capable of fast feedback between the quantum processor and the classical processor => to fasten and reflect any measurement results to the classical code as return values of the QuantumRuntime::mz() function, enables flexible control flow for error correction.
Operator, Optimizer, and Objective Function enable efficient expression of common quantum algorithms, specifically those that are variational and target potential near-term quantum hardware.
- Operators represents quantum mechanical operators or compositions of operators that can observe unmeasured quantum kernels and then returning a list of measured quantum kernels.
- Optimizer represents a multi-variate function optimization strategy(COBYLA, L-BFGS, Adam, etc.).
- ObjectiveFunction represents multi-variate function that returns a scalar value, and evaluation of the function to produce that scalar requires quantum co-processor execution.
- Task-based Asynchronous Execution Defines a Handle type that is returned by taskInitiate() and is used by programmers to synchronize the host and execution thread. The synchronization should cause the host thread to wait if the execution thread is not complete, and return a ResultsBuffer(provide the optimal value and parameters) upon completion.
Compiler The primary goal of the qcor compiler is to map quantum kernel functions to appropriate definitions of QuantumKernel sub-types.Enabling QCOR extensions to Clang and integration with the QCOR runtime library. Syntax Handler Provides a hook for DSL to replace the input stream token with valid C++ API calls to Clang after lexing and preprocessing but before the AST generated. The team proposes a QCORSyntaxHandler implementation that enables the qcor C++ language extension to fulfill two tasks: 1.Translate the quantum code into QuantumRuntime Using TokenCollector’s collect() method to map to QuantumRuntime API calls and tehn it can translate the token to another quantum language but both of them using the same quantum kernel. 2.Define a QuantumKernel subtype and associated function calls. Rewrite the quantum kernel function and define a new QuantumKernel<Derived, Args…> sub-type, incorporating the results of the first task - the rewritten QuantumRuntime code. Pass Manager Provide a class called PassManager to handle the runtime optimization passes which is structured by the runtime circuit optimization tasks and levels (set of passes). The goal of levels is to balance gate count reduction and optimization time. Analyzes detailed statistics about each pass, such as the execution time, the gate count distribution before and after the pass, Placement In qcor’s compile time, it takes into account the hardware placement functionality and it’s involve two things need to be considered: 1.Permutations of gates and qubits Using swap-shorstest path algorithm to swap two-qubit gates between uncoupled qubits are swapped to satisfy the coupling graph. 2.Taking the advantage of best-performing qubits by directly logical-physical qubit mapping. Supplying a ‘-qubit-map’ option along with a sequence of qubit indices to qcor, the runtime placement service will map logical qubits to the physical ones according to this map. Automated Error Mitigation Enables automated error mitigation via decoration of the Accelerator backend. The AcceleratorDecorator service interface is used to analyze or update the incoming compiled circuit, execute it, and analyze and mitigate the results based on the sub-type’s implemented strategy. JIT Quantum Kernel Compilation To build up quantum circuits at runtime based on pertinent runtime information.The team proposes a new data type - QJIT, which provides quantum kernel JIT execution.The jit_compile would take quantum kernel as a source string as input and then compiled to LLVM IR module.Next,it would passes to LLVM JIT’s data structure for jit compilation.
Results
Overall Compiler Performance Circuit optimization results for benchmarks using (1) individual qcor passes and (2) qcor’s level-1 optimization sequence.
The number of two-qubit gates after placement using various placement strategies
Reading Materials
- Quantum Computers Explained – Limits of Human Technology
- The Map of Quantum Computing | Quantum Computers Explained
- Learn quantum computing: a field guide
- Try out some circuit examples
- Extending C++ for Heterogeneous Quantum-Classical Computing
- (Optional) Quantum Algorithm Implementations for Beginners
- (Optional) A Leap among Quantum Computing and Quantum Neural Networks: A Survey
- (Optional) 俗說量子
- Introduction to Quantum Computing
Building Environment
Reference OS : Ubuntu 20.04
The goal is to install XACC & QCOR on ubuntu 20.04 and run the example code below:
- Result:
Basic Info.
Update:since some python package is unsupported for arm-based’s linux, so I change my target hardware from Apple M1 to Intel X86’s computer and success install xacc. :::success Notice: If you want to build xacc and qcor in docker container, make sure you container is mounted by Docker Socket, or you need to remove the container and rerun the container with
-v /var/run/docker.sock:/var/run/docker.sock
to mount socket so that you can use host’s docekr engine to install qcor instead of reinstall docker in container again. :::
- Environmeent
- GCC version
XACC
Follow the installation doc.
- Step 1 : Prerequisites Since the version of Ubuntu is 20.04. I follow the guide for Ubuntu 18.04 in Prerequisites secion in the following:
Step 2 : Build XACC
- install recent version of CMake through Python Pip.
1
sudo python3 -m pip install cmake
- clone and build XACC
error issues
error 1 : couldn’t find openssl
1 2 3 4 5 6 7
-- Could NOT find MbedTLS (missing: MBEDTLS_INCLUDE_DIRS MBEDTLS_LIBRARY MBEDX509_LIBRARY MBEDCRYPTO_LIBRARY) CMake Error at tpls/cpr/CMakeLists.txt:112 (message): No valid SSL backend found! Please install OpenSSL, Mbed TLS or disable SSL by setting CPR_ENABLE_SSL to OFF. -- Configuring incomplete, errors occurred!
solution
sudo apt-get install libssl-dev
error 2 :couldn’t found python interpreter
solution add the following flag after
cmake ...
-DPython_EXECUTABLE=/path/to/python3
error 3 : lack of python library
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
-- Found Python version 3.8.10. Traceback (most recent call last): File "<string>", line 1, in <module> ModuleNotFoundError: No module named 'qiskit' -- Qiskit not found. To use the Aer Pulse Simulator, please install Qiskit. Traceback (most recent call last): File "<string>", line 1, in <module> ModuleNotFoundError: No module named 'rpcq' -- rpcq or requests not found. QCS Accelerator is still built, but tests will not available until you install them and re-run cmake. CMake Deprecation Warning at quantum/plugins/dwave/tpls/legacy-sapi-clients/c-client/CMakeLists.txt:1 (cmake_minimum_required): Compatibility with CMake < 3.5 will be removed from a future version of CMake. Update the VERSION argument <min> value or use a ...<max> suffix to tell CMake that the project does not need compatibility with older versions. Traceback (most recent call last): File "<string>", line 1, in <module> ModuleNotFoundError: No module named 'qsearch' -- QSearch not found. py-qsearch Synthesis not available until you install it. Traceback (most recent call last): File "<string>", line 1, in <module> ModuleNotFoundError: No module named 'qfactor' -- QFactor not found. py-qfactor Synthesis not available until you install it. -- Could NOT find Z3 (missing: Z3_LIBRARY Z3_INCLUDE_DIR) (Required is at least version "4.8.0") CMake Warning at quantum/plugins/placement/CMakeLists.txt:8 (message): Z3 library not found. TriQ placement plugin will not be installed. -- Building Staq Compiler. -- Could NOT find Qrack library (missing: find_library(QRACK_LIBRARY NAMES qrack)) Traceback (most recent call last): File "<string>", line 1, in <module> ModuleNotFoundError: No module named 'qat' -- QAT not found. Atos QLM Accelerator will not work. -- Found Python version 3.8.10. Building XACC Python API with /usr/include/python3.8 -- PYTHON: libpython3.8.so Traceback (most recent call last): File "<string>", line 1, in <module> ModuleNotFoundError: No module named 'skquant' -- Scikit-Quant not found. skquant Optimizer will not until you install it. Traceback (most recent call last): File "<string>", line 1, in <module> ModuleNotFoundError: No module named 'pelix'
solution
- Qiskit
pip install qiskit
- Qsearch
Need to install qsrs first,according to its wiki page
First, install the dependencies.
sudo apt install libopenblas-dev libceres-dev libgfortran-10-dev
then install Rust like as follows:curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh
Accept all of the default prompts. Then runsource ~/.cargo/env
, and switch to the nightly toolchain change the version of cargo and proc-marco2 to avoid the issue of unknown feature proc_macro_span_shrink :rustup default nightly && cargo update -p syn --precise 1.0.99; cargo update -p proc-macro2 --precise 1.0.43
Clone the Qsearch repo:git clone https://github.com/BQSKit/qsearch.git cd qsearch/qsrs
and run:pip install .
Finally install qsearchpip install qsearch
- Qfactor
1
pip install qfactor
- Z3
- rpcq
1
pip install rpcq
- QAT
1
pip install qat-compiler
- Skquant(Sci-quant)
1
pip install scikit-quant
- Qrack
- QLM accelerator
1
pip install qlmaas
- Qiskit
issue 3:unwind library support(only for non x86-based system)
Solution Download the patch file from the page In the root directory of xacc and run
patch -p1<path/to/patchfile.patch
issue 4: make install failed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
Usage: /usr/bin/strip <option(s)> in-file(s) Removes symbols and sections from files The options are: -I --input-target=<bfdname> Assume input file is in format <bfdname> -O --output-target=<bfdname> Create an output file in format <bfdname> -F --target=<bfdname> Set both input and output format to <bfdname> -p --preserve-dates Copy modified/access timestamps to the output -D --enable-deterministic-archives Produce deterministic output when stripping archives (default) -U --disable-deterministic-archives Disable -D behavior -R --remove-section=<name> Also remove section <name> from the output --remove-relocations <name> Remove relocations from section <name> -s --strip-all Remove all symbol and relocation information -g -S -d --strip-debug Remove all debugging symbols & sections --strip-dwo Remove all DWO sections --strip-unneeded Remove all symbols not needed by relocations --only-keep-debug Strip everything but the debug information -M --merge-notes Remove redundant entries in note sections (default) --no-merge-notes Do not attempt to remove redundant notes -N --strip-symbol=<name> Do not copy symbol <name> --keep-section=<name> Do not strip section <name> -K --keep-symbol=<name> Do not strip symbol <name> --keep-file-symbols Do not strip file symbol(s) -w --wildcard Permit wildcard in symbol comparison -x --discard-all Remove all non-global symbols -X --discard-locals Remove any compiler-generated symbols -v --verbose List all object files modified -V --version Display this program's version number -h --help Display this output --info List object formats & architectures supported -o <file> Place stripped output into <file> /usr/bin/strip: supported targets: elf64-littleaarch64 elf64-bigaarch64 elf32-littleaarch64 elf32-bigaarch64 elf32-littlearm elf32-bigarm elf64-little elf64-big elf32-little elf32-big srec symbolsrec verilog tekhex binary ihex plugin make[2]: *** [quantum/plugins/dwave/tpls/legacy-sapi-clients/c-client/CMakeFiles/dwave_sapi.dir/build.make:536: quantum/plugins/dwave/tpls/legacy-sapi-clients/c-client/libdwave_sapi.so] Error 1 make[2]: *** Deleting file 'quantum/plugins/dwave/tpls/legacy-sapi-clients/c-client/libdwave_sapi.so' make[1]: *** [CMakeFiles/Makefile2:5086: quantum/plugins/dwave/tpls/legacy-sapi-clients/c-client/CMakeFiles/dwave_sapi.dir/all] Error 2 make[1]: *** Waiting for unfinished jobs....
Ctest Result:
QCOR
Follow the installation doc.
- Step 1 : Install the aide-qc command line tool
Install the
aide-qc
tool, run the following from your local terminal.
|
|
Since I run the Ubuntu 20.04 using Docker and installation of aide-qc dependecies Docker