RONCC
/
HPC-Tools-for-Quantum-Computing


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835
							<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title>QCGPU User Guide</title>
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="The user guide / prose documentation for QCGPU">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <base href="">

        <link rel="stylesheet" href="book.css">
        <link href="https://fonts.googleapis.com/css?family=Open+Sans:300italic,400italic,600italic,700italic,800italic,400,300,600,700,800" rel="stylesheet" type="text/css">
        <link href="https://fonts.googleapis.com/css?family=Source+Code+Pro:500" rel="stylesheet" type="text/css">

        <link rel="shortcut icon" href="favicon.png">

        <!-- Font Awesome -->
        <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/font-awesome/4.3.0/css/font-awesome.min.css">

        <link rel="stylesheet" href="highlight.css">
        <link rel="stylesheet" href="tomorrow-night.css">
        <link rel="stylesheet" href="ayu-highlight.css">

        <!-- Custom theme -->
        

        <!-- MathJax -->
        <script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
        

        <!-- Fetch Clipboard.js from CDN but have a local fallback -->
        <script src="https://cdn.jsdelivr.net/clipboard.js/1.6.1/clipboard.min.js"></script>
        <script>
            if (typeof Clipboard == 'undefined') {
                document.write(unescape("%3Cscript src='clipboard.min.js'%3E%3C/script%3E"));
            }
        </script>

        <noscript>
            <style type="text/css">
                .javascript-only {
                    display: none;
                }
            </style>
        </noscript>

    </head>
    <body class="light">
        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { } 
            if (theme === null || theme === undefined) { theme = 'light'; }
            document.body.className = theme;
            document.querySelector('html').className = theme;
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <ol class="chapter"><li><a href="qcgpu.html"><strong aria-hidden="true">1.</strong> QCGPU</a></li><li><ol class="section"><li><a href="getting-started.html"><strong aria-hidden="true">1.1.</strong> Getting Started</a></li></ol></li><li><a href="user-guide/user-guide.html"><strong aria-hidden="true">2.</strong> User Guide</a></li><li><ol class="section"><li><a href="user-guide/registers.html"><strong aria-hidden="true">2.1.</strong> Quantum Registers</a></li><li><a href="user-guide/gates.html"><strong aria-hidden="true">2.2.</strong> Quantum Gates</a></li><li><a href="user-guide/operations.html"><strong aria-hidden="true">2.3.</strong> Quantum Operations</a></li><li><a href="user-guide/examples.html"><strong aria-hidden="true">2.4.</strong> Examples</a></li><li><a href="user-guide/decoherence.html"><strong aria-hidden="true">2.5.</strong> Decoherence</a></li></ol></li><li><a href="algorithms/algorithms.html"><strong aria-hidden="true">3.</strong> Algorithms</a></li><li><ol class="section"><li><a href="algorithms/bernstein-vazirani.html"><strong aria-hidden="true">3.1.</strong> Bernstein-Vazirani</a></li><li><a href="algorithms/deutsch-jozsa.html"><strong aria-hidden="true">3.2.</strong> Deutsch-Jozsa</a></li><li><a href="algorithms/grover.html"><strong aria-hidden="true">3.3.</strong> Grovers</a></li><li><a href="algorithms/shor.html"><strong aria-hidden="true">3.4.</strong> Shors</a></li><li><a href="algorithms/super-dense.html"><strong aria-hidden="true">3.5.</strong> Super Dense Coding</a></li></ol></li></ol>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                
                <div id="menu-bar" class="menu-bar">
                    <div id="menu-bar-sticky-container">
                        <div class="left-buttons javascript-only">
                            <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                                <i class="fa fa-bars"></i>
                            </button>
                            <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                                <i class="fa fa-paint-brush"></i>
                            </button>
                            <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                                <li role="none"><button role="menuitem" class="theme" id="light">Light <span class="default">(default)</span></button></li>
                                <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                                <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                                <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                                <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                            </ul>
                            
                            <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                                <i class="fa fa-search"></i>
                            </button>
                            
                        </div>

                        <h1 class="menu-title">QCGPU User Guide</h1> 

                        <div class="right-buttons">
                            <a href="print.html" title="Print this book" aria-label="Print this book">
                                <i id="print-button" class="fa fa-print"></i>
                            </a>
                        </div>
                    </div>
                </div>

                
                <div id="searchbar-outer" class="searchbar-outer">
                    <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                </div>
                <div id="searchresults-outer" class="searchresults-outer">
                    <div class="searchresults-header" id="searchresults-header"></div>
                    <ul id="searchresults">
                    </ul>
                </div>
                

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <a class="header" href="print.html#qcgpu" id="qcgpu"><h1>QCGPU</h1></a>
<p><strong>QCGPU</strong> is a high performance, hardware accelerated quantum computer simulator written with <a href="https://rust-lang.org/">Rust</a> and <a href="https://www.khronos.org/opencl/">OpenCL</a>.</p>
<p>QCGPU is free and open source. The source code is available on <a href="https://github.com/qcgpu/qcgpu-rust">GitHub</a>. Please report any places where the documentation is unclear, or where examples could be added or improved by creating an <a href="https://github.com/qcgpu/qcgpu-rust/issues">issue</a>.</p>
<a class="header" href="print.html#help-wanted" id="help-wanted"><h2>Help Wanted</h2></a>
<p>Please request any functionality you would like, need or appreciate by creating an <a href="https://github.com/qcgpu/qcgpu-rust/issues">issue</a>. If you would like to add functionality or fix issues, please create a <a href="https://github.com/qcgpu/qcgpu-rust/pulls">pull request</a> and I will get back to you (usually within the day).</p>
<p>Any other feedback, suggestions or even tiny bits of criticism are welcome. When in doubt, file an <a href="https://github.com/qcgpu/qcgpu-rust/issues">issue</a>!</p>
<a class="header" href="print.html#api-docs" id="api-docs"><h2>API Docs</h2></a>
<p>Alongside this guide, you may also want the <a href="https://qcgpu.github.com/qcgpu/documentation">documentation</a>.</p>
<a class="header" href="print.html#license" id="license"><h2>License</h2></a>
<p>QCGPU is licensed under the <a href="https://github.com/qcgpu/qcgpu-rust/blob/master/LICENSE">MIT</a> License.</p>
<a class="header" href="print.html#getting-started" id="getting-started"><h1>Getting Started</h1></a>
<a class="header" href="print.html#installing-the-requirements" id="installing-the-requirements"><h2>Installing The Requirements</h2></a>
<p>To use QCGPU, you will need Rust and OpenCL installed.</p>
<p>The setup process for OpenCL will be different for every device. All apple devices (MacOS / OSX) will have OpenCL already installed.
For some hints on how to install on linux, look at the <a href="https://github.com/QCGPU/qcgpu-rust/blob/master/EC2-install.md">AWS EC2 Install Instructions</a>.
There is also a good chance that it is installed already. Check that <code>clinfo</code> for some other diagnostic command will run.</p>
<p>Rust is very easy to install. Check out <a href="https://www.rustup.rs">rustup</a>.</p>
<a class="header" href="print.html#adding-the-dependency" id="adding-the-dependency"><h2>Adding The Dependency</h2></a>
<p>To use the library with rust, you must add the following to your <code>cargo.toml</code> file:</p>
<pre><code class="language-toml">[dependencies]
qcgpu = &quot;0.1&quot;
</code></pre>
<p>You should now be able to use the library by adding</p>
<pre><code>extern crate qcgpu;
</code></pre>
<p>to <code>lib.rs</code> or <code>main.rs</code>, depending on if you are writing an executable or a library.</p>
<a class="header" href="print.html#user-guide" id="user-guide"><h1>User Guide</h1></a>
<p>This chapter covers the usage of the QCGPU library. It will also contain some information about the mathematics that each of the functions represents.</p>
<p>All aspects of the library are covered by this chapter, whereas complete examples (in the form of algorithm implementations) are available in the <a href="../algorithms/algorithms.html">Algorithms Chapter</a></p>
<a class="header" href="print.html#quantum-registers" id="quantum-registers"><h1>Quantum Registers</h1></a>
<p>All of the simulation is done through quantum registers. QCGPU provides a struct as a register, but that contains fields to do with the OpenCL buffers and related items, so the creation of registers should be done through the provided methods.</p>
<p>The library is optimized for complex superpositions, so the registers are all dense. This means that the number of qubits you can initialize is directly related to the capacity / available memory of the device.</p>
<p>The register struct is called <code>State</code> and is available through <code>qcgpu::State</code>.</p>
<p>To create a register, the easiest way to do it is with the <code>State::new</code> method.
It takes two parameters, the number of qubits and the device to use. The device is given as a usize, and corresponds to the OpenCL device which the register will be on.</p>
<p>The following example creates a register with 5 qubits on the 1st device.</p>
<pre><pre class="playpen"><code class="language-rust"># extern crate qcgpu;

use qcgpu::State;

# fn main() {
let mut register = State::new(5, 0);
# }
</code></pre></pre>
<p>Notice that the register is mutable. This allows the register to change. Also, the device is 0 indexed.</p>
<p>The implementation is equivilent to the description of a state vector \( \lvert \psi \rangle \) with</p>
<p>\[ \lvert \psi \rangle = \sum_{j = 0}^{2^n - 1} \alpha_j \lvert j \rangle \]</p>
<p>where \(n\) is the number of qubits, \(\alpha_j\) is the amplitude and the state is \(j\) runs over all \(2^n\) basis states.</p>
<p>There is one other way to initialize a state. Given a bitstring, a register can be initialized in that state using the <code>State::from_bit_string</code> method. For example, to initialize a register with the value <code>0100</code> the following is used:</p>
<pre><pre class="playpen"><code class="language-rust"># extern crate qcgpu;

use qcgpu::State;

# fn main() {
let mut register = State::from_bit_string(&quot;|0100&gt;&quot;, 0);
# }
</code></pre></pre>
<p>The second argument is the same as before. The register that is outputed from this method is equivilent to the state</p>
<p>\[ \lvert 0100 \rangle\]</p>
<a class="header" href="print.html#quantum-gates" id="quantum-gates"><h1>Quantum Gates</h1></a>
<p>Gates are used to manipulate quantum registers and to implement quantum algorithms.</p>
<a class="header" href="print.html#built-in-gates" id="built-in-gates"><h2>Built In Gates</h2></a>
<p>There are a number of gates built in to QCGPU. They can all be applied the same way:</p>
<pre><pre class="playpen"><code class="language-rust">
# #![allow(unused_variables)]
#fn main() {
use qcgpu::State;

let mut state = State::new(5, 0);

state.h(0); // Applies the hadamard (`h`) gate to the 0th qubit
#}</code></pre></pre>
<p><code>h</code> can be replaced with any of the following:</p>
<ul>
<li>The hadmard gate: <strong>h</strong> - <code>state.h(0);</code></li>
<li>The S gate: <strong>s</strong> - <code>state.s(0);</code></li>
<li>The T gate: <strong>t</strong> - <code>state.t(0);</code></li>
<li>The Pauli-X / NOT gate: <strong>x</strong> - <code>state.x(0);</code></li>
<li>The Pauli-Y gate: <strong>y</strong> - <code>state.y(0);</code></li>
<li>The Pauli-Z gate: <strong>z</strong> - <code>state.z(0);</code></li>
<li>The CNOT gate: <strong>cx</strong> - <code>state.cx(0, 1); // CNOT with control = 0, target = 1</code></li>
<li>The SWAP gate: <strong>swap</strong> - <code>state.swap(0,1); // Swaps the 0th and 1st qubit</code></li>
<li>The Toffoli gate: <strong>toffoli</strong> - <code>state.toffoli(0, 1, 2); // Toffoli with control1 = 0, control1 = 1, target = 2</code></li>
</ul>
<p>These are all shorthand methods for the application of arbitrary gates. For example, the application of a hadamard gate above is shorthand for</p>
<pre><pre class="playpen"><code class="language-rust">
# #![allow(unused_variables)]
#fn main() {
use qcgpu::gates::{h};
use qcgpu::State;

let mut state = State::new(5, 0);
state.apply_gate(h(), 0);
#}</code></pre></pre>
<p>You can also use any of the gates as controlled gates. For example, the application of the CNOT gate above is shorthand for</p>
<pre><pre class="playpen"><code class="language-rust">
# #![allow(unused_variables)]
#fn main() {
use qcgpu::gates::{x};
use qcgpu::State;

let mut state = State::new(5, 0);
state.apply_controlled_gate(x(), 0, 1);
#}</code></pre></pre>
<a class="header" href="print.html#user-defined-gates" id="user-defined-gates"><h2>User Defined Gates</h2></a>
<p>Gates in QCGPU are represented by the <code>Gate</code> struct, available through <code>qcgpu::Gate</code>.</p>
<p>It is defined as follows:</p>
<pre><pre class="playpen"><code class="language-rust">
# #![allow(unused_variables)]
#fn main() {
extern crate num_complex;
use num_complex::Complex32;

struct Gate {
    a: Complex32,
    b: Complex32,
    c: Complex32,
    d: Complex32,
}
#}</code></pre></pre>
<p>To create your own gate, you will need to add the <code>num_complex</code> crate to your dependencies.</p>
<p>A gate is created as follows:</p>
<pre><pre class="playpen"><code class="language-rust">
# #![allow(unused_variables)]
#fn main() {
let x = Gate {
    Gate {
        a: Complex32::new(0.0, 0.0),
        b: Complex32::new(1.0, 0.0),
        c: Complex32::new(1.0, 0.0),
        d: Complex32::new(0.0, 0.0),
    }
}
#}</code></pre></pre>
<p>This corresponds to the matrix</p>
<p>\[x = \begin{bmatrix} 0 &amp; 1 \\ 1 &amp; 0 \end{bmatrix}\]</p>
<p>This can be applied using the same long hand method as above:</p>
<pre><pre class="playpen"><code class="language-rust">
# #![allow(unused_variables)]
#fn main() {
let mut state = State::new(1, 0);
state.apply_gate(x, 0);
#}</code></pre></pre>
<a class="header" href="print.html#quantum-operations" id="quantum-operations"><h1>Quantum Operations</h1></a>
<p>There are a number of operations you can preform on quantum registers with QCGPU.</p>
<a class="header" href="print.html#measurement" id="measurement"><h2>Measurement</h2></a>
<p>You can measure the register in two ways. You can either do a single measurement and return an integer with the measured value or you can measure multiple times and return a <code>HashMap&lt;String, i32&gt;</code>, with the key being the bitstring, and the value being the number of times it was measured.</p>
<p>The measurements don't collapse the state.</p>
<p>They are used as follows:</p>
<pre><pre class="playpen"><code class="language-rust">
# #![allow(unused_variables)]
#fn main() {
use qcgpu::State;

let mut state = State::new(5, 0);
state.measure(); // Returns an integer
state.measure_many(1000); // Measures 1000 times, returns a HashMap&lt;String, i32&gt;
#}</code></pre></pre>
<p>There is also a convenience method to measure the first \(n\) qubits in the register. Again, the state is not collapsed</p>
<pre><pre class="playpen"><code class="language-rust">
# #![allow(unused_variables)]
#fn main() {
use qcgpu::State;

let mut state = State::new(5, 0);
state.measure_first(3, 1000); // Measures the first 3 qubits 1000 times, returns a HashMap&lt;String, i32&gt;
#}</code></pre></pre>
<a class="header" href="print.html#probability" id="probability"><h2>Probability</h2></a>
<p>QCGPU provides another method for getting the probability of each outcome.</p>
<p>The probability is calculated for a state \(\lvert \psi \rangle = \sum_{j = 0}^{2^n - 1} \alpha_j \lvert j \rangle\),</p>
<p>\[P(j) = |\alpha_j|^2\]</p>
<p>The method <code>get_probabilities</code> returns a <code>Vec&lt;f32&gt;</code> with each of the values corresponding to \(|\alpha_j|^2\) for each index \(j\).</p>
<pre><pre class="playpen"><code class="language-rust">
# #![allow(unused_variables)]
#fn main() {
use qcgpu::State;

let mut state = State::new(1, 0);
state.h(0);
state.get_probabilities(); // [0.5, 0.5]
#}</code></pre></pre>
<a class="header" href="print.html#examples" id="examples"><h1>Examples</h1></a>
<p>Here is a complete example of using QCGPU to simulate the bell state.</p>
<pre><pre class="playpen"><code class="language-rust">extern crate qcgpu;

use qcgpu::State;

fn main() {
    // Create a new quantum register with 2 qubits on OpenCL device #0
    let mut register = State::new(2, 0);

    // Apply a hadamard gate to the first qubit
    register.h(0);

    // Apply a CNOT, with the control = 0, and target = 1
    register.cx(0, 1);

    // Measure the register 1000 times and print the output
    println!(&quot;Measured: {:?}&quot;, register.measure_many(1000));
}
</code></pre></pre>
<p>The output should be something like</p>
<pre><code class="language-shell">Measured: {&quot;00&quot;: 516, &quot;11&quot;: 484}
</code></pre>
<p>For more, non trivial examples, see the <a href="../algorithms/algorithms.html">Algorithms</a></p>
<a class="header" href="print.html#decoherence" id="decoherence"><h1>Decoherence</h1></a>
<p>QCGPU provides a way to easily simulate the effects of decoherence on the quantum computer. The effects are simulated by a random gate, corresponding to a random rotation around the \(z\) axis of the bloch sphere.</p>
<p>The angle of the rotation is a normal distrobuted value, with the varience as the strength factor <code>d</code>.</p>
<p>To avoid performance costs when not being used, decoherence can be enabled via a feature.</p>
<p>Change the dependency in <code>cargo.toml</code> to</p>
<pre><code class="language-toml">[dependencies]
qcgpu = { version = &quot;0.1&quot;, features = [&quot;decoherence&quot;] }
</code></pre>
<p>Now you can add decoherence to your simulator.</p>
<p>To set the amount of decoherence, the <code>set_decoherence</code> method is used. Its arguments are the strength of the decoherence.
This will affect all following gate applications.</p>
<pre><pre class="playpen"><code class="language-rust">
# #![allow(unused_variables)]
#fn main() {
use qcgpu::State;

let mut register = State::new(5, 0);
register.set_decoherence(0.4);
#}</code></pre></pre>
<p>You can also manually decohere the register based on the previously set strength value. This method is automatically called by all gate applications.</p>
<pre><pre class="playpen"><code class="language-rust">
# #![allow(unused_variables)]
#fn main() {
register.decohere();
#}</code></pre></pre>
<a class="header" href="print.html#algorithms" id="algorithms"><h1>Algorithms</h1></a>
<p>The following chapter details some implementations of non trivial quantum algorithms. They are based on the source code from <a href="http://www.libquantum.de/">libquantum</a> along with the lecture notes from <a href="https://cs.uwaterloo.ca/%7Ewatrous/LectureNotes.html">the University of Waterloo</a>.</p>
<p>Note that some implementations may not yet be complete.</p>
<a class="header" href="print.html#bernstein-vazirani-algorithm" id="bernstein-vazirani-algorithm"><h1>Bernstein-Vazirani Algorithm</h1></a>
<p>This algorithm finds a hidden integer \(a \in { 0, 1}^n\)from
an oracle \(f_a\)which returns a bit \(a \cdot x \equiv \sum_i a_i x_i \mod 2\)
for an input \(x \in {0,1}^n\).</p>
<p>A classical oracle returns \(f_a(x) = a \dot x \mod 2\), while the quantum oracle
must be queried with superpositions of input \(x\)'s.</p>
<p>To solve this problem classically, the hidden integer can be found by checking the
oracle with the inputs \(x = 1,2,\dots,2^i,2^{n-1}\), where each
query reveals the \(i\)th bit of \(a\) (\(a_i\)).
This is the optimal classical solution, and is O(n). Using a quantum oracle and the
Bernstein-Vazirani algorithm, \(a\) can be found with just one query to the oracle.</p>
<a class="header" href="print.html#the-algorithm" id="the-algorithm"><h2>The Algorithm</h2></a>
<ol>
<li>Initialize \(n\) qubits in the state \(\lvert 0, \dots, 0\rangle\).</li>
<li>Apply the Hadamard gate \(H\) to each qubit.</li>
<li>Apply the inner product oracle.</li>
<li>Apply the Hadamard gate \(H\) to each qubit.</li>
<li>Measure the register</li>
</ol>
<p>From this procedure, we find that the registers measured value is equal to that of
the original hidden integer.</p>
<pre><pre class="playpen"><code class="language-rust">extern crate qcgpu;

use qcgpu::State;
use qcgpu::gates::h;

fn main() {
    let num_qubits = 16; // Number of qubits to use
    let a = 101; // Hidden integer, bitstring is 1100101

    // You should also make sure that a is representable with n qubits,
    // by settings a as a mod 2^n.

    // Bernstein-Vazirani algorithm
    let mut state = State::new(num_qubits, 1); // New quantum register, using the GPU.

    // Apply a hadamard gate to each qubit
    state.apply_all(h());

    // Apply the inner products oracle
    for i in 0..num_qubits {
        if a &amp; (1 &lt;&lt; i) != 0 {
            state.z(i as i32);
        }
        // Otherwise should apply identity gate, but computationally this doens't change the state.
    }

    // Apply hadamard gates before measuring
    state.apply_all(h());

    println!(&quot;Measurement Results: {:?}&quot;, state.measure_many(1000));
    // Measurement Results: {&quot;0000000001100101&quot;: 1000}
}
</code></pre></pre>
<a class="header" href="print.html#deutsch-jozsa-algorithm" id="deutsch-jozsa-algorithm"><h1>Deutsch-Jozsa Algorithm</h1></a>
<p>This algorithm was the first to show that quantum computers could have a speedup over classical computers.</p>
<p>Consider a function \(f(x)\) which takes an input of an \(n\)-bit string \(x\) and returns 0 or 1.</p>
<p>Suppose that \(f(x)\) is either a <strong>constant</strong> function that has the same value \(c \in {0, 1},  \forall x\), or a <strong>balanced</strong> function, where the value is 0 for half of the inputs, and 1 for the other half.</p>
<p>The Deutsch-Jozsa problem is to find whether \(f\) is <em>constant</em> or <em>balanced</em>, in as few function evaluations as possible.</p>
<p>Using classical computing, in the worst case, this requires \(2^{n-1}+1\) function evaluations.
Using quantum computing, this can be done with just one function evaluation.</p>
<p>The function \(f\), to be used in a quantum computer, must be specified by an oracle circuit \(U_{f}\) such that \(U_{f} \lvert x \rangle = (-1)^{f(x)}\lvert x \rangle\).</p>
<a class="header" href="print.html#the-algorithm-1" id="the-algorithm-1"><h2>The Algorithm</h2></a>
<ol>
<li>Initialize \(n\) qubits in the state \(\lvert 0, \dots, 0\rangle\).</li>
<li>Apply the Hadamard gate \(H\) to each qubit.</li>
<li>Apply the oracle circuit \(U_f\).</li>
<li>Apply the Hadamard gate \(H\) to each qubit.</li>
<li>Measure each qubit. Let \(y = (y_{1}, \dots, y_{n})\) be the list of measurement outcomes.</li>
</ol>
<p>From this procedure, we find that \(f\) is constant if \(y\) is the all zero string.</p>
<pre><pre class="playpen"><code class="language-rust">extern crate qcgpu;

use qcgpu::State;
use qcgpu::gates::h;

fn main() {
    // 3 qubits, f(x) = x_0 NOT x_1 x_2
    // Balanced
    let mut balanced_state = State::new(3, 1);

    balanced_state.apply_all(h());

    // Oracle U_f
    balanced_state.h(2);
    balanced_state.z(0);
    balanced_state.cx(1, 2);
    balanced_state.h(2);

    balanced_state.apply_all(h());

    println!(
        &quot;{}&quot;,
        if balanced_state.measure() == 0 {
            &quot;constant&quot;
        } else {
            &quot;balanced&quot;
        }
    );

    // 3 qubits, f(x) = 0
    // Constant
    let mut constant_state = State::new(3, 1);

    constant_state.apply_all(h());

    // Oracle is equivilant to the identity gate, thus has no effect on the
    // state.

    constant_state.apply_all(h());

    println!(
        &quot;{}&quot;,
        if constant_state.measure() == 0 {
            &quot;constant&quot;
        } else {
            &quot;balanced&quot;
        }
    );
}
</code></pre></pre>
<a class="header" href="print.html#grovers-algorithm" id="grovers-algorithm"><h1>Grovers Algorithm</h1></a>
<p>Given an unstructured set \(N = {a_1, a_2,\dots,a_n}\), find
a given element \(a_i \in N\).</p>
<p>This implementation looks for a given number \(target\) in the set \({0,1,\dots, \text{regwidth}}\).</p>
<p>See <a href="https://cs.uwaterloo.ca/%7Ewatrous/LectureNotes.html">https://cs.uwaterloo.ca/~watrous/LectureNotes.html</a></p>
<pre><pre class="playpen"><code class="language-rust">extern crate qcgpu;
extern crate rand;

use qcgpu::State;
use std::f32::consts::PI;

fn main() {
    let mut state = State::new(8, 1);

    let target = 5;
    let reg_width = 3;

    let num_inversions = ((PI / 4.0) * ((1 &lt;&lt; reg_width) as f32).sqrt()) as i32;

    state.x(reg_width);

    for i in 0..(reg_width + 1) {
        state.h(i);
    }

    for _ in 0..(num_inversions) {
        iteration(&amp;mut state, target, reg_width);
    }

    state.h(reg_width);

    println!(&quot;Measured: {:?}&quot;, state.measure_first(reg_width, 1000));
}

fn oracle(state: &amp;mut State, target: i32, reg_width: i32) {
    for i in 0..reg_width {
        if get_bit(target, i) == 0 {
            state.x(i);
        }
    }

    state.toffoli(0, 1, reg_width + 1);

    let mut i = 1;
    while i &lt; reg_width {
        state.toffoli(i, reg_width + i, reg_width + i + 1);
        i += 1;
    }

    state.cx(reg_width + i, reg_width);

    i = reg_width - 1;
    while i &gt; 0 {
        state.toffoli(i, reg_width + i, reg_width + i + 1);
        i -= 1;
    }

    state.toffoli(0, 1, reg_width + 1);

    for i in 0..reg_width {
        if get_bit(target, i) == 0 {
            state.x(i);
        }
    }
}

fn inversion(state: &amp;mut State, reg_width: i32) {
    for i in 0..reg_width {
        state.x(i);
    }

    state.h(reg_width - 1);

    if reg_width == 3 {
        state.toffoli(0, 1, 2);
    } else {
        state.toffoli(0, 1, reg_width + 1);

        let mut i = 1;
        while i &lt; reg_width {
            state.toffoli(i, reg_width + i, reg_width + i + 1);
            i += 1;
        }

        state.cx(reg_width + i, reg_width - 1);

        i = reg_width - 2;
        while i &gt; 0 {
            state.toffoli(i, reg_width + i, reg_width + i + 1);
            i -= 1;
        }

        state.toffoli(0, 1, reg_width + 1);
    }

    state.h(reg_width - 1);

    for i in 0..reg_width {
        state.x(i);
    }
}

fn iteration(state: &amp;mut State, target: i32, reg_width: i32) {
    oracle(state, target, reg_width);

    for i in 0..reg_width {
        state.h(i);
    }

    inversion(state, reg_width);

    for i in 0..reg_width {
        state.h(i);
    }
}

/// Get the value of a bit
fn get_bit(number: i32, n: i32) -&gt; i32 {
    if number &amp; (1 &lt;&lt; n) != 0 {
        return 1;
    }
    0
}
</code></pre></pre>
<a class="header" href="print.html#shors-algorithm" id="shors-algorithm"><h1>Shors Algorithm</h1></a>
<p>This algorithm finds the prime factors (\)u\) and \(v\)) of an odd, composite integer \(n\),
that is not a prime power.</p>
<a class="header" href="print.html#the-algorithm-2" id="the-algorithm-2"><h2>The Algorithm</h2></a>
<p>(pseudo code)</p>
<pre><code class="language-pseudo">Repeat
    Randomly choose \\(a \in \{ 2, \dots, n - 1 \}\\)
    Compute \\(d = gcd(a, n)\\)
    If \\(d \geq 2\\) then
        Return \\(u = d\\) and \\(v = n/d\\)
    Else // We know \\(a \in \mathbb{Z}^*_N\\)
        Let \\(r\\) be the order of \\(a\\) in \\(\mathbb{Z}^*_N\\) // Order finding algorithm
        If \\(r\\) is even then
            Compute \\(x = a^{r/2} - 1 (\mod n)\\)
            Compute \\(d = \gcd(x, n)\\)
            If \\(d \geq 2\\) then
                Return \\(u = d\\) and \\(v = n/d\\)
Until a value is returned.
</code></pre>
<p>See <a href="https://cs.uwaterloo.ca/%7Ewatrous/LectureNotes.html">https://cs.uwaterloo.ca/~watrous/LectureNotes.html</a></p>
<pre><pre class="playpen"><code class="language-rust">extern crate qcgpu;
extern crate rand;

use rand::{thread_rng, Rng};
use qcgpu::{gcd, State};
use qcgpu::gates::h;


fn main() {
    let n = 15; // Number to factor
    println!(&quot;Factoring {}.&quot;, n);

    // Here we should check if the number is even, or if it is a power factor

    let mut rng = thread_rng();
    loop {
        let mut a = rng.gen_range(2, n); // Randomly choose \\(a \in \{ 2, \dots, n - 1 \}\\)

        let mut d = gcd(a, n);
        if d &gt;= 2 {
            // Found the factors; No Quantum needed
            println!(
                &quot;Factors are {} and {} (No quantum algorithm used)&quot;,
                d,
                n / d
            );
            break;
        } else {
            // We know \\(a \in \mathbb{Z}^*_N\\)
            let r = find_order(a, n);
            if r % 2 == 0 {
                let x = (a.pow((r as f32 / 2 as f32) as u32) - 1) % n;
                d = gcd(x, n);
                if d &gt;= 2 {
                    println!(&quot;Factors are {} and {}&quot;, d, n / d);
                    break;
                }
            } else {
                println!(&quot;Period is odd&quot;);
            }
        }
    }
}
</code></pre></pre>
<a class="header" href="print.html#order-finding" id="order-finding"><h2>Order Finding</h2></a>
<p>Given a positive integer \(n \geq 2\) and an element \(a \in \mathbb{Z}_n^* \),
Find the order of \(a\) in \(\mathbb{Z}_n^*\).</p>
<p>Order finding is the only quantum part in shors algorithm.</p>
<p>\(\mathbb{Z}_n\) is the set of integers from \({0,\dots, n - 1}\) or \(\mathbb{z} \mod n\).
The set \(\mathbb{Z}_n^* = {a \in \mathbb{Z}_n : \gcd(a,n) = 1}\)</p>
<p>The set \( \mathbb{Z}_n^* \) forms a group wth the multiplication modulo \(n\) operation.
Thus, for \( a \in \mathbb{Z}_n^* \) , \(\exists b \in \mathbb{Z}_n^*\) that uniquely satisfies</p>
<p>\[
ab \equiv 1 \mod n
\]</p>
<p>The order of a given element \(a \in \mathbb{Z}_n^*\) is the smallest positive integer \(r\) such that</p>
<p>\[
a^r \equiv 1 \mod n
\]</p>
<pre><pre class="playpen"><code class="language-rust">
# #![allow(unused_variables)]
#fn main() {
fn find_order(a: i32, n: i32) -&gt; i32 {
    unimplemented!()
}
#}</code></pre></pre>
<a class="header" href="print.html#super-dense-coding" id="super-dense-coding"><h1>Super Dense Coding</h1></a>
<p>if Alice and Bob share a pair of entangled qubits, then Alice can encode two classical bits into her one entangled qubit,
send it to Bob, and Bob can decode it with the help of his entangled qubit.</p>
<pre><pre class="playpen"><code class="language-rust">extern crate qcgpu;

use qcgpu::State;

fn superdense(input: &amp;str) -&gt; i32 {
    let mut state = State::new(2, 0);
    let input_str = String::from(input);

    // Prepare the bell state
    state.h(0);
    state.cx(0, 1);

    // Alice prepares her qubit
    let alice = 1;
    if input_str.get(0..1) == Some(&quot;1&quot;) {
        state.z(alice);
    }
    if input_str.get(1..2) == Some(&quot;1&quot;) {
        state.x(alice);
    }

    println!(&quot;\nState after Alice prepares her qubit: \n{}&quot;, state);

    // Alice sends her qubit to Bob
    let bob = 0;
    state.cx(alice, bob);
    state.h(alice);

    println!(
        &quot;\nState after Bob receives Alice's qubit and 'decodes' it: \n{}&quot;,
        state
    );

    state.measure()
}

fn main() {
    use std::io;

    println!(&quot;Two bit string to send:&quot;);
    let mut input = String::new();
    match io::stdin().read_line(&amp;mut input) {
        Ok(_n) =&gt; {
            let result = superdense(input.as_str());
            println!(&quot;\nDecoded string is: {}&quot;, result);
        }
        Err(error) =&gt; println!(&quot;error: {}&quot;, error),
    }
}
</code></pre></pre>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                        

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                

            </nav>

        </div>


        <!-- Local fallback for Font Awesome -->
        <script>
            if (getComputedStyle(document.querySelector(".fa")).fontFamily !== "FontAwesome") {
                var link = document.createElement('link');
                link.rel = 'stylesheet';
                link.type = 'text/css';
                link.href = '_FontAwesome/css/font-awesome.css';
                document.head.insertBefore(link, document.head.firstChild)
            }
        </script>

        
        <script src="searchindex.js" type="text/javascript" charset="utf-8"></script>
        
        
        <script src="elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="searcher.js" type="text/javascript" charset="utf-8"></script>
        

        <script>
            document.addEventListener('DOMContentLoaded', function() {
                window.print();
            })
        </script>
        

        <script src="highlight.js"></script>
        <script src="book.js"></script>

        <!-- Custom JS script -->
        

    </body>
</html>