Projects

Quartz: Superoptimization of Quantum Circuits

Existing quantum compilers optimize quantum circuits by applying circuit transformations designed by experts. This approach requires significant manual effort to design and implement circuit transformations for different quantum devices, which use different gate sets, and can miss subtle optimizations that are hard to find manually. We propose Quartz, a quantum circuit superoptimizer that automatically generates and verifies circuit transformations for arbitrary quantum gate sets. Given a gate set, Quartz generates possible circuit transformations by enumerating small circuits over the given gate set, and verifies them with a automated theorm solver. Quartz then applies the verified transformations to optimize quantum circuits. Evaluation shows that the transformations generated and verified by Quartz cover the manually designed ones used by existing optimizers, and Quartz's optimizer matches the performance of existing optimizers on one gate set for which they are tuned, and outperforms them on the two other gate sets.

WavingSketch: An Unbiased and Generic Sketch for Finding Top-k Items in Data Streams

Finding top-k items in data streams is a fundamental problem in data stream mining. Existing algorithms that can achieve unbiased estimation suffer from poor accuracy. We propose WavingSketch, which is unbiased, accurate, generic and fast. It has four primary use cases: finding top-k frequentitems, finding heavy changes, finding persistent items,and finding Super-Spreaders. Experimental results show that, compared with the SOTA, WavingSketch has 4.50 times higher insertion speed and up to 9×10^6 times (2×10^4 times in average) lower error rate in finding frequent items with limited memory.

BurstSketch: Finding Bursts in Data Streams

Burst is a common pattern in data streams and burst detection has attracted extensive attention from the research community. We propose BurstSketch to detect bursts accurately in real time. BurstSketch uses the technique Running Track to select potential burst items efficiently, and it monitors the potential burst items and capture burst pattern by a technique called Snapshotting. Experimental results show that our algorithm achieves a 1.75 times higher recall rate than the strawman solution.