# Are there any estimates on how complexity of quantum engineering scales with size?

It seems to me that an extremely relevant question for the prospects of quantum computing would be how the engineering complexity of quantum systems scales with size. Meaning, it's easier to build $n$ $1$-qubit computers than one $n$-qubit computer. In my mind, this is roughly analogous to the fact that it's easier to analytically solve $n$ $1$-body problems than one $n$-body problem, since entanglement is the primary motivating factor behind quantum computing in the first place.

My question is the following: It seems that we should really care about how the 'difficulty' of building and controlling an $n$-body quantum system grows with $n$. Fix a gate architecture, or even an algorithm--is there a difficulty in principle arising from the fact that an $n$-qubit computer is a quantum many-body problem? And that mathematically speaking, our understanding of how quantum phenomena scale up into classical phenomena is quite poor? Here difficulty could be defined in any number of ways, and the question we would care about, roughly is, is controlling a $1000$-qubit machine (that is, preserving the coherence of its wavefunctions) 'merely' $100$x harder than controlling a $10$-qubit machine, or $100^2$, or $100!$ or $100^{100}$? Do we have any reasons for believing that it is more or less the former, and not the latter?

• Ha, don't know what my and was supposed to lead to... May 9, 2018 at 17:20
• Hi @KeithRush isn’t there also missing something in the first sentence? Great question by the way. May 9, 2018 at 19:14
• Absolutely not duplicated, but I feel that the answers to the two questions are deeply connected: quantumcomputing.stackexchange.com/questions/1803/… May 10, 2018 at 18:44

This is a question that I have been thinking about for more than 10 years. In 2008 I was a student, and I told my quantum computing professor that I wanted to study the "physical complexity" of performing quantum algorithms for which the "computational complexity" was known to benefit from quantum computation.

For example Grover search requires $\mathcal{O}(\sqrt{n})$ quantum gates as opposed to $\mathcal{O}(n)$ classical gates, but what if the cost of controlling quantum gates scales as $n^4$ while for classical gates it's only $n$?

He instantly replied:

"Surely your idea of physical complexity will be implementation dependent"

That turned out to be true. The "physical complexity" of manipulating $n$ qubits with NMR is much worse than it is for superconducting qubits, but we do not have a formula for the physical difficulty with respect to $n$ for either case.

These are the steps you'd need to take:

1. Come up with an accurate decoherence model for your quantum computer. This will be different for a spin qubit in a GaAs quantum dot, vs a spin qubit in a diamond NV centre, for example.
2. Accurately calculate the dynamics of the qubits in the presence of decoherence.
3. Plot $F$ vs $n$, where $F$ is the fidelity of the $n$ decohered qubits compared to the outcome you'd get without decoherence.
4. This can give you an indication of the error rate (but different algorithms will have different fidelity requirements).
5. Choose an error correcting code. This will tell you how many physical qubits you need for each logical qubit, for an error rate $E$.
6. Now you can plot cost (in terms of number of auxiliary qubits needed) of "engineering" the quantum computer.

Now you can see why you had to come here to ask the question and the answer wasn't in any textbook:

Step 1 depends on the type of implementation (NMR, Photonics, SQUIDS, etc.)
Step 2 is very hard. Decoherence-free dynamics has been simulated without physical approximations for 64 qubits, but non-Markovian, non-perturbative dynamics with decoherence is presently limited to 16 qubits.
Step 4 depends on the algorithm. So there is no "universal scaling" of physical complexity, even if working with a particular type of implementation (like NMR, Photonics, SQUIDs, etc.)
Step 5 depends on the choice of error correcting code

Is controlling a 1000-qubit machine (that is, preserving the coherence of its wavefunctions) 'merely' $100$x harder than controlling a $10$-qubit machine, or $100^2$, or $100!$ or $100^{100}$?

It depends on your choice in Step 1, and no one has been able to go all the way through Step 1 to Step 3 yet to get a precise formula for the physical complexity with respect to the number of qubits, even for a specific algorithm. So this is still an open question, limited by the difficulty of simulating open quantum system dynamics.

Do we have any reasons for believing that it is more or less the former, and not the latter?

The best reason is that this is our experience when we play with IBM's 5-qubit, 16-qubit and 50-qubit quantum computers. The error rates are not going up by $n!$ or $n^{100}$. How does the energy it takes to make the 5-qubit, 16-qubit and 50-qubit quantum computer, and how does that scale with $n$? This "engineering complexity" is even more implementation-dependent (think NMR vs SQUIDs) of an open question, albeit an interesting one.

• How about the easier question of on infinitesimal dynamics? That is for each $n$ and starting state $\rho$ on $(\mathbb{C}^2)^{\otimes n}$, you have the vector field determined by the dynamics evaluated at that point. Calculate it's norm with Fisher metric tensor field. That's a significantly easier question without letting the dynamics flow for finite time, but still gives a bound. If you want, for each $n$ take the supremum over all starting states $\rho$ and plot the result against $n$. May 9, 2018 at 22:10
• What do you mean by "infinitesimal dynamics" ? The vector field is determined by the dynamics evaluated at which point? Calculate the norm of what (using Fisher metric tensor field)? Do you mean calculate the norm of the vector field? It appears to possibly be a good idea, but if it is what I think you mean, which is to look at the decoherence for infinitesimal time at t=0, I don't know how valuable this is as a metric, because it takes time for decoherence to reach its full strength, because decoherence strength is characterized by the bath response function, which is an integral over t. May 9, 2018 at 23:51
• Let $(M_n , g)$ be the Riemannian manifold defined by all states on $n$ qubits equipped with the Fisher metric tensor. An ordinary differential equation defines a vector field on $M_n$. For any state $\rho$ you can see an element in $T_\rho M_n$. You figure out the rate of decoherence from that to get a function $r(\rho)$. If you want supremum over all possible states do gradient ascent. This gives a very coarse bound of the rate of decoherence given the vector field that defined the dynamics. This can be used for bounding the decoherence even at larger times because of that rate bound. May 10, 2018 at 6:26

# Circuit Complexity

I think the first issue is to really understand what is meant by 'controlling' a quantum system. For this, it might help to start thinking about the classical case.

How many different $n$-bit input, 1-bit output classical computations are there? For each of the $2^n$ possible inputs, there are $2$ different possible outputs. Thus, there are $2^{2^n}$ different possible functions that you could be asked to build, if what you're talking about in terms of controllability is "build any of the possible functions". You might then go on to ask "what fraction of these functions can I create by using no more than $2^n/n$ two-bit gates?" (you could presumably generalise this to $k$-bit gates to get a relative complexity argument between two circuit sizes). There's a detailed calculation you can perform to get a good bound on this number, showing that it's small. This is something called Shannon's Theorem (but what isn't?), but there's at least an intuitive explanation: it requires a bit string of $2^n$ bits to specify which possible computation you're wanting to perform. This information must be incompressible, as there's no 'space' to be saved. But, if you could create all of these functions using shorter circuits, then describing that circuit would be a way of compressing the data.

The equivalent statement in quantum computing is "build any $n$-qubit unitary to within some accuracy, $\epsilon$". But the classical answer is already horrific, even before we have to take into account the precision issues of specifying an arbitrary unitary. The point is that with both classical and quantum computations, we focus very specifically on the algorithms that we can implement 'easily', for some definition of 'easily', which is usually that the algorithms that we want to implement scale as some polynomial of the input size (with the possible exception of things like Grover's algorithm). So really the answer to the question depends on the algorithms you wish to run on the computer. If the algorithm scales as $O(n^2)$, then appropriately controlling an 1000-qubit machine is kind of 10000 times harder than controlling a 10-qubit machine, in the sense that you need to protect it from decoherence for that much longer, implement that many more gates etc.

# Decoherence

Let's consider a specific algorithm or a specific kind of circuit. My question could be restated--is there any indication, theoretical or practical, of how the (engineering) problem of preventing decoherence scales as we scale the number of these circuits?

This divides into two regimes. For small scale quantum devices, before error correction, you might say we're in the NISQ regime. This answer is probably most relevant to that regime. However, as your device gets larger, there will be diminishing returns; it gets harder and harder to accomplish the engineering task just to add a few more qubits.

At that point, you have to transition to using error correction and, indeed, fault-tolerance (which is just a form of error correction which is capable of tolerating errors in the gates that implement the correction). Specifically, fault-tolerance says that there exists a threshold error probability $p$ such that, if you can perform every gate with an error probability $\leq p$, you can define some logical qubits (made up of multiple physical qubits) such that the result of any computation or arbitrary length can be accomplished with arbitrary precision. Whatever your physical hardware, by the time you've left the NISQ regime, you've done a lot of work eliminating decoherence as much as possible, and made sure you're as far below the $p$ threshold as possible. Current estimates place $p$ somewhere around the $1\%$ mark. The question becomes "what are the overheads for these fault-tolerant processes". The precise details are scheme dependent, and much work continues into how to minimise these costs. The scaling argument, however, says that for each logical qubit, you require $O(-\log\epsilon)$ physical qubits to achieve an overall accuracy of $\epsilon$. There is also a time cost; most of your time is spent performing error correction rather than the logical gates. Again, this is an $O(-\log\epsilon)$ scale factor. For specific numbers, you might be interested in the sorts of calculations that Andrew Steane has performed: see here (although the numbers could probably be improved a bit now).

What is really quite compelling is to see how the coefficients in these relations change as your gate error gets closer and closer to the error correcting threshold. I can't seem to lay my hands on a suitable calculation (I'm sure Andrew Steane did one at some point. Possibly it was a talk I went to.), but they blow up really badly, so you want to be operating with a decent margin below the threshold.

That said, there are a few assumptions that have to be made about your architecture before these considerations are relevant. For example, there has to be sufficient parallelism; you have to be able to act on different parts of the computer simultaneously. If you only do one thing at a time, errors will always build up too quickly. You also want to be able to scale up your manufacturing process without things getting any worse. It seems that, for example, superconducting qubits will be quite good for this. Their performance mainly depends on how accurately you can make different parts of the circuit. You get it right for one, and you can "just" repeat many times to make many qubits.

• This is essentially what I meant, but removing the algorithmic complexity, and focusing on complexity of the engineering--especially preventing decoherence. Let's consider a specific algorithm or a specific kind of circuit. My question could be restated--is there any indication, theoretical or practical, of how the (engineering) problem of preventing decoherence scales as we scale the number of these circuits? May 9, 2018 at 18:53
• @KeithRush OK! Now I start to understand what you’re after :) in essence, this is the computational complexity of fault tolerance - what are the time and space overheads to get a certain number of high quality logical qubits - and is something that people have worked out quite carefully. I’ll try to dig out the relevant information tomorrow, unless someone else beats me to it. May 9, 2018 at 19:10

One way to think about quantum systems, which is qubits with error correction, and an encoded algorithm built in, or even in the general case where we program an algorithm is to ensure the fidelity of a qubit. So, for a system of $m$ qubits, we could could use proper error correction - for a given system of qubits, whether they are ion trap, superconducting, or any other scheme, and say the "fidelity" of a system given all these parameters is $n$ qubits.

So in a sense, the "fidelity" could give an estimate, how error prone the processor is. If you used the quantum computer to compute say chemical reaction dynamics, or any other problem, that could use superposition to achieve quantum speedup (or even "quantum supremacy" eventually) you could be impacted by decoherence, or even how quickly you achieve a superposition, could play a part in error free operation. "Fidelity" could give an error estimation, whether we use 1 qubit, or say 200 qubits. You could even "engineer" a Hamiltonian, to give high fidelity qubits, in the adiabatic case, where leakage errors, take place.

Note that in practice, error rates of 99.5%+ are highly desirable, to facilitate efficient error correction. Error rates could be of the type of reading electron spins between qubits to accuracy. In such a case, error rates, of 99.5%, or 99.8%(five or six sigma type confidence) would require less overheads(error correction) when scaling the system.