Project Title

A parallel algorithm for quantum circuit synthesis


Michele Mosca, University of Waterloo and Olivia Di Matteo, PhD student

Supported by

SOSCIP, IBM Canada Ltd., NSERC, University of Waterloo

Website >


With activities like online banking and shopping on the rise, Canada will require adept problem solvers to develop secure protocols and encryption software to protect sensitive data.

“The world is going to need programmers and problem solvers,” said Olivia Di Matteo, a second year PhD student at the University of Waterloo. 

Di Matteo is working with Prof. Michele Mosca to develop software for quantum circuit synthesis, a process that “translates” arbitrary quantum operations into a set of instructions that can run on a quantum computer. 

The project supports start-up company evolutionQ which provides cybersecurity risk assessments. EvolutionQ was co-founded by Profs. Mosca and Norbert Lütkenhaus, from the University of Waterloo.

With access to SOSCIP’s BGQ, the team were able to solve big problems quickly.

“There weren’t enough processors to solve the problems that were interesting to us. The software is largely parallel, so we needed a lot of time and processors. Because we were able to get so many processors working together, our run time changed from a week to a couple of minutes,” said Di Matteo.

“It is imperative that this quantum threat is mitigated before it becomes a reality.”

Michele Mosca
University of Waterloo

Case in point, the biggest program the team ran took 4000 processors and 21 hours, a project which would have taken weeks or longer on standard systems.

Di Matteo, who is a recipient of an NSERC Canada Graduate Scholarship for her PhD studies, also credits SOSCIP’s expert knowledge.

“I had a little training in HPC but not in parallel computing and we needed to learn how to make all of the processors talk to each other effectively. The technicians were helpful in understanding how to best take advantage of the technology. If I got stuck and didn’t know if my method was efficient, I had someone to get suggestions from.”

For Prof. Mosca, now is the time for this research.

“We’re trying to develop the foundation of a software industry that I hope Canada can be a world leader in.

“Our research directly impacts cybersecurity, since the currently deployed cryptographic infrastructure, which underpins cybersecurity, will be compromised by a large scale quantum computer. It is imperative that this quantum threat is mitigated before it becomes a reality,” explained Prof. Mosca.