qiskit-toqm / libtoqm Goto Github PK

This project forked from arihayes/toqm

A C++11 class library port of the reference implementation originally published alongside paper Time-Optimal Qubit Mapping.

License: Apache License 2.0

C++ 0.58% CMake 0.01% OpenQASM 99.40% Shell 0.01%

libtoqm's Introduction

libtoqm

A C++11 class library port of the reference implementation originally published alongside paper Time-Optimal Qubit Mapping.

There are two build targets here:

libtoqm, a class library that exposes the full breadth of configuration options and algorithms available in the reference implementation.
mapper, an interactive commandline program that mimics the behavior of the original reference program, written on top of libtoqm.

Example usage

// Construct mapper with desired configuration.
toqm::ToqmMapper m(
	toqm::DefaultQueue {},
	std::make_unique<toqm::DefaultExpander>(),
	std::make_unique<toqm::CXFrontier>(),
	std::make_unique<toqm::Latency_1_3>(),
	{},
	{std::make_unique<toqm::HashFilter>(), std::make_unique<toqm::HashFilter2>()}
);

// Run TOQM algorithm on a particular gate listing and target.
m.run(gates, num_qubits, coupling_map);

References

Time-Optimal Qubit Mapping paper: Chi Zhang, Ari B. Hayes, Longfei Qiu, Yuwei Jin, Yanhao Chen, and Eddy Z. Zhang. 2021. Time-Optimal Qubit Mapping. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’21), April 19–23, 2021, Virtual, USA. ACM, New York, NY, USA, 14 pages.
TOQM reference implementation, published with paper.
@arihayes fork, which adds the Table latency class used in this library to support arbitrary 2 qubit operations and also make changes to how latency is handled.

libtoqm's People

Contributors

Stargazers

Watchers

Forkers

kevinhartman

libtoqm's Issues

Dependency graph doesn't respect classical bits

The current implementation doesn't take into account classical bits when constructing the gate dependency graph. This means that gates that have an ordering with respect to each other only because of classical writes (e.g. successive measurements of different qubits to the same classical bit) will not necessarily be ordered properly.

To fix this, classical bits must be considered when building the dependency graph. This also means that the GateOp struct needs to record each gate's classical bits as well.

Asymmetrical coupling maps probably don't work

Most places in the code check for compatibility with the coupling map in either direction, but really only the exact direction should be acceptable.

[mapper] Refactor QASM and other text parsers to avoid memory leaks

Currently, the mapper executable exhibits memory leaks due to char buffer allocations that are never freed when parsing text files.

Support variable number of qubits

Currently, the max number of supported qubits is a compile-time constant. It should be fairly easy to remove this restriction, but some arrays will need to be changed to vectors and maps.

`GreedyMapper` doesn't respect initial search cycles

Specifying initialSearchCycles as 0 does not seem to work when GreedyMapper is used.

This means that some "pure" swaps are still performed at the start of the circuit, meaning that the initial layout becomes no longer trivial.

Until this is fixed, users should expect that libtoqm may end up using a non-trivial initial layout. For qiskit-toqm, this means ToqmSwap needs to always check for updates to the layout, even if initialSearchCycles was passed as 0.

Remove `ToqmMapper::run` `num_qubits` parameter

This is used for some allocations, but we can derive it from other parameters.

Zero latency gate support improvements

Currently, zero latency gate support exists but has some limitations/issues.

Node::scheduleGate should allow zero-latency gates to be scheduled, always. Currently, scheduling will be blocked if a non-zero latency gate has already been scheduled. Note that this is different from the recursive scheduling of zero-latency gates that follows the scheduling of the first gate in a cycle.
When a zero-latency gate is the first gate scheduled for a set of qubits in Node::scheduleGate on the 0th cycle only, we recursively schedule ready gates up to and including the first non-zero latency gate, if one exists. This behavior is actually probably not right for two reasons: 1) it should be able to happen on any cycle if we do this at all, not just cycle 0, and 2) expanders that call Node::scheduleGate might not expect non-zero latency gates to be scheduled. For example, DefaultExpander distinguishes between 1 cycle gates (singleCycleGates) and > 1 cycle gates (possibleGates).

Latency `Table` can lead to nontermination

When ToqmMapper is configured with Table latency and Table is constructed with qubit-specific gate durations, some circuit runs do not seem to terminate.

A minimal repro case still needs to be determined, but it seems that this can happen when using heuristic configuration classes, such as TrimSlowNodes and GreedyTopK. The original TOQM implementation has no testing with coupling-specific gate durations, so it's quite likely there's a preexisting bug.