<?xml version="1.0" encoding="utf-8" standalone="yes"?>
<rss version="2.0" xmlns:atom="http://www.w3.org/2005/Atom">
  <channel>
    <title>Quantum Compilation as a Graph Transformation Problem on Scaling QC with Graph Rewriting</title>
    <link>http://localhost:1313/03_compiler/</link>
    <description>Recent content in Quantum Compilation as a Graph Transformation Problem on Scaling QC with Graph Rewriting</description>
    <generator>Hugo</generator>
    <language>en-gb</language>
    <atom:link href="http://localhost:1313/03_compiler/index.xml" rel="self" type="application/rss+xml" />
    <item>
      <title>Related work</title>
      <link>http://localhost:1313/03_compiler/secgts-sota/</link>
      <pubDate>Mon, 01 Jan 0001 00:00:00 +0000</pubDate>
      <guid>http://localhost:1313/03_compiler/secgts-sota/</guid>
      <description>&lt;p&gt;&lt;strong&gt;Graph rewriting on computation graphs.&lt;/strong&gt;  Optimisation of computation&#xA;graphs is a long-standing problem in computer science that is seeing renewed&#xA;interest in the compiler &lt;span class=&#34;citation&#34;&gt;&lt;span data-bibtex-key=&#34;Lattner_2021&#34; class=&#34;citation-key&#34;&gt;Lattner, 2021&lt;/span&gt;&lt;span class=&#34;citation-full&#34;&gt;&lt;span class=&#34;authors&#34;&gt;Chris  &lt;span class=&#34;last-name&#34;&gt;Lattner&lt;/span&gt;, Mehdi  &lt;span class=&#34;last-name&#34;&gt;Amini&lt;/span&gt;, Uday  &lt;span class=&#34;last-name&#34;&gt;Bondhugula&lt;/span&gt;, Albert  &lt;span class=&#34;last-name&#34;&gt;Cohen&lt;/span&gt;, Andy  &lt;span class=&#34;last-name&#34;&gt;Davis&lt;/span&gt;, Jacques  &lt;span class=&#34;last-name&#34;&gt;Pienaar&lt;/span&gt;, River  &lt;span class=&#34;last-name&#34;&gt;Riddle&lt;/span&gt;, Tatiana  &lt;span class=&#34;last-name&#34;&gt;Shpeisman&lt;/span&gt;, Nicolas  &lt;span class=&#34;last-name&#34;&gt;Vasilache&lt;/span&gt; and Oleksandr  &lt;span class=&#34;last-name&#34;&gt;Zinenko&lt;/span&gt;&lt;/span&gt;. 2021. MLIR: Scaling Compiler Infrastructure for Domain Specific Computation. In &lt;em&gt;2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)&lt;/em&gt;, February 2021. IEEE, 2--14. &lt;span class=&#34;doi&#34;&gt;doi: &lt;a href=&#34;https://doi.org/10.1109/CGO51591.2021.9370308&#34;&gt;10.1109/CGO51591.2021.9370308&lt;/a&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;, machine learning (ML) &lt;span class=&#34;citation&#34;&gt;&lt;span data-bibtex-key=&#34;Jia2019&#34; class=&#34;citation-key&#34;&gt;Jia, 2019&lt;/span&gt;&lt;span class=&#34;citation-full&#34;&gt;&lt;span class=&#34;authors&#34;&gt;Zhihao  &lt;span class=&#34;last-name&#34;&gt;Jia&lt;/span&gt;, Oded  &lt;span class=&#34;last-name&#34;&gt;Padon&lt;/span&gt;, James  &lt;span class=&#34;last-name&#34;&gt;Thomas&lt;/span&gt;, Todd  &lt;span class=&#34;last-name&#34;&gt;Warszawski&lt;/span&gt;, Matei  &lt;span class=&#34;last-name&#34;&gt;Zaharia&lt;/span&gt; and Alex  &lt;span class=&#34;last-name&#34;&gt;Aiken&lt;/span&gt;&lt;/span&gt;. 2019. TASO: optimizing deep learning computation with automatic generation of graph substitutions. In &lt;em&gt;Proceedings of the 27th ACM Symposium on Operating Systems Principles&lt;/em&gt;, October 2019. ACM, 47--62. &lt;span class=&#34;doi&#34;&gt;doi: &lt;a href=&#34;https://doi.org/10.1145/3341301.3359630&#34;&gt;10.1145/3341301.3359630&lt;/a&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt; &lt;span class=&#34;citation&#34;&gt;&lt;span data-bibtex-key=&#34;Fang2020&#34; class=&#34;citation-key&#34;&gt;Fang, 2020&lt;/span&gt;&lt;span class=&#34;citation-full&#34;&gt;&lt;span class=&#34;authors&#34;&gt;Jingzhi  &lt;span class=&#34;last-name&#34;&gt;Fang&lt;/span&gt;, Yanyan  &lt;span class=&#34;last-name&#34;&gt;Shen&lt;/span&gt;, Yue  &lt;span class=&#34;last-name&#34;&gt;Wang&lt;/span&gt; and Lei  &lt;span class=&#34;last-name&#34;&gt;Chen&lt;/span&gt;&lt;/span&gt;. 2020. Optimizing DNN computation graph using graph substitutions. &lt;em&gt;Proceedings of the VLDB Endowment&lt;/em&gt; 13, 12 (August 2020, 2734--2746). &lt;span class=&#34;doi&#34;&gt;doi: &lt;a href=&#34;https://doi.org/10.14778/3407790.3407857&#34;&gt;10.14778/3407790.3407857&lt;/a&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;&#xA;and quantum computing communities &lt;span class=&#34;citation&#34;&gt;&lt;span data-bibtex-key=&#34;Xu2022&#34; class=&#34;citation-key&#34;&gt;Xu, 2022&lt;/span&gt;&lt;span class=&#34;citation-full&#34;&gt;&lt;span class=&#34;authors&#34;&gt;Mingkuan  &lt;span class=&#34;last-name&#34;&gt;Xu&lt;/span&gt;, Zikun  &lt;span class=&#34;last-name&#34;&gt;Li&lt;/span&gt;, Oded  &lt;span class=&#34;last-name&#34;&gt;Padon&lt;/span&gt;, Sina  &lt;span class=&#34;last-name&#34;&gt;Lin&lt;/span&gt;, Jessica  &lt;span class=&#34;last-name&#34;&gt;Pointing&lt;/span&gt;, Auguste  &lt;span class=&#34;last-name&#34;&gt;Hirth&lt;/span&gt;, Henry  &lt;span class=&#34;last-name&#34;&gt;Ma&lt;/span&gt;, Jens  &lt;span class=&#34;last-name&#34;&gt;Palsberg&lt;/span&gt;, Alex  &lt;span class=&#34;last-name&#34;&gt;Aiken&lt;/span&gt;, Umut A.  &lt;span class=&#34;last-name&#34;&gt;Acar&lt;/span&gt; and Zhihao  &lt;span class=&#34;last-name&#34;&gt;Jia&lt;/span&gt;&lt;/span&gt;. 2022. Quartz: Superoptimization of Quantum Circuits. In &lt;em&gt;Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation&lt;/em&gt;, June 2022. Association for Computing Machinery, 625--640. &lt;span class=&#34;doi&#34;&gt;doi: &lt;a href=&#34;https://doi.org/10.1145/3519939.3523433&#34;&gt;10.1145/3519939.3523433&lt;/a&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt; &lt;span class=&#34;citation&#34;&gt;&lt;span data-bibtex-key=&#34;Xu2023&#34; class=&#34;citation-key&#34;&gt;Xu, 2023&lt;/span&gt;&lt;span class=&#34;citation-full&#34;&gt;&lt;span class=&#34;authors&#34;&gt;Amanda  &lt;span class=&#34;last-name&#34;&gt;Xu&lt;/span&gt;, Abtin  &lt;span class=&#34;last-name&#34;&gt;Molavi&lt;/span&gt;, Lauren  &lt;span class=&#34;last-name&#34;&gt;Pick&lt;/span&gt;, Swamit  &lt;span class=&#34;last-name&#34;&gt;Tannu&lt;/span&gt; and Aws  &lt;span class=&#34;last-name&#34;&gt;Albarghouthi&lt;/span&gt;&lt;/span&gt;. 2023. Synthesizing Quantum-Circuit Optimizers. &lt;em&gt;Proceedings of the ACM on Programming Languages&lt;/em&gt; 7, PLDI (June 2023, 835--859). &lt;span class=&#34;doi&#34;&gt;doi: &lt;a href=&#34;https://doi.org/10.1145/3591254&#34;&gt;10.1145/3591254&lt;/a&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;. In all these domains, graphs&#xA;encode computations that are either expensive to execute or evaluated repeatedly&#xA;over many iterations, making the optimisation of the execution cost of the&#xA;computation a primary concern.&lt;/p&gt;</description>
    </item>
    <item>
      <title>Computation graphs and linearity</title>
      <link>http://localhost:1313/03_compiler/sec-compgraphs/</link>
      <pubDate>Mon, 01 Jan 0001 00:00:00 +0000</pubDate>
      <guid>http://localhost:1313/03_compiler/sec-compgraphs/</guid>
      <description>&lt;p&gt;Computation graphs represent the flow of data between operations in a program,&#xA;with nodes as operations and edges as data dependencies. Widely used in machine&#xA;learning frameworks and GPU optimisations &lt;span class=&#34;citation&#34;&gt;&lt;span data-bibtex-key=&#34;Bergstra2011&#34; class=&#34;citation-key&#34;&gt;Bergst., 2011&lt;/span&gt;&lt;span class=&#34;citation-full&#34;&gt;&lt;span class=&#34;authors&#34;&gt;James  &lt;span class=&#34;last-name&#34;&gt;Bergstra&lt;/span&gt;, Frédéric  &lt;span class=&#34;last-name&#34;&gt;Bastien&lt;/span&gt;, Olivier  &lt;span class=&#34;last-name&#34;&gt;Breuleux&lt;/span&gt;, Pascal  &lt;span class=&#34;last-name&#34;&gt;Lamblin&lt;/span&gt;, Razvan  &lt;span class=&#34;last-name&#34;&gt;Pascanu&lt;/span&gt;, Olivier  &lt;span class=&#34;last-name&#34;&gt;Delalleau&lt;/span&gt;, Guillaume  &lt;span class=&#34;last-name&#34;&gt;Desjardins&lt;/span&gt;, David  &lt;span class=&#34;last-name&#34;&gt;Warde-Farley&lt;/span&gt;, Ian  &lt;span class=&#34;last-name&#34;&gt;Goodfellow&lt;/span&gt;, Arnaud  &lt;span class=&#34;last-name&#34;&gt;Bergeron&lt;/span&gt; and   &lt;span class=&#34;last-name&#34;&gt;others&lt;/span&gt;&lt;/span&gt;. 2011. Theano: Deep learning on gpus with python. In &lt;em&gt;NIPS 2011, BigLearning Workshop, Granada, Spain&lt;/em&gt;&lt;/span&gt;&lt;/span&gt; &lt;span class=&#34;citation&#34;&gt;&lt;span data-bibtex-key=&#34;Zhao2023&#34; class=&#34;citation-key&#34;&gt;Zhao, 2023&lt;/span&gt;&lt;span class=&#34;citation-full&#34;&gt;&lt;span class=&#34;authors&#34;&gt;Yuxuan  &lt;span class=&#34;last-name&#34;&gt;Zhao&lt;/span&gt;, Qi  &lt;span class=&#34;last-name&#34;&gt;Sun&lt;/span&gt;, Zhuolun  &lt;span class=&#34;last-name&#34;&gt;He&lt;/span&gt;, Yang  &lt;span class=&#34;last-name&#34;&gt;Bai&lt;/span&gt; and Bei  &lt;span class=&#34;last-name&#34;&gt;Yu&lt;/span&gt;&lt;/span&gt;. 2023. AutoGraph: Optimizing DNN Computation Graph for Parallel GPU Kernel Execution. &lt;em&gt;Proceedings of the AAAI Conference on Artificial Intelligence&lt;/em&gt; 37, 9 (June 2023, 11354--11362). &lt;span class=&#34;doi&#34;&gt;doi: &lt;a href=&#34;https://doi.org/10.1609/aaai.v37i9.26343&#34;&gt;10.1609/aaai.v37i9.26343&lt;/a&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;, they are&#xA;conceptually equivalent to dataflow graphs used in compiler design, which were&#xA;pioneered by &lt;span class=&#34;citation&#34;&gt;&lt;span data-bibtex-key=&#34;Feo1990&#34; class=&#34;citation-key&#34;&gt;Feo, 1990&lt;/span&gt;&lt;span class=&#34;citation-full&#34;&gt;&lt;span class=&#34;authors&#34;&gt;John T.  &lt;span class=&#34;last-name&#34;&gt;Feo&lt;/span&gt;, David C.  &lt;span class=&#34;last-name&#34;&gt;Cann&lt;/span&gt; and Rodney R.  &lt;span class=&#34;last-name&#34;&gt;Oldehoeft&lt;/span&gt;&lt;/span&gt;. 1990. A report on the sisal language project. &lt;em&gt;Journal of Parallel and Distributed Computing&lt;/em&gt; 10, 4 (December 1990, 349--366). &lt;span class=&#34;doi&#34;&gt;doi: &lt;a href=&#34;https://doi.org/10.1016/0743-7315(90)90035-n&#34;&gt;10.1016/0743-7315(90)90035-n&lt;/a&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt; and &lt;span class=&#34;citation&#34;&gt;&lt;span data-bibtex-key=&#34;Kahn1976&#34; class=&#34;citation-key&#34;&gt;Kahn, 1976&lt;/span&gt;&lt;span class=&#34;citation-full&#34;&gt;&lt;span class=&#34;authors&#34;&gt;Gilles  &lt;span class=&#34;last-name&#34;&gt;Kahn&lt;/span&gt; and David  &lt;span class=&#34;last-name&#34;&gt;MacQueen&lt;/span&gt;&lt;/span&gt;. 1976. Coroutines and networks of parallel processes. PhD Thesis. IRIA&lt;/span&gt;&lt;/span&gt; and are now central to most compiler IRs.&lt;/p&gt;</description>
    </item>
    <item>
      <title>A graph representation for quantum programs</title>
      <link>http://localhost:1313/03_compiler/secgraph-defs/</link>
      <pubDate>Mon, 01 Jan 0001 00:00:00 +0000</pubDate>
      <guid>http://localhost:1313/03_compiler/secgraph-defs/</guid>
      <description>&lt;p&gt;For the purposes of this thesis, we introduce a simplified graph-based IR for&#xA;quantum computations that we will call minIR. It captures all the expressiveness&#xA;that we require for hybrid programs whilst remaining sufficiently abstract to be&#xA;applicable to a variety of IRs and, by extension, quantum programming languages&#xA;and compiler frameworks.&lt;/p&gt;&#xA;&lt;p&gt;MinIR can be thought of as being built from statements of the form&lt;/p&gt;&#xA;&lt;div class=&#34;highlight&#34;&gt;&lt;pre tabindex=&#34;0&#34; style=&#34;color:#4c4f69;background-color:#eff1f5;-moz-tab-size:4;-o-tab-size:4;tab-size:4;&#34;&gt;&lt;code class=&#34;language-python&#34; data-lang=&#34;python&#34;&gt;&lt;span style=&#34;display:flex;&#34;&gt;&lt;span&gt;x, y, &lt;span style=&#34;color:#04a5e5;font-weight:bold&#34;&gt;...&lt;/span&gt; &lt;span style=&#34;color:#04a5e5;font-weight:bold&#34;&gt;:=&lt;/span&gt; op(a, b, c, &lt;span style=&#34;color:#04a5e5;font-weight:bold&#34;&gt;...&lt;/span&gt;)&#xA;&lt;/span&gt;&lt;/span&gt;&lt;/code&gt;&lt;/pre&gt;&lt;/div&gt;&lt;p&gt;to be understood as an operation &lt;code&gt;op&lt;/code&gt; applied on the SSA values &lt;code&gt;a, b, c, ...&lt;/code&gt;&#xA;and producing the output values &lt;code&gt;x, y, ...&lt;/code&gt;.&lt;/p&gt;</description>
    </item>
    <item>
      <title>Graph transformation in minIR</title>
      <link>http://localhost:1313/03_compiler/secrewrite-def/</link>
      <pubDate>Mon, 01 Jan 0001 00:00:00 +0000</pubDate>
      <guid>http://localhost:1313/03_compiler/secrewrite-def/</guid>
      <description>&lt;p&gt;As discussed in &lt;span&gt;section &lt;/span&gt;&lt;a href=&#34;#sec-compgraphs&#34;&gt;3.2&lt;/a&gt;, computation graphs with linear&#xA;values, such as minIR, must adopt strict graph transformation semantics to&#xA;ensure that linear constraints are satisfied at all times. In this section, we&#xA;use the minIR graph category presented in the previous section to define&#xA;transformation semantics that lean on the double pushout (DPO) &lt;span class=&#34;citation&#34;&gt;&lt;span data-bibtex-key=&#34;Ehrig1976&#34; class=&#34;citation-key&#34;&gt;Ehrig, 1976&lt;/span&gt;&lt;span class=&#34;citation-full&#34;&gt;&lt;span class=&#34;authors&#34;&gt;Hartmut  &lt;span class=&#34;last-name&#34;&gt;Ehrig&lt;/span&gt; and Hans-Jörg  &lt;span class=&#34;last-name&#34;&gt;Kreowski&lt;/span&gt;&lt;/span&gt;. 1976. Parallelism of manipulations in multidimensional information structures&lt;/span&gt;&lt;/span&gt; and&#xA;sesqui-pushout (SqPO) &lt;span class=&#34;citation&#34;&gt;&lt;span data-bibtex-key=&#34;Corradini2006&#34; class=&#34;citation-key&#34;&gt;Corrad., 2006&lt;/span&gt;&lt;span class=&#34;citation-full&#34;&gt;&lt;span class=&#34;authors&#34;&gt;Andrea  &lt;span class=&#34;last-name&#34;&gt;Corradini&lt;/span&gt;, Tobias  &lt;span class=&#34;last-name&#34;&gt;Heindel&lt;/span&gt;, Frank  &lt;span class=&#34;last-name&#34;&gt;Hermann&lt;/span&gt; and Barbara  &lt;span class=&#34;last-name&#34;&gt;König&lt;/span&gt;&lt;/span&gt;. 2006. Sesqui-Pushout Rewriting. In &lt;em&gt;Graph Transformations&lt;/em&gt;, Berlin, Heidelberg. Springer Berlin Heidelberg, 30--45. &lt;span class=&#34;doi&#34;&gt;doi: &lt;a href=&#34;https://doi.org/10.1007/11841883_4&#34;&gt;10.1007/11841883_4&lt;/a&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt; semantics in adhesive categories &lt;span class=&#34;citation&#34;&gt;&lt;span data-bibtex-key=&#34;Lack2005&#34; class=&#34;citation-key&#34;&gt;Lack, 2005&lt;/span&gt;&lt;span class=&#34;citation-full&#34;&gt;&lt;span class=&#34;authors&#34;&gt;Stephen  &lt;span class=&#34;last-name&#34;&gt;Lack&lt;/span&gt; and Pawel  &lt;span class=&#34;last-name&#34;&gt;Sobocinski&lt;/span&gt;&lt;/span&gt;. 2005. Adhesive and quasiadhesive categories. &lt;em&gt;RAIRO - Theoretical Informatics and Applications&lt;/em&gt; 39, 3 (July 2005, 511--545). &lt;span class=&#34;doi&#34;&gt;doi: &lt;a href=&#34;https://doi.org/10.1051/ITA:2005028&#34;&gt;10.1051/ITA:2005028&lt;/a&gt;&lt;/span&gt;&lt;/span&gt;&lt;/span&gt;.&lt;/p&gt;</description>
    </item>
    <item>
      <title>MinIR rewriting, operationally</title>
      <link>http://localhost:1313/03_compiler/secrewrite-operational/</link>
      <pubDate>Mon, 01 Jan 0001 00:00:00 +0000</pubDate>
      <guid>http://localhost:1313/03_compiler/secrewrite-operational/</guid>
      <description>&lt;p&gt;The previous section proposed to view minIR rewrites as the result of a (DPO or&#xA;SqPO) graph transformation. This yields valid rewriting semantics elegantly (and&#xA;with little effort!). However, the conditions that must be imposed on the&#xA;transformation to be valid, along with the fact that pushouts may not exist mean&#xA;that the existence of a rewrite given a transformation rule and a match is not&#xA;guaranteed.&lt;/p&gt;&#xA;&lt;p&gt;In this section, we address this by considering a more restricted notion of&#xA;minIR rewriting, for which the existence of the right-hand side of the rewrite&#xA;is guaranteed. In addition, in place of the categorical presentation of the last&#xA;section, we express the rewriting operation &lt;em&gt;operationally&lt;/em&gt;, i.e. as data and a&#xA;procedure on sets that translates directly into an algorithmic implementation.&lt;/p&gt;</description>
    </item>
  </channel>
</rss>
