openqasm/qe-qasm

A LALR(1) OpenQASM Parser and AST Generator.

qe-qasm

The Quantum Engine's implementation of an OpenQASM v3.0 lexer and parser written in C++. The Quantum Engine is a system comprised of low-level software components enabling the execution of quantum programs in quantum hardware. The parser is based on Flex and Bison, and therefore it is a LALR parser.

This is a CMake Project. It builds four libraries:

• libqasmParser.{so|a}
• libqasmAST.{so|a}
• libqasmFrontend.{so|a}
• libqasmDIAG.{so|a}

and a simple CLI tool QasmParser for demonstrations and testing.

These libraries can be used to work on further development of a fully functional OpenQASM 3 compiler. In particular, the library is used by the qe-compiler to parse OpenQASM 3 source files to MLIR.

Contents

• qe-qasm
  • Contents
  • Building from source
    • Conan
      • Building for development and debugging
    • Make
      • Running Tests
  • Static Code Checks
  • CI and Release Cycle
    • CI
    • Branches
    • Tags
    • Release cycle
    • Example release cycle

Building from source

The parser's build system is driven by Cmake. For simplicity of building, packaging and distribution we provide a conan packager and recommend this for development/integration.

Currently the supported platforms are Linux and OSX. It is possible to build on Windows using WSL.

Conan

• Clone this repo: git clone [email protected]:openqasm/qe-qasm.git
• Install build dependencies: pip install -r requirements-dev.txt
  • It is recommended to use a Python virtual environment for this
• The package may be built and installed to conan with: conan create . --build=outdated -pr:h default -pr:b default
  • This will build the conan package and install it locally. The version will be detected automatically from the repo tag.
  • If you wish to override the package name, version or remote do so by calling conan with conan create . <package>/<version>@remote -pr:h default -pr:b default

Building for development and debugging

• Create a build directory: mkdir build && cd build/
• Install package with: conan install .. --build=outdated -pr:h default -pr:b default which will install and build all missing dependencies
• Build the package with: conan build ..
• The package tests may be run with: conan build .. --test

Make

• Clone this repo: git clone [email protected]:openqasm/qe-qasm.git

• Install build dependencies: pip install -r requirements-dev.txt

  • It is recommended to use a Python virtual environment for this

• Install a recent GCC or LLVM/clang compiler that supports C++17, GNU MP, GNU MPFR, GNU MPC, GNU Flex and GNU Bison installed on your system. Please make sure you install the devel packages for GNU MP, GNU MPFR and GNU MPC.

  Recommended versions are:

  • GCC: >= 9.2
  • LLVM: >= 10.0

• Install the package dependencies:

  • Versions:
  • Bison: >= 3.6.2
  • Flex: >= 2.6.1
  • GNU MP: >= 5.0.0
  • GNU MPFR: >= 4.0.0
  • GNU MPC >= 1.0.0
  • CMake: >= 3.17.0
  • Platforms:

    • Linux: Recent versions of Fedora (32 or 33) or Ubuntu (20.X.X) should satisfy these version requirements.

    • On Fedora (RedHat), the names of the packages are:

    • gmp(gmp-devel)

    • mpfr(mpfr-devel)

    • libmpc(libmpc-devel)

    • Apple Darwin (MacOS):

    • GCC is a symlink to clang. Building with GCC on MacOS is not supported.

    • You need XCode >= 14.2. Lower versions do not handle static initializations correctly on MacOS M1 (AArch64).

    • Most of the Toolchain utilities provided by Darwin by default in /usr/bin are much too old to be able to build qe-qasm correctly. Recent equivalents of these tools must be downloaded from Homebrew [ https://brew.sh/ ].

    • List of dependencies that must be installed from Homebrew:

      • flex
      • bison
      • gmake
      • cmake
      • gmp
      • mpfr
      • libmpc
      • m4

    • Please consult the Homebrew documentation on how to use Homebrew.

    • If you want to use the Homebrew LLVM: The LLVM lld linker [lld] needs a symlink created to itself in order to work correctly. To do so:

      • cd to the Homebrew LLVM installation directory:
        • /opt/homebrew/opt/llvm/bin on MacOS M1
        • /usr/local/opt/llvm/bin on MacOS x86_64
      • ln -sf lld ld64.lld

• Prepare the build directory: mkdir build && cd build

• Configure: cmake -G "Unix Makefiles" ..

  • If dependencies are not installed or properly setup errors may be raised

• Build with: make

  • This will build both static and shared libraries

• Running: make DESTDIR=/path/to/DESTDIR/ in the build directory will install the required libraries and header files to /path/to/DESTDIR/.

Running Tests

• There are a number of OpenQASM 2.0 and OpenQASM 3.0 tests in the directory `./tests``.
• You can run any of these tests manually as: ./QasmParser -I../../qasm/tests/include ../../qasm/tests/src/<test-name>.qasm from the 'build/bin' directory.
• You can also run the ./short-run-tests.sh shell script found in the tests directory. It runs all the tests in the ../../tests/src directory. This script is intended to be run from the build/bin`` directory. Alternatively, you can run the 'make test' target from the toplevel build`` directory. This will run all the tests using the CMake CTest utility.
• QasmParser will tell you if it could parse and generate the AST for the OpenQASM program correctly, or if it encountered an errror.
• A pseudo-XML output of the AST being built by the parser will be printed either to stdout, or to the file used to capture QasmParser's output.

Static Code Checks

The easiest, fastest, and most automated way to integrate the formatting into your workflow is via pre-commit. Note that this tool requires an internet connection to initially setup because the formatting tools needs to be downloaded.

In environments without an internet connection, please see one of the other solutions documented below.

These should be installed and setup prior to any development work so that they are not forgotten about. The setup is straight forward:

pip install pre-commit
pre-commit install

The first time pre-commit install is run, it will take a minute to setup the environment.

After installation, the hooks will be run prior to every commit, and will be run against all staged changes. Optionally, you can trigger this run via pre-commit run.

If you wish to run the hooks against the entire repository, run:

pre-commit run --all-files

The other checks that are performed can be seen in .pre-commit-config.yaml. At the time of writing, these are:

• No direct committing to main, or release/*
• Check json for validity
• Ensure newline character at the end of files
• Trim end of line whitespace characters
• Check for no merge conflict lines accidentally being staged
• Clang format
• Python block (line length 100)

CI and Release Cycle

Please keep the following points in mind when developing:

CI

CI is currently run on every pull request against the main branch. All CI processes are based on the conan package build.

Branches

• main: The main branch is used for the development of the next release. It is updated frequently and should not be considered stable. On the development branch, breaking changes can and will be introduced. All efforts should be made to ensure that the development branch is maintained in a self-consistent state that is passing continuous integration (CI). Changes should not be merged unless they are verified by CI.
• release/<major.minor> branches: Branches under release/<major.minor> are used to maintain released versions of the qe-qasm parser. They contain the version of the parser corresponding to the release as identified by its semantic version. For example, release/1.5 would be the compiler version for major version 1 and minor version 5. On these branches, the parser is considered stable. The only changes that may be merged to a release branch are patches/bugfixes. When a patch is required when possible the fix should first be made to the development branch through a pull request. The fix should then be backported from the development branch to the target release branch (of name release/<major.minor>) by creating a pull request on Github into the target release branch with the relevant cherry-picked commits. The new release branch HEAD should be tagged (see Tags) with a new <major.minor.patch> version and pushed to Github.

Tags

Git tags are used to tag the specific commit associated with a versioned release. Tags must take the form of v<major>.<minor>.<patch>-<labels>. For example the semver v1.5.1 would point to the parser release with major version 1, minor version 5, and, patch version 1. The current development version would therefore be MINOR+1 v1.6.0. All official releases when tagged must always point to the current HEAD of a release branch.

Release cycle

To release a version a new version:

• (Option A) If releasing a major/minor version create a new release branch for the version (See Branches). This should be cut from the latest development branch.

  git checkout -b release/<version> <base>
  git push -u origin release/<version>

• (Option B) If releasing a patch version:
  • checkout the existing release branch for your target major/minor version to apply the patch

  git checkout -b <backport>-<desc>-release/<version> release/<version>

  • Apply your changes (or cherry-pick existing commits) to your new branch and then push your branch to Github

  git push -u origin <your-branch>

  • Make a PR from your new branch into the target release/<version> branch with the form [Backport] <Title> and merge the PR
• Create a new tag with the required semantic version number (see Tags), tagging the HEAD of the target release/<version> branch. Push the tag to Github which will trigger CI.

  git tag -a v<version> -m "<description> e.g. release v<x>.<y>.<z>" # <- where version is the version number of the tag.
  git push -u origin v<version>

Example release cycle

For this example assume the current release of the parser is version 0.5.1. This will correspond to a commit on release/0.5. The project's development branch reflects the development state of the next release - 0.6.0 and is referred to by version as 0.6.0-dev.

To trigger a bugfix release - 0.5.2:

1. Create a PR into release/0.5 with all required changes. The PR ideally should begin with title of the form [Backport] <Title>. These may be backported commits from main.
2. Upon merger of the PR tag the HEAD of release/0.5 with v0.5.2 and push to Github.

To trigger a minor release - 0.6.0:

1. Create a new release branch release/0.6 using the current development branch (main) as the base branch, eg., git checkout -b release/0.6 main.
   • Note: Branch protection rules are in place for release branches and these steps may only be completed by project administrators.
2. Push this branch to Github.
3. Tag the branch with v0.6.0 and push to Github.

qe-qasm's Issues

qss-qasm must build the complete Graph for nested conditionals

Currently, qss-qasm only handles simple (non-nested) if/else-if/else conditionals. For complex cases (nested conditionals) the Graph is not generated correctly.

qss-qasm should generate a complete and correct Graph for nested conditionals.

ASTTypeDiscovery.cpp (Type Inference) is messy

ASTTypeDiscovery.cpp needs a revamp. The current code is quite messy. It does the job, but needs a clean-up.

This is low priority

Simplify the discovery of an Induction Variable from an indexed ASTIdentifier

OQ3 currently supports programming constructs such as this:

OPENQASM 3.0;

gate h a { U(π/2, 0, π) a; }

qubit[4] q;

for i in [0:3] {
  h q[i];
}

Currently, it is very difficult for consumers of the AST to determine the origin of the i identifier used as an array-style index, and whether or not it is the Induction Variable of the loop, or a variable declared independently of the loop.

The purpose of this enhancement is to make it easier for consumers of the AST to determine the origin of the variable used as an array-style index.

qss-qasm needs CodeGen

In order to maintain a clearly defined separation between the various sub-components of the Compiler, we need a CodeGen module.

This CodeGen module is responsible for consuming the final AST Represenation of the OpenQASM Program after all the transformations, including Semantic Analysis, are complete.

qss-qasm needs a LLVM-compatible Diagnostics Engine

The current DiagnosticEngine in qss-qasm is very barebones and minimal, and is incompatible with LLVM.

qss-qasm needs a LLVM-compatible DiagnosticEngine.

ASTIdentifierNode should inherit from ASTExpressionNode directly

This requires quite a bit of experimentation but it's worth doing because it will simplify the code.

qss-qasm needs Sema (semantic analysis)

qss-qasm needs to do more Semantic Analysis on the generated AST.

The Lexer (flex) and the Parser (bison) already do quite a bit of Semantic Analysis, but we do need more in a separate pass on the initial AST.

qss-qasm needs an N-Dimensional array implementation

The OQ3 Spec requires N-Dimensional arrays, so we're doing it.

Line number reported is off by one with direct string input

In the qe-compiler when the parser is called with a direct string input the reported line numbers are off by one.

https://github.com/openqasm/qe-compiler/blob/f50fc4ce43160c11db465759ccd7aed72ac830c3/lib/Frontend/OpenQASM3/OpenQASM3Frontend.cpp#L227-L229

oc - line: 5 col: 1
test.qasm:5:1: warning: While parsing OpenQASM3 input: 
Number of Gate Qubit params (bad) does not match the number of Qubit arguments provided (2).

gate bad q, t {} 
^

module {
  func.func @bad(%arg0: !quir.qubit<1>, %arg1: !quir.qubit<1>) {
    return
  }
  func.func @main() -> i32 {
    qcs.init
    %c0 = arith.constant 0 : index
    %c1000 = arith.constant 1000 : index
    %c1 = arith.constant 1 : index
    scf.for %arg0 = %c0 to %c1000 step %c1 {
      %dur = quir.constant #quir.duration<1.000000e+00> : !quir.duration<ms>
      quir.delay %dur, () : !quir.duration<ms>, () -> ()
      qcs.shot_init {qcs.num_shots = 1000 : i32}
      %0 = quir.declare_qubit {id = 0 : i32} : !quir.qubit<1>
      quir.call_gate @bad(%0) : (!quir.qubit<1>) -> ()
      %false = arith.constant false
    } {qcs.shot_loop}
    qcs.finalize
    %c0_i32 = arith.constant 0 : i32
    return %c0_i32 : i32
  }
}

(qss-compiler) thomas@Thomass-MBP build % cat test.qasm | bin/qss-compiler -X qasm --emit mlir
Loc - line: 4 col: 1
<stdin>:4:1: warning: While parsing OpenQASM3 input: 
Number of Gate Qubit params (bad) does not match the number of Qubit arguments provided (2).


^

module {
  func.func @bad(%arg0: !quir.qubit<1>, %arg1: !quir.qubit<1>) {
    return
  }
  func.func @main() -> i32 {
    qcs.init
    %c0 = arith.constant 0 : index
    %c1000 = arith.constant 1000 : index
    %c1 = arith.constant 1 : index
    scf.for %arg0 = %c0 to %c1000 step %c1 {
      %dur = quir.constant #quir.duration<1.000000e+00> : !quir.duration<ms>
      quir.delay %dur, () : !quir.duration<ms>, () -> ()
      qcs.shot_init {qcs.num_shots = 1000 : i32}
      %0 = quir.declare_qubit {id = 0 : i32} : !quir.qubit<1>
      quir.call_gate @bad(%0) : (!quir.qubit<1>) -> ()
      %false = arith.constant false
    } {qcs.shot_loop}
    qcs.finalize
    %c0_i32 = arith.constant 0 : i32
    return %c0_i32 : i32
  }
}

Parser treats angle > 2pi as a warning

Currently, the parser is treating angles > 2pi as a warning. Angles are defined on a ring, ie., modulo 2pi, and should not be a warning. This creates a lot of unnecessary noise and confusion for end users who are currently receiving it since it does not impact their results.

I looked into suppressing this warning in the diagnostic system. However, I don't think a warning can be individually suppressed without parsing and discarding the warning diagnostic string as I do not believe there is type information available in the diagnostic to differentiate this warning outside of the message string itself? If there is a way I'd appreciate a pointer and I can do this instead. For the time being, I will suppress warning diagnostics being returned to the end-service user (which I don't think should be happening anyways as they are being reported as errors) .

I'm happy to put together a PR to remove this warning.

qss-qasm needs a real Preprocessor

qss-qasm's current Preprocessor is minimal and barebones. It needs to be made production quality.

Bug in cbit error diagnostic emission

The QASM source file:

cbit[4] var = "100";
var[3] = 1;

results in the following error:

Error: File: "test.qasm", Line: 2, Col: 1:
    Bitset indexed element access is out-of-bounds.
Maximum number of errors (1) has been reached. Exiting now.

The modified source file:

cbit[4] var = "0100";
var[3] = 1;

parses correctly.

It seems that the size check is using the size of the bit string instead of the declared size of the variable.

An ill-formed re-declaration should not ICE

The following test case:

OPENQASM 3.0;

input angle theta = 3.1414592;

input angle theta;

results in:

===> ICE [Internal Compiler Error]: File: "theta-redecl.qasm", Line: 5, Col: 13:
    Symbol theta was not found.
Compilation terminated abnormally.

The re-declaration is ill-formed but the error message generated (a) shouldn't be an ICE and (b) should be more explicit as to why it's an error.

Failure to parse classical expressions with binary and unary operations combined

When attempting to compile an expression like

OPENQASM 3.0;

qubit $0;

gate x q {}

bit[4] qc0_c0;

if ((qc0_c0[0] & qc0_c0[1] | qc0_c0[0] & qc0_c0[2] | qc0_c0[1] & qc0_c0[2]) & ~(qc0_c0[0] & qc0_c0[1] & qc0_c0[2])) {
    x $0;
}
qc0_c0[3] = measure $0;

Related to openqasm/qe-compiler#278

On OSX debug build fails in GetPreviousToken

When running tests for the qe-compiler against the latest release on debug build using GetPreviousToken there is a stack dump

 #5 0x0000000114ebfe76 std::__1::__tree_end_node<std::__1::__tree_node_base<void*>*>* std::__1::__tree_next_iter[abi:ue170006]<std::__1::__tree_end_node<std::__1::__tree_node_base<void*>*>*, std::__1::__tree_node_base<void*>*>(std::__1::__tree_node_base<void*>*) (/opt/conan/data/qasm/0.3.1/qss/stable/package/5bf0bcd8962802a2e1298e1c519669bbb70fd69e/lib/libqasmAST.0.0.1.dylib+0x8e76)
 #6 0x00000001154889ea std::__1::__tree_const_iterator<std::__1::__value_type<unsigned int, QASM::ASTToken*>, std::__1::__tree_node<std::__1::__value_type<unsigned int, QASM::ASTToken*>, void*>*, long>::operator++[abi:ue170006]() (/opt/conan/data/qasm/0.3.1/qss/stable/package/5bf0bcd8962802a2e1298e1c519669bbb70fd69e/lib/libqasmAST.0.0.1.dylib+0x5d19ea)
 #7 0x0000000115488997 std::__1::__map_const_iterator<std::__1::__tree_const_iterator<std::__1::__value_type<unsigned int, QASM::ASTToken*>, std::__1::__tree_node<std::__1::__value_type<unsigned int, QASM::ASTToken*>, void*>*, long>>::operator++[abi:ue170006]() (/opt/conan/data/qasm/0.3.1/qss/stable/package/5bf0bcd8962802a2e1298e1c519669bbb70fd69e/lib/libqasmAST.0.0.1.dylib+0x5d1997)
 #8 0x000000011548893b std::__1::reverse_iterator<std::__1::__map_const_iterator<std::__1::__tree_const_iterator<std::__1::__value_type<unsigned int, QASM::ASTToken*>, std::__1::__tree_node<std::__1::__value_type<unsigned int, QASM::ASTToken*>, void*>*, long>>>::operator--[abi:ue170006]() (/opt/conan/data/qasm/0.3.1/qss/stable/package/5bf0bcd8962802a2e1298e1c519669bbb70fd69e/lib/libqasmAST.0.0.1.dylib+0x5d193b)
 #9 0x00000001154723bb QASM::ASTTokenFactory::GetPreviousToken() (/opt/conan/data/qasm/0.3.1/qss/stable/package/5bf0bcd8962802a2e1298e1c519669bbb70fd69e/lib/libqasmAST.0.0.1.dylib+0x5bb3bb)
#10 0x0000000115466b9e QASM::ASTTypeDiscovery::ResolveASTIdentifier(QASM::ASTToken const*, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char>> const&) const (/opt/conan/data/qasm/0.3.1/qss/stable/package/5bf0bcd8962802a2e1298e1c519669bbb70fd69e/lib/libqasmAST.0.0.1.dylib+0x5afb9e)

Rename from qss (quantum systems software) to qe (quantum engine) - qasm

As part of migrating to the open source we are renaming this project from the qss (quantum systems software) prefix to qe (quantum engine).

Steps:

• Update the readme
• Rename the repository
• Migrate the repository to the openqasm organization
• Migrate all code references

Bug: If not allowed after switch statement

The following QASM program:

int switch_dummy;
switch (switch_dummy) {
  default: {
  }
}

bit a;
if(a == 1){
}

produces the following parse error:

Error: File: "test.qasm", Line: 8, Col: 2:
    An If Statement is not allowed here (ASTTypeSwitchStatement).
Maximum number of errors (1) has been reached. Exiting now.

From: https://github.ibm.com/IBM-Q-Restricted-System/qic-rta-driver/blob/dev/compiler/targets/systems/LesPaul/test/static/integration/openqasm3/switch-issue-1706-rz.qasm

Classical bitset of size zero not supported

If one creates a bit array of size zero (e.g. bit[0] c1;), the program will fail to parse

qe-qasm/include/qasm/AST/ASTCBit.h

Line 81 in f6d695f

assert(S > 0 && "Invalid bitset of size zero!");

However, this is not explicitly forbidden by the openqasm3 spec, as far as I can tell (see https://openqasm.com/language/types.html#arrays).

In the circuit-knitting-toolbox, we programmatically generate many circuits, all of which have two registers for consistency in handling them. But, one of the registers has zero bits in some of the circuits.

We can work around this easily, but I wanted to flag it as something that would be desirable to either support or clarify.

Code duplication in ASTProductionFactory.cpp

There is some code duplication in ASTProductionFactory.cpp, related to type inference from a toplevel ASTExpressionNode.

This should be abstracted out, and the code duplication removed - to the extent possible.

The qss-qasm Preprocessor should not use intermediate temporary files

Currently, qss-qasm's Preprocessor uses $TMPDIR to store intermediate representation temporary files.

This is bogus. It should not do that. Every intermediary transformation step should be done in-memory.

I actually have a concrete model and implementation for this capability, it just need to be applied to qss-qasm.