<p>The general belief seems to be that the expansion in $\alpha$ is an asymptotic series but not a convergent series. The handwaving estimate is that in $\sum_k c_k \alpha^k$, the scaling for the coefficients is roughly $c_k \sim k!$. So, since $\alpha \simeq 1/137$ the terms will start to get bigger rather than smaller for $k$ larger than around 137. (I assume there is serious literature on this topic, but I'm not too familiar with it. The above is what high energy physicists have told me in casual conversation.)</p>

<p>The fine structure constant itself is not something for which anyone knows a purely theoretical formula. So getting more digits of $\alpha$ is a fundamentally different problem from getting more digits of $\pi$. That being said, the challenges are both experimental and computational. Various experiments in particle accelerators and atomic physics laboratories are dedicated to making progressively more precise measurements of fundamental constants such as $\alpha$. Often, the high-precision theoretical calculation of the factors relating the experimentally observed quantities (such as scattering probabilities or spectral lines) to fundamental constants of interest such as $\alpha$ is very difficult and computationally heavy. The computational side can be just as much a limiting factor as the experimental side in these precision metrology problems. (Some of my coworkers at NIST specialize in this sort of thing.)</p>

<p>In the quantum algorithm that Keith and John and I developed, we do not use a perturbative expansion in powers of the coupling constant. The simulation algorithm is much more directly analogous to an actual experiment. However, one advantage over experiment is that in a simulation we are free to change $\alpha$ to whatever value we want. So, by computing scattering amplitudes at varying $\alpha$ it might be easier to determine the individual coefficients $c_k$ than it is in the real world. However, the study of quantum algorithms for simulating quantum field theories is in its infancy. The extraction of such coefficients is one of the numerous interesting questions that have not really been explored yet! Also, our algorithms don't yet tackle QED but rather some simplified models.</p>

<p>Today, we primarily have two classical algorithms for QFT: Feynman diagrams and lattice simulations. Feynman diagrams break down at strong coupling or high precision, as discussed above. Lattice calculations are mostly only good for computing static quantities such as binding energies (e.g. the mass of the proton), rather than dynamic quantities such as scattering amplitudes. This is because the lattice calculations use imaginary time. (Also, for certain condensed matter systems that are highly frustrated, even finding static quantities such as ground state energies is exponentially hard. It is not clear to me to what extent this phenomenon is relevant to high energy physics.) There is also a current research program on speeding up the computation of scattering amplitudes in supersymmetric quantum field theories. You may have heard about the "amplituhedron", which is part of this. This seems kind of exciting, but it's recent stuff and I don't know too much about it. </p>

<p>So, there is room for exponential speedup by quantum computation in the case that you wish to compute dynamical quantities such as scattering amplitudes with high precision or in a strongly coupled quantum field theory. My papers with Keith and John work out polynomial-time quantum algorithms for computing scattering amplitudes in simple quantum field theories which can be strongly coupled. We would like to extend our algorithms to simulate more complete models such as QED and QCD but we are not there yet. Doing so involves nontrivial challenges, but my feeling is that quantum computers should be able to compute scattering amplitudes in quantum field theories in polynomial time quite generally.</p>

<p>So, that's the perspective based on known classical and quantum algorithms. There is also a perspective from complexity theory. For many classes of physical systems, the problem of computing transition amplitudes to polynomial precision is BQP-complete, and the problem of computing ground energies is QMA-complete. So, for worst case instances we expect quantum computers to compute transition amplitudes in polynomial time, whereas classical computers require exponential time. We expect both quantum and classical computers (as well as nature itself) to require exponential time to find ground states in the worst case. The question is whether the worst case instances of the computational problems look like any real physics. In the context of condensed matter physics, the answer is basically yes, I would say. In the context of high energy physics, one can construct BQP-hard instances of the scattering amplitude problem that correspond at least loosely to something a physicist might need to calculate. (We are currently working on a paper about this.) Whether one can construct QMA-hard instances of the problem of computing a vacuum state for a quantum field theory is something that I have not really thought about. However, I think this could be done if one is willing to allow non-translationally-invariant external fields. </p>

CC BY-SA 3.0
2014-12-24T08:46:45.440Z
Specifically, it looks that a) the k!/137^k heuristic gives hope that the QED computations have (with unlimited computational power) potential to give 30-40 useful digits, and b) It is an interesting question if a quantum computer can efficiently approximate $c_k$ up to (1+epsilon) multiplicative error. The answer can be yes since it is plausible that a quantum computer can efficiently simulate physics with arbitrary alpha.
Gil Kalai
CC BY-SA 3.0
2014-12-23T16:10:27.700Z
2014-12-23T17:01:09.857Z
2014-12-23T17:01:09.857Z
StephenJ
<p>My question is about quantum algorithms for QED (quantum electrodynamics) computations related to the fine structure constants. Such computations (as explained to me) amounts to computing Taylor-like series <span class="math-container">$$\sum c_k\alpha^k,$$</span> where <span class="math-container">$\alpha$</span> is the fine structure constant (around 1/137) and <span class="math-container">$c_k$</span> is the contribution of Feynman diagrams with <span class="math-container">$k$</span>-loops.</p>
<p>This question was motivated by <a href="https://gilkalai.wordpress.com/2014/03/18/why-quantum-computers-cannot-work-the-movie/#comment-16061" rel="noreferrer">Peter Shor's comment</a> (about QED and the fine structure constant) in a discussion regarding quantum computers on my blog. For some background here is a <a href="http://en.wikipedia.org/wiki/Precision_tests_of_QED" rel="noreferrer">relevant Wikipedea article</a>.</p>
<p>It is known that <strong>a)</strong> The first few terms of this computation gives very accurate estimations for relations between experimental outcomes which are with excellent agreement with experiments. <strong>b)</strong> The computations are very heavy and computing more terms is beyond our computational powers. <strong>c)</strong> At some points the computation will explode - in other words, the radius of convergence of this power series is zero.</p>
<p>My question is very simple: Can these computations be carried out efficiently on a quantum computer.</p>
<h3>Question 1</h3>
<blockquote>
<h3>1):  Can we actually efficiently compute (or well-approximate) with a quantum computers the coefficients <span class="math-container">$c_k$</span>.</h3>
<h3>2) (Weaker) Is it  at least feasible to compute the estimates given by QED computation in the regime before  these coefficients explode?</h3>
<h3>3) (Even weaker) Is it  at least feasible to compute the estimates given by these QED computation as long as they are relevant. (Namely for those terms in the series that gives good approximation to the physics.)</h3>
</blockquote>
<p>A similar question applies to QCD computations for computing properties of the proton or neutron. (Aram Harrow made a related comment on my blog on QCD computations, and the comments by Alexander Vlasov are also relevant.)  I would be happy to learn the situation for QCD computations as well.</p>
<p>Following Peter Shor's comment:</p>
<h3>Question 2</h3>
<blockquote>
<h3>Can quantum computation give the answer more accurately than is possible classically because the coefficients explode?</h3>
</blockquote>
<p>In other words</p>
<blockquote>
<h3>Will quantum computers allow to model the situation and to give</h3>
<h3>efficiently approximate answer to the actual physical quantities.</h3>
</blockquote>
<p>Another way <a href="https://gilkalai.wordpress.com/2014/03/18/why-quantum-computers-cannot-work-the-movie/#comment-16071" rel="noreferrer">to ask it</a>:</p>
<blockquote>
<p><strong>Can we compute using quantum computers more and more digits of the
fine structure constant, just like we can compute with a digital
computer more and more digits of e and <span class="math-container">$\pi$</span>?</strong></p>
</blockquote>
<p>(Ohh, I wish I was a believer  :) )</p>
<h3>more background</h3>
<p>The hope that computations in quantum field theory can be carried our efficiently with quantum computers was (perhaps) one of Feynman’s motivation for QC.  Important progress towards quantum algorithms for computations in quantum field theories was achieved in this paper: Stephen Jordan, Keith Lee, and John Preskill  <a href="http://arxiv.org/abs/1111.3633" rel="noreferrer">Quantum Algorithms for Quantum Field Theories</a>. I don't know if the work by Jordan, Lee, and Preskill (or some subsequent work) implies an affirmative answer to my question (at least in its weaker forms).</p>
<h3>A related question on the physics side</h3>
<p>I am curious also if there are  estimations for how many terms in the expansion before we witness explosion. (To put it on more formal ground: Are there estimates for the minimum k for  which <span class="math-container">$\alpha c_k/c_{k+1} &gt; 1/5$</span> (say).) And what is the quality of the approximation we can expect when we use these terms. In other words, how much better results can we expect from this QED computations with an unlimited computation power.</p>
<p>Here are two related questions on the physics sister site. <a href="https://physics.stackexchange.com/questions/155000/qec-and-qed-with-unlimited-computational-power-how-precise-they-are-going-to-b">QED and QCD with unlimited computational power - how precise they are going to be?</a>; <a href="https://physics.stackexchange.com/questions/155002/the-fine-structure-constant-can-it-genuinely-be-a-random-variable">The fine structure constant - can it genuinely be a random variable?</a></p>

CC BY-SA 3.0
2014-12-17T13:21:54.797Z
How about the question: can quantum computation give the answer more accurately than is possible classically because the coefficients explode?
Peter Shor 
CC BY-SA 3.0
2014-12-17T18:44:08.857Z
Sure! lets add this question too!
Gil Kalai
<cc.complexity-theory><quantum-computing><physics>
Quantum algorithms for QED computations related to the fine structure constants
Gil Kalai
# Quantum algorithms for QED computations related to the fine structure constants

(Asked by: username_0 on 2014-12-17)

My question is about quantum algorithms for QED (quantum electrodynamics) computations related to the fine structure constants. Such computations (as explained to me) amounts to computing Taylor-like series $$\sum c\_k\alpha^k,$$ where $\alpha$ is the fine structure constant (around 1/137) and $c\_k$ is the contribution of Feynman diagrams with $k$-loops.

This question was motivated by [Peter Shor's comment](https://gilkalai.wordpress.com/2014/03/18/why-quantum-computers-cannot-work-the-movie/#comment-16061) (about QED and the fine structure constant) in a discussion regarding quantum computers on my blog. For some background here is a [relevant Wikipedea article](http://en.wikipedia.org/wiki/Precision_tests_of_QED).

It is known that **a)** The first few terms of this computation gives very accurate estimations for relations between experimental outcomes which are with excellent agreement with experiments. **b)** The computations are very heavy and computing more terms is beyond our computational powers. **c)** At some points the computation will explode - in other words, the radius of convergence of this power series is zero.

My question is very simple: Can these computations be carried out efficiently on a quantum computer.

### Question 1

> ### 1): Can we actually efficiently compute (or well-approximate) with a quantum computers the coefficients $c\_k$.
>
> ### 2) (Weaker) Is it at least feasible to compute the estimates given by QED computation in the regime before these coefficients explode?
>
> ### 3) (Even weaker) Is it at least feasible to compute the estimates given by these QED computation as long as they are relevant. (Namely for those terms in the series that gives good approximation to the physics.)

A similar question applies to QCD computations for computing properties of the proton or neutron. (Aram Harrow made a related comment on my blog on QCD computations, and the comments by Alexander Vlasov are also relevant.) I would be happy to learn the situation for QCD computations as well.

Following Peter Shor's comment:

### Question 2

> ### Can quantum computation give the answer more accurately than is possible classically because the coefficients explode?

In other words

> ### Will quantum computers allow to model the situation and to give
>
> ### efficiently approximate answer to the actual physical quantities.

Another way [to ask it](https://gilkalai.wordpress.com/2014/03/18/why-quantum-computers-cannot-work-the-movie/#comment-16071):

> **Can we compute using quantum computers more and more digits of the
> fine structure constant, just like we can compute with a digital
> computer more and more digits of e and $\pi$?**

(Ohh, I wish I was a believer :) )

### more background

The hope that computations in quantum field theory can be carried our efficiently with quantum computers was (perhaps) one of Feynman’s motivation for QC. Important progress towards quantum algorithms for computations in quantum field theories was achieved in this paper: Stephen Jordan, Keith Lee, and John Preskill [Quantum Algorithms for Quantum Field Theories](http://arxiv.org/abs/1111.3633). I don't know if the work by Jordan, Lee, and Preskill (or some subsequent work) implies an affirmative answer to my question (at least in its weaker forms).

### A related question on the physics side

I am curious also if there are estimations for how many terms in the expansion before we witness explosion. (To put it on more formal ground: Are there estimates for the minimum k for which $\alpha c\_k/c\_{k+1} > 1/5$ (say).) And what is the quality of the approximation we can expect when we use these terms. In other words, how much better results can we expect from this QED computations with an unlimited computation power.

Here are two related questions on the physics sister site. [QED and QCD with unlimited computational power - how precise they are going to be?](https://physics.stackexchange.com/questions/155000/qec-and-qed-with-unlimited-computational-power-how-precise-they-are-going-to-b); [The fine structure constant - can it genuinely be a random variable?](https://physics.stackexchange.com/questions/155002/the-fine-structure-constant-can-it-genuinely-be-a-random-variable)

**Tags:** cc.complexity-theory, quantum-computing, physics
> **Comments:**
> **username_1**: How about the question: can quantum computation give the answer more accurately than is possible classically because the coefficients explode?  
> **username_0**: Sure! lets add this question too!  

---

## 1 answers

### Answer by username_2 on 2014-12-23. Score: 13 | Accepted answer

The general belief seems to be that the expansion in $\alpha$ is an asymptotic series but not a convergent series. The handwaving estimate is that in $\sum\_k c\_k \alpha^k$, the scaling for the coefficients is roughly $c\_k \sim k!$. So, since $\alpha \simeq 1/137$ the terms will start to get bigger rather than smaller for $k$ larger than around 137. (I assume there is serious literature on this topic, but I'm not too familiar with it. The above is what high energy physicists have told me in casual conversation.)

The fine structure constant itself is not something for which anyone knows a purely theoretical formula. So getting more digits of $\alpha$ is a fundamentally different problem from getting more digits of $\pi$. That being said, the challenges are both experimental and computational. Various experiments in particle accelerators and atomic physics laboratories are dedicated to making progressively more precise measurements of fundamental constants such as $\alpha$. Often, the high-precision theoretical calculation of the factors relating the experimentally observed quantities (such as scattering probabilities or spectral lines) to fundamental constants of interest such as $\alpha$ is very difficult and computationally heavy. The computational side can be just as much a limiting factor as the experimental side in these precision metrology problems. (Some of my coworkers at NIST specialize in this sort of thing.)

In the quantum algorithm that Keith and John and I developed, we do not use a perturbative expansion in powers of the coupling constant. The simulation algorithm is much more directly analogous to an actual experiment. However, one advantage over experiment is that in a simulation we are free to change $\alpha$ to whatever value we want. So, by computing scattering amplitudes at varying $\alpha$ it might be easier to determine the individual coefficients $c\_k$ than it is in the real world. However, the study of quantum algorithms for simulating quantum field theories is in its infancy. The extraction of such coefficients is one of the numerous interesting questions that have not really been explored yet! Also, our algorithms don't yet tackle QED but rather some simplified models.

Today, we primarily have two classical algorithms for QFT: Feynman diagrams and lattice simulations. Feynman diagrams break down at strong coupling or high precision, as discussed above. Lattice calculations are mostly only good for computing static quantities such as binding energies (e.g. the mass of the proton), rather than dynamic quantities such as scattering amplitudes. This is because the lattice calculations use imaginary time. (Also, for certain condensed matter systems that are highly frustrated, even finding static quantities such as ground state energies is exponentially hard. It is not clear to me to what extent this phenomenon is relevant to high energy physics.) There is also a current research program on speeding up the computation of scattering amplitudes in supersymmetric quantum field theories. You may have heard about the "amplituhedron", which is part of this. This seems kind of exciting, but it's recent stuff and I don't know too much about it.

So, there is room for exponential speedup by quantum computation in the case that you wish to compute dynamical quantities such as scattering amplitudes with high precision or in a strongly coupled quantum field theory. My papers with Keith and John work out polynomial-time quantum algorithms for computing scattering amplitudes in simple quantum field theories which can be strongly coupled. We would like to extend our algorithms to simulate more complete models such as QED and QCD but we are not there yet. Doing so involves nontrivial challenges, but my feeling is that quantum computers should be able to compute scattering amplitudes in quantum field theories in polynomial time quite generally.

So, that's the perspective based on known classical and quantum algorithms. There is also a perspective from complexity theory. For many classes of physical systems, the problem of computing transition amplitudes to polynomial precision is BQP-complete, and the problem of computing ground energies is QMA-complete. So, for worst case instances we expect quantum computers to compute transition amplitudes in polynomial time, whereas classical computers require exponential time. We expect both quantum and classical computers (as well as nature itself) to require exponential time to find ground states in the worst case. The question is whether the worst case instances of the computational problems look like any real physics. In the context of condensed matter physics, the answer is basically yes, I would say. In the context of high energy physics, one can construct BQP-hard instances of the scattering amplitude problem that correspond at least loosely to something a physicist might need to calculate. (We are currently working on a paper about this.) Whether one can construct QMA-hard instances of the problem of computing a vacuum state for a quantum field theory is something that I have not really thought about. However, I think this could be done if one is willing to allow non-translationally-invariant external fields.

> **Comments:**
> **username_0**: Specifically, it looks that a) the k!/137^k heuristic gives hope that the QED computations have (with unlimited computational power) potential to give 30-40 useful digits, and b) It is an interesting question if a quantum computer can efficiently approximate $c_k$ up to (1+epsilon) multiplicative error. The answer can be yes since it is plausible that a quantum computer can efficiently simulate physics with arbitrary alpha.  

---

