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?

  • $\begingroup$ Ha, don't know what my and was supposed to lead to... $\endgroup$ – Keith Rush May 9 '18 at 17:20
  • $\begingroup$ Hi @KeithRush isn’t there also missing something in the first sentence? Great question by the way. $\endgroup$ – MEE the setup wizard May 9 '18 at 19:14
  • $\begingroup$ Absolutely not duplicated, but I feel that the answers to the two questions are deeply connected: quantumcomputing.stackexchange.com/questions/1803/… $\endgroup$ – agaitaarino May 10 '18 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

So, to answer your two questions specifically:

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.

  • 1
    $\begingroup$ 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$. $\endgroup$ – AHusain May 9 '18 at 22:10
  • 1
    $\begingroup$ 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. $\endgroup$ – user1271772 May 9 '18 at 23:51
  • 1
    $\begingroup$ 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. $\endgroup$ – AHusain May 10 '18 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.


Following up on the comments,

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.

  • 1
    $\begingroup$ 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? $\endgroup$ – Keith Rush May 9 '18 at 18:53
  • $\begingroup$ @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. $\endgroup$ – DaftWullie May 9 '18 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.

  • $\begingroup$ What does "error rate of 99.5+" mean? Is that a percentage? If yes, please add the percentage symbol ($\%$) using MathJax. $\endgroup$ – Sanchayan Dutta May 9 '18 at 22:49

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

My question is the following: It seems that we should really care about how the 'difficulty' of building and controlling a $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?

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' 100x harder than controlling a 10-qubit machine, or $100^2$, or $100!$ or $100^{100}$?

The paper "Measures of macroscopicity for quantum spin systems" 21 Sept 2012, by Fröwis and Dür, has a useful introduction explaining one viewpoint of the complexity of this:

"1. Introduction

Quantum mechanics is probably the most successful and fascinating physical theory of the last century. In the first place, it provides a deep understanding of atoms and their interaction with light. In recent years, the prospects of improved technologies have been intensively investigated. This success comes with the price of a difficult interpretation of the theory, which was intensively discussed from a philosophical point of view. As long as we consider only microscopic systems on the scale of an atomic radius, objections to quantum mechanics are nevertheless rare, mainly because of the overwhelming experimental evidence. When it comes to macroscopic systems, many things are not clear anymore. Already in 1935, Schrödinger pointed out in his seminal paper$^{[1]}$ that quantum mechanics in principle allows superpositions of macroscopic states, like a cat that is alive and dead at the same time. This gedanken experiment is deeply connected with the so-called quantum measurement problem and was discussed by generations of physicists.

Besides the interest in the foundations of quantum mechanics, the question of macroscopic quantum mechanics also has practical aspects. Proposed architectures for quantum computers are based on a large number of qubits. Computational tasks that can overcome classical algorithms may require long-range quantum correlations$^{[2, 3]}$. A further application, quantum metrology, uses a certain kind of multipartite entanglement among many particles for an increased sensitivity in phase estimation protocols$^{[4]}$.

In 1980, Leggett$^{[5]}$ gave an important impulse to the topic of macroscopic quantum mechanics. He asked for a clear definition of the phrases 'macroscopic quantum phenomenon' and 'macroscopic superposition'. He realized that one should distinguish between quantum effects that originate on a microscopic level from 'true' macroscopic quantum effects. Among other examples, he highlights the specific heat of insulators. Classical statistical mechanics predicts a specific heat that is constant with respect to the temperature T. On the other hand, the quantum mechanical Debye model correctly predicts T3 behaviour for small temperatures. Many physicists considered this as an example of a macroscopic quantum phenomenon, since this law is valid even for large insulators. Leggett argued that the phrase macroscopic in this context is not justified, because the interactions that cause this effect are on an atomic scale and thus microscopic. In the following, he demanded a distinction between classical and microscopic quantum effects on the one hand, and macroscopic quantum effects on the other hand. Only the latter allow us to verify quantum mechanics (against classical theories) on a macroscopic scale, as in the example of Schrödinger's cat.

Consequently, we call quantum states that are capable of inducing macroscopic quantum effects the 'macroscopic quantum states'. The question at issue is: which properties of a many-body quantum state are appropriate for such a characterization? It is clear that the number of particles is an important but not sufficient criterion. If we consider superpositions of semi-classical quantum states, it seems to be crucial that they be 'macroscopically distinct', as Leggett$^{[5]}$ phrased it. However, a straightforward mathematical formulation of this intuitive characterization does not exist. Furthermore, there may be quantum states that do not exhibit a superposition of two semi-classical states but are superpositions of a large number of those. These and further concerns led to various proposals of macroscopic quantum states$^{[5–12]}$.

The goal of this work is twofold. Firstly, we motivate and introduce another aspect of macroscopic quantum effects in discrete systems. After basic considerations in section 2, we propose to use the so-called quantum Fisher information as a measure of 'macroscopicity'." ...

References for above:


[1] Schrödinger E 1935 Naturwissenschaften 23 807

[2] Jozsa R and Linden N 2003 Phil. Trans. R. Soc. A 459 2011–32

[3] Datta A and Vidal G 2007 Phys. Rev. A 75 042310

[4] Pezzé L and Smerzi A 2009 Phys. Rev. Lett. 102 100401

[5] Leggett A J 1980 Prog. Theor. Phys. Suppl. 69 80

[6] Dür W, Simon C and Cirac J I 2002 Phys. Rev. Lett. 89 210402

[7] Shimizu A and Miyadera T 2002 Phys. Rev. Lett. 89 270403

[8] Björk G and Mana P G L 2004 J. Opt. B: Quantum Semiclass. Opt. 6 429–36

[9] Shimizu A and Morimae T 2005 Phys. Rev. Lett. 95 090401

[10] Korsbakken J I, Whaley K B, Dubois J and Cirac J I 2007 Phys. Rev. A 75 042106

[11] Marquardt F, Abel B and von Delft J 2008 Phys. Rev. A 78 012109

[12] Lee C and Jeong H 2011 Phys. Rev. Lett. 106 220401

Another metric put forth to measure complexity is the Greenberger–Horne–Zeilinger state but Fröwis and Dür explain why they favor Fisher.

GHZ is explained as:

"The GHZ state is an entangled quantum state of $M \gt 2$ subsystems. In the case of each of the subsystems being two-dimensional, that is for qubits, it reads:

$${\displaystyle |\mathrm {GHZ}}\rangle ={\frac {|0\rangle ^{{\otimes M}}+|1\rangle ^{{\otimes M}}}{{\sqrt {2}}}}.$$

In simple words, it is a quantum superposition of all subsystems being in state 0 with all of them being in state 1 (states 0 and 1 of a single subsystem are fully distinguishable).

The simplest one is the 3-qubit GHZ state:

$${\displaystyle |\mathrm {GHZ}}\rangle ={\frac {|000\rangle +|111\rangle }{{\sqrt {2}}}}.$$

This state is non-biseparable$^{[1]}$ and is the representative of one of the two non-biseparable classes of 3-qubit states (the other being the W state), which cannot be transformed (not even probabilistically) into each other by local quantum operations.$^{[2]}$ Thus $|\mathrm {GHZ} \rangle$ and $|W\rangle$ represent two very different kinds of tripartite entanglement. The W state is, in a certain sense "less entangled" than the GHZ state; however, that entanglement is, in a sense, more robust against single-particle measurements, in that, for an N-qubit W state, an entangled (N − 1)-qubit state remains after a single-particle measurement. By contrast, certain measurements on the GHZ state collapse it into a mixture or a pure state.".


[1]. A pure state $| \psi \rangle$ of $\text{N}$ parties is called biseparable, if one can find a partition of the parties in two disjoint subsets $\text{A}$ and $\text{B}$ with $A\cup B=\{1,\dots ,N\}$ such that $|\psi \rangle =|\phi \rangle _{A}\otimes |\gamma \rangle _{B}$, i.e. $|\psi \rangle$ is a product state with respect to the partition $A|B$.

[2]. W. Dür; G. Vidal & J. I. Cirac (2000). "Three qubits can be entangled in two inequivalent ways". Phys. Rev. A. 62: 062314. arXiv:quant-ph/0005115 🔓. Bibcode:2000PhRvA..62f2314D. doi:10.1103/PhysRevA.62.062314.

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

My own favorite would be the hyperoperation called tetration or in Rudy Rucker notation $^{n}a$.

Tetration is defined as:

$$T(a, b) = {}^ba = \underbrace{a^{a^{a^{…^{a}}}}}_{b \> times}$$

A single qubit we will call easy for the sake of comparison, adding another qubit, not as another single qubit but as a fully operational pair, increases the complexity beyond $2^2$. There's the building, maintenance, maintaining of state, programming and measurement complexity; which are all increased for each additional universal qubit.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.