Hello!
For over a year now I’ve been working on software to do resource estimation (RE) for fault tolerant quantum computation (FTQC). I’ve been working on this as a part of the Quantum Benchmarking program funded by DARPA
Being part of this program was an amazing experience, I had an opportunity to work with many great people from all around the world. But this is a story for another time.
In this post I wanted to summarize my thoughts on what would make an ideal software for resource estimation.
Notes before we start: I’ll use “QRE” as shorthand for “Quantum Resource Estimation”. And by “quantum” here I really mean FTQC – nothing I’ll write about has anything to do with NISQ. It might apply, but it’s never my intent. This post is not an introduction to QRE. It’s targeted at people who are working on QRE or related topic and are already familiar with some parts of the stack we’ll be using here. But even so – if you’ll get lost at any point, please let me know in the comments! There are a few tools for resource estimation out there already – Azure QRE or resource estimation module in OpenFermion. They have some of the characteristics of “my dream QRE tool”, but not the others.I won’t mention them anywhere in the text, as I haven’t worked with them enough to be able to do them justice. However, if you’re interested in the topic and haven’t seen them yet, absolutely please check them out :)
Ok, so let’s start!
What is QRE and why is it hard?
Let’s start by briefly explaining what do we mean by QRE? Let’s say you want to know how long it will take to run an algorithm which solves a certain problem on a quantum computer.
I’ll start by making a horrible oversimplification, which sweeps under a rug A TON of problems – you already have a quantum circuit that you want to run on your quantum computer. What to do about it?
Well, since we need to account for error correction overhead, this is not as simple as calculating the depth of the circuit and then multiplying it by gate time. You need to understand how this circuit would be implemented on a real quantum computer, which might require the following reasoning (in the Q&A format):
Q: What gates do I have in my circuit?
A: I have Clifford gates and Pauli rotations
Q: Are these gates something that my error correction method can directly use?
A: Method I’m using can handle only Clifford+T gates, so we need to do something about rotations.
Q: What can I do about rotations?
A: You can either translate each rotation into a sequence of Clifford + T (i.e. gate synthesis), or estimate how many T gates each rotation gate will translate to.
Q: Let’s say we can compile it to Clifford+T. What resources do we even want to estimate?
A: Let’s estimate how much time the calculation will take and how many physical qubits it will take.
Q: Don’t these numbers depend on the characteristics of the physical hardware? For example gate time and gate fidelity?
A: That’s true – we can model the hardware by parameterizing these quantities.
Q: Do we want to distinguish between one-qubit gates and two-qubit gates?
A: For now we can treat them the same.
Q: Ok, how much does it take to implement each gate in a fault tolerant way?
A: It depends on the type of the gate and the failure rate of the whole circuit we want to achieve. You can never have a 0% failure rate, even on classical computers. So you need to specify what failure rate you’re willing to tolerate. In the surface code, for example, you can achieve a lower failure rate by increasing the code distance.
Q: Let’s assume we know the target failure rate. What resources are needed for each gate?
A: Each T gate might require thousands of Clifford gates itself, so as a first approximation we can cost out just them…
Let’s finish it here, as I really don’t want to spend this time getting into the details of how to build a T-gate factory. And how to implement this with the surface code. And how to calculate resources for it. And how those resources depend on the parameters of the hardware (quality of qubits, connectivity, architecture…). And how to take the decoding process into account. And that you can get other resources, such as energy needed or the physical area of the machine you need. Oh, not to mention dealing with space-time tradeoffs…
The main points I’ve tried to make are:
- When trying to perform resource estimation, there are a huge number of considerations and assumptions that go into making a particular estimate.
- Some of the assumptions depend on the compilation you’re using, some on the fault-tolerant protocols you’re considering, some on the hardware and some others depend on how accurate you want to be.
- It’s pretty complex.
Final note – I’m not super happy about the section that you’ve just read. But I really don’t have time to write a 3-part blogpost explaining all the nuances in detail right now, so I’ll just leave it as it is.
Ok, let’s now talk about how these translate into challenges for building a software that performs all of this automatically.
Main challenges
My focus is on challenges on the software level – not what makes QRE hard in general, but what makes it hard to write software for QRE.
Many assumptions
Performing resource estimates comes with many assumptions about the future hardware. The problem is that some of the assumptions might turn out to be incorrect in the future, so you don’t want to hardcode too many of them. Sometimes it’s hard to say what is an assumption and what is not, as some assumptions are not really being stated explicitly (e.g.: “we use surface codes” or “Clifford gates are cheap”). It’s unreasonable to write software without making any kind of assumptions, but managing them is a big challenge in QRE.
Science is changing
QRE as a subfield of quantum computing is a relatively young and small niche, which touches on many adjacent subfields (such as quantum algorithms, compilation, error correction, quantum hardware), all of which are developing rapidly. This means that every year there are many new improvements, algorithms and breakthroughs being made and it’s hard to keep up or have expertise in all of them. It’s very, very hard to find people who have a good, holistic understanding of all the concepts involved – I guess it’s under 100 people in the world, and that might be generous already. Therefore there are not many learning materials on the topic and good knowledge is very scarce. Fortunately it’s easier to find people who have deep understanding on particular parts of the QRE pipeline, but still – this knowledge is very specialized.
Another issue is that there’s no well-established language. It’s common that across many groups people use different words for the same thing or one word has different meaning for each group. This is typical for QC in general and I’ve been complaining about it for years, but it is definitely more acute when it comes to QRE because doing it properly requires input from each group.
A couple of mundane examples of why it makes writing software harder:
- we had too many meetings where it took us up to an hour to just understand that we’re talking about two things that were similar, but distinct in important ways. Both sides used the same word for it.
- imagine how the code looks like after you rename each variable 3 times…
- I think I’ve never worked on a project that had such a steep learning curve – onboarding new people to the project was taking a lot of time.
Ill-defined abstractions
This one is a derivative of the previous point, but it’s particularly problematic when it comes to writing software, so I think it’s worth discussing it separately. In order to do resource estimation you’ll have to go through multiple layers of abstractions (e.g.: quantum algorithms, quantum subroutines, arbitrary logical circuit, transpiled logical circuit (e.g.: Clifford+T), error correction codes, logical qubits, physical qubits). Many of these abstraction layers are neither well defined nor is there common software describing them. It’s also not entirely clear what’s the coupling between all of them, as they seem to be distinct on the paper, until you start writing code. And then it turns out that you actually need to exchange information between them, the boundary is fuzzy and as a cherry on the top, there are some feedback loops.
I’ve been working on designing software abstractions for quantum computing for a couple of years now, and every single time getting it right takes months (if not years) from the first prototypes to actually making things run smoothly. Creating software is an iterative process after all, and since some of the ideas really live only in scientific papers or people’s heads, putting them into code properly is really challenging.
Target group
Given how important the topic is and how many parts of the quantum computing stack it spans, it’s no surprise that there are many potential users of such software. Let’s take a look at who they are and why they are interested in it.
Decision makers
This group contains people who need to make strategic decisions about investing their time and money in quantum computing, when they can expect it to be useful and for what type of problems. They might need to decide, for example, “which quantum computing hardware do I invest in?”
- They want reliable numbers, but are not necessarily able to check their correctness – they need to trust the software.
- They care mostly about solving a particular problem – an “application instance”.
- They don’t care what algorithm or particular error correction method has been used.
Application scientists / algorithm researchers
These are people who are researchers, but do not specialize in error correction, compilation or any of these. They want to solve a particular problem or design a new algorithm and they want to make sure that it uses a reasonable amount of resources.
- They want something that’s fast, as they use this tool to get feedback and iterate.
- Tool will be integrated into their current workflow, so it needs to be easy to integrate with.
- They might use the tool as a profiler, so it would need to have good visualization capabilities. While not being an expert, they might be knowledgeable about various tradeoffs present in the system, so they want to be able to play with various parameters much more than the previous group.
As an example, of this type of usage Microsoft recently posted a blog post where Goldman Sachs researchers used their resource estimation tool in this way.
Resource-estimation-related researchers
This is a group whose main interests intersect with how the resource estimation pipeline works 1. They want to see how it works, they want to tinker with it and they want to test their own ideas and see if they improve the performance of the system.
- They don’t want to use the tool to get the final results. They want to use it as a way to improve their own research.
- They are potential contributors to the tool.
- They will try to break the system and prove that it actually doesn’t work as well as you claim it works. In the end they’re scientists at heart, right? ;)
Hardware providers
Hardware providers are also interested in this kind of tools, as it allows them to model how changes in their architecture impact the capacity to solve utility scale problems.
- They need to be able to use sophisticated models of the hardware in conjunction with the resource estimation tools.
- Given how many different hardware modalities are there, they might need a lot of flexibility when it comes to manipulating assumptions. For example, the assumption “a quantum computer is just a huge grid of qubits connected to their nearest neighbors” might not allow certain hardware developers to make progress.
- They might be interested in estimating resources much different than the other users – amount of materials needed to build, amount of power needed for specific components, etc.
Ideal resource estimation software
Given all these, let’s get back to the question – what should be the characteristics of the ideal resource estimation software? To put it differently – if I had a team of 100 people and 5 years to build it, how would I build it?
Modularity
I think such software should be modular as hell! In order to deal with multiple, constantly changing assumptions, you need to have a very modular system. It would be lovely if the modules were all independent software packages which can serve their purpose without relying on other modules, but I think that’s too much to ask, as I don’t think it’s possible to escape some coupling.
Modularity itself is not enough though, it also needs to have well established interfaces, so one can plug-in those modules. This way you can tame the proliferation of the assumptions, as you can always check which assumptions have been used by just inspecting what was the input data and which modules were used for computation.
Future compilation chain
I think that a resource estimation system of today should be the compilation toolchain of tomorrow.
In order to run something on a quantum computer, we will have to compile the “high level algorithm” into some “quantum machine code”. There’s no doubt about that. Machine code would be a source of truth about executing a given program – the only thing that will allow us to have a more precise view of how much resources would the execution take is the execution itself.
So “in the limit”, if we had a resource estimator that work on the machine code level, we could compile everything to the machine code and then we would have perfect resource estimates – beautiful! Even better – such an approach would allow us to take advantage of various hardware-level optimizations, which are not possible when we’re operating on a more abstract level. However, this introduces a whole host of technical difficulties and is definitely not very practical in the short term. It would be overly complex and resource intensive, not to mention that we don’t really even have a good idea of how such machine code would look like2.
Still, I think striving for this is a useful approach, as it forces you to make the resource estimates more realistic.
This approach stands in opposition to what we internally call “footprint analysis” – i.e. an approach where you only count the number of T gates, see how much “footprint” each T gate has (in terms of space and time) and then calculate the resources based on that. I think both approaches have pros and cons, but I believe in the long run the more detailed one will turn out to be more useful.
Well defined abstraction layers
I think that it’s impossible to build a system which is modular and flexible without defining what are the abstraction layers, what are the basic data structures and interfaces and how they interact. Today abstractions all float around the concept of “quantum circuit”, and this is not a good abstraction for multiple reasons (see: my previous post).
We need both better higher level abstractions (quantum programming languages really) and lower level abstractions.
Multiple entrypoints
As mentioned before, different users have different needs and different goals. Therefore, we would need to allow different users to use it differently.
Non-quantum domain experts don’t want to deal with details of specifying quantum algorithms. They want to know how long it will take for a quantum computer to perform simulation of the dynamics of a particular molecule. So they should be able to specify what molecule they care about, what properties and what they want to do with it (e.g.: find ground state, excited state, or just evolve it over time).
Quantum algorithm researchers might want to work at the level of an algorithm, see how costly different pieces of the algorithm are in practice and how to optimize them to get better results.
Compilation researchers might totally not care about the problem they are solving – they just want to know if their particular new compilation technique works well across a wide range of algorithms.
It might be similar for hardware providers – they would care most whether their hardware is modeled accurately in the software and less about the choice of the active spaces that’s used in order to prepare the molecule’s Hamiltonian.
I think it’s also important that such software would have a library of “ready-to-go” components that new users can immediately start experimenting with. Some high-level instances, some algorithms, some hardware models etc.
High quality results.
The numbers that we get at the end of the resource estimation process need to have a couple of qualities.
First, they need to be correct – i.e. we want to make sure that the formulas we’re using to obtain them are correct and that there were no mistakes in how they have been calculated.
Second, we want them to be realistic – it’s great that we have a number which has been calculated correctly. However, if it came from using unrealistic assumptions, it doesn’t really provide much value. And believe me, making sure your assumptions are realistic is by no means simple.
Third, we want them to be optimized – it’s nice that we got some numbers using realistic assumptions. However, realistic assumptions don’t ensure that we have optimized different parts of our system. Perhaps we used an old algorithm for gate synthesis and we have an unnecessarily high T-gate count? Or we didn’t make use of the fact that qubits have all-to-all connectivity and we just assumed nearest neighbors? Well, it’s not “incorrect” to do that, but it leaves a lot of room on the table for getting even lower numbers once you optimize things like this.
Fourth – I want my dream QRE software to produce numbers which have error bars. Error bars are important!
Scalability
At some point the scale of the calculation cannot be done on your laptop, the problem size just gets too big. In such a case, I’d love to be able to seamlessly switch to some distributed computing system that handles all the scaling for me.
I might be biased, but it sounds like a perfect usecase for the Orquestra platform that’s being built at Zapata…
Visualization
I think that the software should have some good way of visualizing the outputs. Different things might be important for different types of users, e.g.:
- Showing how many resources each part of the algorithm uses.
- Plotting multiple problem instances on one chart to see how various resources scale with changing size of the problem or target accuracy.
- I could even imagine visualization for a given hardware model which would show which parts of the hardware has been underutilized, which might hint at where it can be further optimized.
I’m a big believer in good visualization making making huge difference, so I really think this shouldn’t be overlooked!
Hosting
I think that the system like this should be available in at least a couple of flavors – again, this will allow to meet needs of different users.
Standalone library – I think plenty of researchers and developers will prefer to like to play with such tool locally at first. It’s just so much more convenient to test things on your own machine.
Rest API – on the other hand, there are plenty of scenarios, where you might want to have access to an easy to use API. It allows to offload some of the calculations to external server and makes it easy to integrate with certain services.
Web App – I think for the most high-level users a web app with an intuitive interface is something that would fit their needs best. No installation, easy access, no need to see what’s inside.
Open-source
Damn, I just believe in open-source, so if this is my list I’ll just throw it in ;)
But more seriously – obviously various organizations will have different concerns about open-source so it’s not that simple. But apart from all the benefits and challenges associated with OSS, here are some points that are particularly important in this area:
Reliability – the problem is quite complex. Therefore, the transparency and the ability to inspect the code and let the users find potential issues is really important in this case. Especially if your users are world-class experts. Easier to collaborate – if there are 20 people in the world who understand a particular algorithm you’re using (most probably based on one of their old papers in one way or another), then it will be great if you discuss it with them. Much easier with OSS.
Obviously, not all parts of the system make sense to be open-source for every player. For example, the hardware providers might very much not like to make detailed models of their hardware public. However, I still think that an “open-core” model would be the best approach. I believe things such as:
- interfaces
- datastructures
- basic flow
- API
should be open, as they will make it easier for various people to cooperate and integrate with the system, while specific implementations of some of the interfaces can well be closed-source proprietary black boxes.
Well documented
This one’s pretty obvious. Things just need to be well documented and given the complexity it needs to have multiple layers of documentation:
- Very basic “intro to the topic” tutorials
- Code examples for the most common use cases
- Deep scientific dives explaining in details the methods being used
- API docs
- Probably many others I didn’t think about at the moment ;)
Well tested
It goes without saying, but a system like this needs to be well tested. And with different modes of testing – unit tests, end-to-end tests, integration tests, performance tests.
BenchQ
I think it’s not surprising that the reason why I have so many thoughts on the topic is because for more than a year I’ve been developing such software. It’s called BenchQ and we’ve been developing it at Zapata in collaboration with people from University of Technology Sydney, Aalto University, University of Texas at Dallas, Keio University, IonQ and Rigetti Computing. This has been done as a part of the DARPA’s Quantum Benchmarking program.
We tried to get a lot of the points that I listed above right. However, since in real life there are plenty of constraints, it doesn’t fit perfectly into the picture I’ve just painted. If anyone is interested in learning more, please let me know in the comments – I could write a “case-study” blogpost where I show how various design choices we made fit into the framework above.
If you’re interested, please feel free to try it out, as it’s open-source: benchq. It’s still very much in development, not very well documented, so please don’t be too harsh – rather create a GitHub issue or contact the developers3.
Closing notes
I hope that someone managed to get through this wall of text :)
Huge thanks to Peter Johnson, who reviewed this post on an extremely short notice. And who is the most brilliant, most awesome and most handsome PI that this program ever had or ever will have ;) And also to everyone we worked with on in this project, definitely one of the most intense learning experiences in my career so far! Unfortunately that’s too many people to list here.
Have a wonderful day!
Michał
Footnotes: