corrected spellings and improved formatting
Sanchayan Dutta
• 15.5k
• 5
• 39
• 91

These are the steps you'd need to take: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 diomanddiamond NV centercentre, 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. Now you can plot cost (in terms of number of auxiliary qubits needed) of "engineering" the quantum computer.

Now you can plot cost (in terms of number of auxiliary qubits needed) of "engineering"see why you had to come here to ask the quantum computer.question and the answer wasn't in any textbook:

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 dyanmicsdynamics 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' 100x$$100$$x harder than controlling a 10$$10$$-qubit machine, or 100^2$$100^2$$, or 100!$$100!$$ or 100^100$$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 numbernumber of qubits, even for a specific algorithm. So this is still an open question, limited by the difficulty of simulating open quantum system dynamics.

user1271772
• 11.6k
• 1
• 16
• 62

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 diomand NV center, 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 dyanmics 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

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.