People of ACM - Mingsheng Ying

December 3, 2019

Some leading physicists have hypothesized that the universe is a quantum computer. Will you explain what they mean by this?

It seems that there is not a precise formulation of such a hypothesis, and different people have different understandings. There is a beautiful popular science book about it, Programming the Universe: A Quantum Computer Scientist Takes on the Cosmos by Seth Lloyd. I’m not a physicist, so I don’t know to what extent this hypothesis is true. But coincidentally, in the Prospects chapter of my quantum programming book, I wrote (half jokingly and half seriously): “If you agree with this view (the universe is a quantum computer), I would like to argue that God (or nature) is a quantum programmer.” My implication there is that perhaps, some ideas from (quantum) programming theory may be applied to quantum physics. I’m fascinated by questions such as: can weakest preconditions and predicate transformations (backward view), parallelism, concurrency, and recursion from programming theory provide a new insight to physics, or a new way of thinking about quantum physical systems?

Many have noted that there have been significantly more advances on the hardware/physical side of quantum computing, rather than the software/algorithmic side. Do you agree with that assertion?

There is no doubt that significant advances on the hardware/physical side of quantum computing have been made in the last few years, and it will continue to be the driving force of the whole field of quantum computing in the future.

On the other hand, several breakthroughs in quantum algorithms happened well before these hardware advances, and in fact, they motivated the industry to invest in quantum hardware research. Research on quantum algorithms and complexity and on quantum cryptography has been extensively conducted for over two decades.

Recently, research on quantum computer architecture, quantum programming languages and compilers, design automation (EDA) for quantum computing, quantum networking and internet, etc., has begun to emerge.

In what area of quantum computing do you expect we will see significant advances in the near future?

First, from the viewpoint of quantum computing as a science, we don’t fully understand where the boundary is between the problems tractable by classical computation and those by quantum computation, and the limitation of quantum computation. So, we will see more research in quantum algorithms and complexity. Furthermore, research in this area will certainly find applications in other areas like quantum and post-quantum cryptography, quantum machine learning, and optimization.

Second, I expect significant progress in quantum hardware. This will pave the road for quantum computing as a practical technology. Many believe that quantum advantage (wherein quantum computers will be able to solve problems faster than classical computers) will occur in a couple of years. If this really happens, then we can imagine research on architecture of quantum computers, operating systems for quantum computers, quantum programming languages and compilers, and many more engineering areas blossoming. The full stack of computer science and technology will be extended to quantum computing.

Perhaps the basic structure of quantum computer science will be similar to that of classical computer science, but their deep layers will be very different, because the former is based on the principles of quantum mechanics. For example, everyone knows that the unique quantum features like superposition, entanglement, and noncommutativity of observables enable us to design faster quantum algorithms and more secure quantum cryptographic protocols than their classical counterparts, but what’s not talked about as much is the fact that these same quantum features will also significantly increase the difficulty of software testing, debugging, analysis and verification.

Why is developing a verified quantum software stack from the beginning essential to the growth of quantum computing?

It is well known that the cost of software errors is huge. It is conceivable that the same will happen for future quantum computers. The early software for classical computers was developed well before a precise notion of program correctness was defined. But now we have a chance in quantum computing to develop a trustworthy software stack from the beginning. Hopefully, this will avoid a lot of troubles in future quantum software development. Several efforts have been made in the last 10 years to develop techniques for analysis and verification of quantum programs. I’m particularly happy to see that several groups have already reported their very interesting work on certified quantum compilers. Some interesting papers in this area include: Verified Optimization in a Quantum Intermediate Representation, Contract-based verification of a realistic quantum compiler and A Verified Optimizer for Quantum Circuits. I also co-authored the paper Formal Verification of Quantum Algorithms Using Quantum Hoare Logic, which explored some of these issues.

What is the vision that you and Co-EIC Travis Humble have for ACM Transactions on Quantum Computing?

For historical reasons, papers on quantum computing have been mainly published in physics journals. Recent advances in quantum computing have moved this new field to a tipping point where hardware devices are going beyond the prototype stage to become useful tools, which, in turn, provide new opportunities to apply the principles of computer science. This can be seen from the rapidly increasing number of quantum papers presented in ACM conferences like STOC, ISCA, POPL, etc. Perhaps due to this, the ACM Publications Board decided to develop a new, computing-centric journal on quantum information science, different from other journals that tend to focus more on physics. When I was contacted by the ACM staff, I hesitated to take the role of EIC because it means a large amount of workload. After discussions with ACM staff and being introduced to Travis, I gradually realized that such a journal will help to foster this promising field.

Currently, quantum computing is very different from other areas of computer science. Indeed, it traverses many different areas. This requires us to use some different strategies to attract high-quality submissions. Travis and I will do our best to achieve this. We will also invite surveys by leaders in this area that will hopefully encourage and help the younger generation to enter this exciting field. With the efforts of the editorial board, we hope that this journal will become a flagship journal in the field by the end of our tenure as EICs.

Mingsheng Ying is a Distinguished Professor and Research Director of the Center for Quantum Software and Information at the University of Technology Sydney, Australia. He is also Deputy Director for Research (adjunct position) at the Institute of Software at the Chinese Academy of Sciences, and holds the Cheung Kong Chair Professorship at Tsinghua University, China. Ying was also the Director of the Scientific Committee of the National Key Laboratory of Intelligent Technology and Systems at Tsinghua University. His research interests include quantum computation, theory of programming languages, and logics in AI. He has published two books: Foundations of Quantum Programming (2016) and Topology in Process Calculus: Approximate Correctness and Infinite Evolution of Concurrent Programs (2001).

Ying received an NSF China Distinguished Young Scholar Award and a China National Science Award in Natural Science. He has served on the editorial board of several publications including Artificial Intelligence Journal. He was recently appointed Co-Editor-in-Chief (with Travis Humble) of the new journal, ACM Transactions on Quantum Computing (TQC).