Yuval Rishu Sanders

Senior Lecturer, Centre for Quantum Software and Information, University of Technology Sydney

• Contact: yuval.sanders@uts.edu.au
• arXiv: sanders_y_1
• ORCID: 0000-0001-8003-0039

Research Statement

A quantum computer, if built, is believed to be able to outperform any non-quantum (“classical”) computer. The outperformance derives not from an evolution in computer technology enabling more efficient logical operations but from a foundational shift in the very concept of a computer enabled by quantum technologies.

Classical computers are, by definition, equivalent in a technical sense to a model proposed by Alan Turing involving a simple machine and an infinite “tape” onto which the symbols 0 and 1 may be written, read, copied, and erased. Quantum computers, by contrast, allow for the possibility that the tape could store quantum superpositions of the symbols 0 and 1. Theoretical complexity analysis of such a machine indicate that the machine could carry out certain computational tasks in a more scalable manner than any classical computer.

The most prominent example of quantum outperformance is given by Shor’s algorithm, which finds a non-trivial factor (if it exists) of an input integer with high probability in polynomial time. By contrast, theoretical computer scientists believe that a classical computer requires more than polynomial time to accomplish the same feat. In fact, the information technology sector is so comfortable with this assertion that a great many cybersecurity protocols assume that an attacker cannot efficiently factorise a large integer. Thus Shor’s algorithm proves quantum computers capable of breaking widely deployed cryptosystems.

The above is my rendition of the standard argument supporting the need for quantum computing research and development. But there is a serious weakness to the story: it may be the case that powerful enough quantum computers will eventually defeat classical computers, but it remains to be seen whether it is technologically feasible to build such large quantum computers. This question of technological feasibility can be expressed in terms of how powerful a quantum computer will be needed to outperform present-day or near-future classical computers for a useful task. To be blunt, this question has not been answered.

Attempts have been made to answer the question. For example, researchers from Google [doi:10/gmbpbg] analysed how much time would be needed for a surface-code-architecture quantum computer with access to 20 million noisy qubits to break 2048-bit RSA (the quintessential cryptography algorithm that relies on the assumed classical difficulty of factorising integers). Their answer: around 8 hours, based on an estimation of the “approximate cost” using “plausible physical assumptions”. I myself have “estimated the approximate cost” [doi:10/fhht] of quantum algorithms with Google researchers and believe that these estimates are highly unreliable.

My ambition is to enable reliable analysis of quantum computations in order to ascertain if, when, and how a quantum computer will beat classical computers at some useful task. Whereas this kind of forecasting is unavoidably based on presumptions about the performance of future technology, those presumptions can be summarised in terms of a computational cost model. One potential quantum computer application could be rigorously analysed in terms of its performance on a hypothetical machine and then the computational cost model would be used to assess how well a real quantum computer would simulate the hypothetical machine. In other words, the analysis of the application is distinct from the analysis of the technology. The application analysis need not be nearly so crude as it is today.

Vision

I aim to enable accurate computational cost analysis of potential quantum computer applications by developing the software support needed to automate that analysis. Currently, this task is carried out ‘by hand’ by expert teams of researchers over many months. I propose to develop software tools that can accomplish the same task in minutes and with greater accuracy.

This set of software tools could roughly be called a “compiler” because it would translate code written in a high level quantum programming language (that I have tentatively called QuO) into quantum circuits suitable for optimisation and execution on quantum hardware. Because the compiler will return quantum circuits, which play a similar role to machine instructions in classical hardware, it will be possible to produce complementary software that analyses the output of the compiler for expected cost under a variety of hardware scenarios, including potential future scenarios.

By enabling such automatic analysis of high-level quantum code, my research will enable a vastly more efficient design process for quantum computer applications. Currently, the sticking point in this design process is the time cost of evaluating possible applications for performance relative to classical counterparts. This could enable a 100,000-fold (≈ 2.5 months / 1 minute) speedup in the design iteration process and pave the way for significantly more sophisticated and reliable cross-comparisons between quantum and classical solutions. This would additionally prove fertile ground for the development of “quantum inspired” algorithms.

Curriculum Vitae

Employment

Education