Connect with us


Our final year report for the first phase of the programme is now published!





How to Solve Equations That Are Stubborn as a Goat




If you’ve ever taken a math test, you’ve probably met a grazing goat. Usually it’s tied to a fence post or the side of some barn, left there by an absent-minded farmer to graze on whatever grass it can reach. When you meet a grazing goat, your job is to calculate the total area of the region it can graze on. It’s a math test, after all.

Math teachers have stymied students by sticking goats in strangely shaped fields for hundreds of years, but one particular grazing goat problem has gotten the goat of mathematicians for more than a century. Until last year they were only able to find approximate answers to the problem, and it took a new approach with some very advanced mathematics to finally produce an exact solution. Let’s take a look at how a question you might find on a math test can turn into a problem that stumps mathematicians for over a century.

The simplest kind of grazing goat problem has the hungry animal attached to the side of a long barn by a fixed length of rope.

Usually in these problems we want to find the area of the region the goat has access to. What does that region look like?

With the leash pulled taut the goat can make a semicircle and can reach anything inside it. The area of a circle is Aπr2, so the area of a semicircle is A = $latex frac{1}{2}$πr2. If, for example, the rope has length 4, then the goat could graze in a region with area A = $latex frac{1}{2}$π × 42 = 8π square units.

This straightforward setup doesn’t pose much of a challenge to the math student or to the goat, so let’s make it more interesting. What if the goat is tied to the side of a square barn?

Let’s say the rope and the side of the barn both have length 4, and that the rope is attached to the middle of one side. What’s the area of the region the goat has access to now?

Well, the goat still has access to the same semicircle as in the first problem.

But the goat can also continue around the corner of the barn. Once it’s at the corner, the goat has two more units of rope to work with, so it can sweep out another quarter circle of radius 2 on either side of the barn.

The goat can access the semicircle of radius 4 plus two quarter circles of radius 2, for a total area of A = $latex frac{1}{2}$π × 42 + $latex frac{1}{4}$π × 22 + $latex frac{1}{4}$π × 22 = 10π square units.

You can make the problem more challenging by changing the shape of the obstruction. I’ve seen goats attached to triangles, hexagons and even concave shapes.

You can also make a new math question from an old one by reversing it: Instead of starting with rope length and finding the area, you can start with the area and find the rope length.

For example, let’s stick with our square barn and ask a new question: How long would the rope have to be for the goat to have access to a total of 50 square units of area? Reversing a math problem can breathe new life into an old idea, but it also makes this problem much more challenging.

First, notice that the shape of the region depends on the length of the rope. For example, if the rope is shorter than 2 units in length, the goat can’t get around the corner of the barn, so the region will only be a semicircle.

If the rope is longer than 2 units, the goat can get around the corner, as we saw above.

And if the rope is longer than 6 units, the goat can get behind the barn, creating another set of quarter circles to consider. (If the rope gets much longer, there will be overlap. See the exercises at the end of the column for an example of this.)

We want to find the rope length that gives us 50 square units of total area. The way to do this mathematically is to set our area formula equal to 50 and solve for r. But each kind of region has a different area formula. Which one do we use?

Figuring this out requires a little casework. If r ≤ 2 the area of the region is A = $latex frac{1}{2}$πr2. The biggest area would occur when r = 2, which yields a total area of A = $latex frac{1}{2}$π × 22 = 2π ≈ 6.28. This is less than 50, so we know we need more than 2 units of rope.

If 2 < r ≤ 6, this gives us the semicircle plus the two quarter circles we encountered before. The radius of the semicircle is r, and the radius of the quarter circles is r – 2, since two units of rope are needed to get to the corner and whatever rope remains acts like the radius of the quarter circle centered at the corner.

The area of this semicircle is $latex frac{1}{2}$πr2, and the area of each quarter circle is $latex frac{1}{4}$π(r – 2)2. Adding this up gives us a total area of

$latex begin{aligned}A&=frac{1}{2} pi r^{2} +frac{1}{4}pi (r-2)^{2} + frac{1}{4}pi (r-2)^{2}\[1pt]
\A &=frac{1}{2} pi r^{2} + frac{1}{2}pi (r-2)^{2}.end{aligned}$

We get the biggest possible area when r = 6, which gives an area of A = $latex frac{1}{2}$π × 62 + $latex frac{1}{2}$π × 42 = 26π ≈ 81.68 square units. Since 50 < 26π, that means the r that will give us 50 square units of area must be less than 6.

Knowing that r must be between 2 and 6 units settles the question of which area formula we should use: When 2 < r ≤ 6, the area is A = $latex frac{1}{2}$πr2 + $latex frac{1}{2}$π(r – 2)2. To find the exact value of r that gives us 50 square units of area, we set up this equation:

50 = $latex frac{1}{2}$πr2 + $latex frac{1}{2}$π(r – 2)2.

Notice that this is another way in which our reversed question is more complicated than the original: Instead of just computing the area the goat can reach, we need to solve an equation to figure out the length of the rope. To do that, we need to isolate r. We have to use arithmetic and algebra to get r by itself on one side of the equation, and that will tell us exactly what r must be.

Our equation may look a little intimidating at first, but it’s just a quadratic equation in r. There’s a standard procedure for solving such equations: We rearrange it in the form ar2 + br + c = 0 and then use the quadratic formula. A little algebra and arithmetic does the trick.

50 = $latex frac{1}{2}$π2 + $latex frac{1}{2}$π(r – 2)2

$latex frac{100}{pi}$ = r2 + (r – 2)2

$latex frac{100}{pi}$ = 2r2 – 4r + 4

0 = 2r2 – 4r + 4 – $latex frac{100}{pi}$.

This may not be the most beautiful mathematical expression in the world, but it’s just a quadratic equation, so we can apply the quadratic formula to solve exactly for r. This gives us an answer of

r = 1 + $latexsqrt{frac{50}{pi} – 1}$ ≈ 4.86.

Because we were able to isolate r in our equation, we now know exactly how long the rope must be to get an area of 50 square units. (Notice that the value of r we found is between 2 and 6, as expected.)

As challenging as this reversed goat grazing problem was compared to the initial ones we looked at, mathematicians discovered that the problem becomes even more challenging when you stick the goat inside the barn. So challenging, in fact, that they couldn’t solve it exactly.

Let’s put the goat inside our square barn with side length 4 and attach the rope to the middle of a wall. How long does the rope need to be for the goat to have access to half the area inside the barn?

As above, part of the challenge is that the shape of the region depends on the value of r. To get half the area of the square we need r to be longer than half the side of the barn but shorter than the full side, which gives us a region like this.

Finding a formula for the area of this region isn’t so easy. We can imagine the region as one sector of a circle of radius r plus two right triangles, and then use some high school geometry to get a formula. But as we’ll soon see, the mixing of circles and triangles is going to cause some trouble.

Let’s start with the triangles. The Pythagorean theorem tells us that the length of the missing leg in each right triangle is $latexsqrt{r^{2}-4}$. This makes the area of one of the triangles $latex frac{1}{2}$ × 2 × $latexsqrt{r^{2} – 4}$ = $latexsqrt{r^{2} – 4}$, so the two triangles together have an area of 2 $latexsqrt{r^{2}-4}$.

Now for the circular sector.

The area of a sector is A = $latexfrac{1}{2}r^{2}$θ, where θ is the measure of the central angle (in radians, not degrees). We need a formula for the area in terms of r, so we need to express the angle θ in terms of r. To do this, we’ll use the law of cosines, an underappreciated theorem from high school trigonometry.

Applying the law of cosines to the isosceles triangle with sides r, r and 4 gives us

42 = r2 + r2 – 2r2cosθ,

which we can solve for cosθ:

cosθ = $latex frac{2 r^{2}-16}{2 r^{2}}$ = $latex frac{r^{2}-8}{r^{2}}$.

To isolate θ, we need to take the inverse cosine, or arccosine, of both sides of the equation. This gives us

θ = arccos $latex left(frac{r^{2}-8}{r^{2}}right)$.

Now we have the angle θ in terms of r, so we can now express the area of our sector in terms of r and r alone.

A = $latex frac{1}{2}$r2θ

A = $latex frac{1}{2}$r2arccos $latex left(frac{r^{2}-8}{r^{2}}right)$.

Our final area formula is the sum of the sector area and the area of the two triangles, which is

A = $latex frac{1}{2}$r2arccos $latex left(frac{r^{2}-8}{r^{2}}right)$ + 2 $latexsqrt{r^{2}-4}$.

We now have a formula for the area of the region accessible to the goat inside the square entirely in terms of r. Now we just need to find the value of r that gives the goat access to half the square. The entire square has area 16, so all we have to do is plug A = 8 into our equation and solve for r and we’ll be finished.

8 = $latex frac{1}{2}$r2arccos $latex left(frac{r^{2}-8}{r^{2}}right)$ + 2 $latexsqrt{r^{2}-4}$.

There’s just one small problem: It’s not possible to solve for r in this equation.

That is, it’s not possible to solve exactly for r in this equation. We can use a calculator to approximate the value of r that makes this equation true (r ≈ 2.331), but we can’t isolate rin our equation. The mixing of trigonometric functions and polynomial functions in our equation creates obstacles we can’t get around.

We could try to get the r’s out from inside the arccosine function, but to do that we’d have to put the other r’s inside a cosine function. Either way we’d be dealing with an equation that involves a transcendental function, like an exponential or trigonometric function. Transcendental functions can’t be simply expressed in terms of the usual algebraic operations like addition and multiplication, and so in general transcendental equations can’t be solved exactly.

This issue lies at the heart of a famous grazing goat problem posed in the 19th century where the goat was placed inside a circular barn. As in our square barn problem, the goal was to determine how long the rope had to be for the goat to have access to half the region.

The region accessible by the goat takes the shape of a “lens” — two circular segments stacked together.

It’s possible to use high school geometry to find the area of this lens in terms of the rope length r, but the formula is much more complicated than it is for the square. And when you set this equal to half the area of the circular barn, you run into the same problem we ran into inside the square: You just can’t isolate r. You can approximate it, but you can’t solve for r exactly.

This sort of obstinacy is no more appealing in an equation than it is in a goat. For over 100 years, mathematicians tried to find an exact solution to this goat-in-a-circle puzzle, but it wasn’t until last year that a German mathematician finally figured it out. He used complex analysis — mathematics far removed from the geometry of circles and squares most goat problems rely on — to solve explicitly for . And while using something as advanced as a contour integral to find the length of a goat’s leash may seem like overkill, there’s always mathematical satisfaction in doing what couldn’t be done before. And there’s always the possibility that these new methods, even if they arise from studying a silly problem about goats, might lead to insights beyond the barnyard.


1. If the goat is attached to the middle of the side of a square barn with side length 4 by a rope of length 8, outside the barn, what’s the area of the region the goat has access to?

2. If the goat is attached to the corner of a square barn with side length 4 by a rope of length 8, outside the barn, what’s the area of the region the goat has access to?

3. Suppose the goat is inside an equilateral triangle of side 4 attached to a vertex. How long would the rope have to be for the goat to have access to half the triangle?

4. If the goat is attached to the middle of the side of a square barn with side length 4 by a rope of length 10, outside the barn, what’s the area of the region the goat has access to?


Click for Answer 1:

The region is comprised of a semicircle of radius 8, two quarter circles of radius 6, and two quarter circles of radius 2. Since 8 is equal to half the perimeter of the barn, the two semicircles behind the barn meet up at the midpoint.

The area of this region is $latexfrac{1}{2}$π × 82 + $latexfrac{1}{2}$π × 62 + $latexfrac{1}{2}$π × 22 = 52π.

Click for Answer 2:

This region is comprised of three-quarters of a circle of radius 8 and two quarter circles of radius 4.

This area is $latexfrac{3}{4}$π × 82 + $latexfrac{1}{2}$π × 42 = 56π. As a challenge, think about what happens if the rope has length 10.

Click for Answer 3:

Since the angles of an equilateral triangle are 60 degrees, the region the goat has access to is one-sixth of a circle of radius r, which has area $latexfrac{1}{6}$πr2.

The area of an equilateral triangle is $latexfrac{sqrt{3}}{4}$s2, so the area of the triangle of side length 4 is $latexfrac{sqrt{3}}{4}$ × 42 = 4 $latex{sqrt{3}}$. We set the two areas equal, $latexfrac{1}{6}$πr2 = $latexfrac{1}{2}$ × 4 $latex{sqrt{3}}$, and solve for r to get r = $latexsqrt{frac{12 sqrt{3}}{pi}}$. Notice how we can solve exactly for r here, unlike when the region mixed circular sectors and triangles.

Click for Answer 4:

The region is apparently comprised of a semicircle of radius 10, two quarter circles of radius 8, and two quarter circles of radius 4. This has an area of $latexfrac{1}{2}$π × 102 + $latexfrac{1}{2}$π × 82 + $latexfrac{1}{2}$π × 42 = 90π. But the last two quarter circles overlap behind the barn.

That overlap has been counted twice, so we need to subtract that overlapping area from 90π. The overlapping area can be thought of as two sixths of circles of radius 4 minus an equilateral triangle of side 4. The area of this region comes to 2 ×
$latexfrac{1}{6}$π × 42 – $latexfrac{sqrt{3}}{4}$ × 42 = $latexfrac{16}{3}$π – 4 $latex{sqrt{3}}$. So the total area is 90π – $latexleft(frac{16}{3} pi-4 sqrt{3}right)$ = $latexfrac{254}{3}$π + 4 $latex{sqrt{3}}$. (Note: This overlap would be much more difficult to find if the two circles had different radii, which is why finding the area of the lens mentioned above is so difficult.)

Coinsmart. Beste Bitcoin-Börse in Europa

Continue Reading


Quantum Double-Slit Experiment Offers Hope for Earth-Size Telescope




Imagine being able to see the surface of an Earth-like planet orbiting another star, or watching a star get shredded by a black hole.

Such precise observations are currently impossible. But scientists are proposing ways to quantum mechanically link up optical telescopes around the world in order to view the cosmos at a mind-boggling level of detail.

The trick is to transport fragile photons between telescopes, so that the signals can be combined, or “interfered,” to create far sharper images. Researchers have known for years that this kind of interferometry would be possible with a futuristic network of teleportation devices called a quantum internet. But whereas the quantum internet is a far-off dream, a new proposal lays out a scheme for doing optical interferometry with quantum storage devices that are under development now.

The approach would represent the next stage of astronomy’s obsession with size. Wider mirrors create sharper images, so astronomers are constantly designing ever-bigger telescopes and seeing more details of the cosmos unfold. Today they’re building an optical telescope with a mirror nearly 40 meters wide, 16 times the width (and thus resolution) of the Hubble Space Telescope. But there’s a limit to how much mirrors can grow.

“We’re not going to be building a 100-meter single-aperture telescope. That’s insane!” said Lisa Prato, an astronomer at Lowell Observatory in Arizona. “So what’s the future? The future’s interferometry.”

Earth-Size Telescope

Radio astronomers have been doing interferometry for decades. The first-ever picture of a black hole, released in 2019, was made by synchronizing signals that arrived at eight radio telescopes dotted around the world. Collectively, the telescopes had the resolving power of a single mirror as wide as the distance between them — an effectively Earth-size telescope.

To make the picture, radio waves arriving at each telescope were precisely time-stamped and stored, and the data was then stitched together later on. The procedure is relatively easy in radio astronomy, both because radio-emitting objects tend to be extremely bright, and because radio waves are relatively large and thus easy to line up.

Optical interferometry is much harder. Visible wavelengths measure hundreds of nanometers long, leaving far less room for error in aligning waves according to when they arrived at different telescopes. Moreover, optical telescopes build images photon-by-photon from very dim sources. It’s impossible to save these grainy signals onto normal hard drives without losing information that’s vital for doing interferometry.

Astronomers have managed by directly linking nearby optical telescopes with optical fibers — an approach that led in 2019 to the first direct observation of an exoplanet. But connecting telescopes farther apart than 1 kilometer or so is “extremely unwieldly and expensive,” said Theo ten Brummelaar, director of the CHARA Array, an optical interferometric array in California. “If there was a way of recording photon events at an optical telescope with some kind of quantum device, that would be a great boon to the science.”

Young’s Slits

Joss Bland-Hawthorn and John Bartholomew of the University of Sydney and Matthew Sellars of the Australian National University recently proposed a scheme for doing optical interferometry with quantum hard drives.

The principle behind the new proposal traces back to the early 1800s, before the quantum revolution, when Thomas Young devised an experiment to test whether light is made of particles or waves. Young passed light through two closely separated slits and saw a pattern of regular bright bands form on a screen behind. This interference pattern, he argued, appeared because light waves from each slit cancel out and add together at different locations.

Then things got a whole lot weirder. Quantum physicists discovered that the double-slit interference pattern remains even if photons are sent toward the slits one at a time; dot by dot, they gradually create the same bands of light and dark on the screen. However, if anyone monitors which slit each photon goes through, the interference pattern disappears. Particles are only wavelike when undisturbed.

Now imagine that, instead of two slits, you have two telescopes. When a single photon from the cosmos arrives on Earth, it could hit either telescope. Until you measure this — as with Young’s double slits — the photon is a wave that enters both.

Bland-Hawthorn, Bartholomew and Sellars suggest plugging in a quantum hard drive at each telescope that can record and store the wavelike states of incoming photons without disturbing them. After a while, you transport the hard drives to a single location, where you interfere the signals to create an incredibly high-resolution image.

Quantum Memory

To make this work, quantum hard drives have to store lots of information over long periods of time. One turning point came in 2015, when Bartholomew, Sellars and colleagues designed a memory device made from europium nuclei embedded in a crystal that could store fragile quantum states for six hours, with the potential to extend this to days.

Then, earlier this year, a team from the University of Science and Technology of China in Hefei demonstrated that you could save photon data into similar devices and later read it out.

“It’s very exciting and surprising to see that quantum information techniques can be useful for astronomy,” said Zong-Quan Zhou, who co-authored the recently published paper. Zhou describes a world in which high-speed trains or helicopters rapidly shuttle quantum hard drives between far-apart telescopes. But whether these devices can work outside laboratories remains to be seen.

Bartholomew is confident that the hard drives can be shielded from errant electric and magnetic fields that disrupt quantum states. But they’ll also have to withstand pressure changes and acceleration. And the researchers are working to design hard drives that can store photons with many different wavelengths — a necessity for capturing images of the cosmos.

Not everyone thinks it’ll work. “In the long run, if these techniques are to become practical, they will require a quantum network,” said Mikhail Lukin, a quantum optics specialist at Harvard University. Rather than physically transporting quantum hard drives, Lukin has proposed a scheme that would rely on a quantum internet — a network of devices called quantum repeaters that teleport photons between locations without disturbing their states.

Bartholomew counters that “we have good reasons to be optimistic” about quantum hard drives. “I think in a five-to-10-year time frame you could see tentative experiments where you actually start looking at real [astronomical] sources.” By contrast, the construction of a quantum internet, Bland-Hawthorn said, is “decades from reality.”

Coinsmart. Beste Bitcoin-Börse in Europa

Continue Reading


How Gravity Is a Double Copy of Other Forces




As far as physicists have been able to determine, nature speaks two mutually unintelligible languages: one for gravity and one for everything else. Curves in the fabric of space-time tell planets and people which way to fall, while all the other forces spring from quantum particles.

Albert Einstein first spoke of gravity in terms of bends in space-time in his general theory of relativity. Most theorists assume that gravity actually pushes us around through particles, called gravitons, but attempts to rewrite Einstein’s theory using quantum rules have generally produced nonsense. The rift between the forces runs deep, and a full unification of the two grammars seems remote.

In recent years, however, a baffling translation tool known as the “double copy” has proved surprisingly adept at turning certain gravitational entities, such as gravitons and black holes, into dramatically simpler quantum equivalents.

“There’s a schism in our picture of the world, and this is bridging that gap,” said Leron Borsten, a physicist at the Dublin Institute for Advanced Studies.

While this unproven mathematical relationship between gravity and the quantum forces has no clear physical interpretation, it’s allowing physicists to pull off nearly impossible gravitational calculations and hints at a common foundation underlying all the forces.

John Joseph Carrasco, a physicist at Northwestern University, said anyone who spends time with the double copy comes away believing “that it’s rooted in a different way of understanding gravity.”

Gravity Versus the Rest

On one side of the fundamental physics divide stand the electromagnetic force, the weak force and the strong force. Each of these forces comes with its own particle carrier (or carriers) and some quality that the particle responds to. Electromagnetism, for instance, uses photons to push around particles that possess charge, while the strong force is conveyed by gluons that act on particles with a property called color.

Physicists can describe any event involving these forces as a sequence of particles scattering off each other. The event might start with two particles approaching each other, and end with two particles flying away. There are, in principle, infinitely many interactions that can happen in between. But theorists have learned how to make frighteningly accurate predictions by prioritizing the simplest, most likely sequences.

On the other side of the divide stands gravity, which rebels against this kind of treatment.

Gravitons react to themselves, generating looping, Escher-like equations. They also proliferate with a promiscuity that would make a bunny blush. When gravitons mingle, any number of them can emerge, complicating the prioritization scheme used for other forces. Just writing down the formulas for simple gravitational affairs is a slog.

But the double copy procedure serves as an apparent back door.

Zvi Bern and Lance Dixon, later joined by Carrasco and Henrik Johansson, developed the procedure in the 2000s, advancing older work in string theory, a candidate quantum theory of gravity. In string theory, O-shaped loops representing gravitons act like pairs of S-shaped strings corresponding to carriers of other forces. The researchers found that the relationship holds for point particles too, not just hypothetical strings.

In the sum of all possible interactions that could happen during a particle scattering event, the mathematical term representing each interaction splits into two parts, much as the number 6 splits into 2 × 3. The first part captures the nature of the force in question; for the strong force, this term relates to the property called color. The second term expresses the movement of particles — the “kinematics.”

To perform the double copy, you throw away the color term and replace it with a copy of the kinematics term, turning 2 × 3  into 3 × 3. If 6 describes the outcome of a strong-force event, then the double copy tells us that 9 will match some comparable graviton event.

The double copy has an Achilles heel: Before executing the procedure, theorists must rewrite the extra kinematics term in a form that looks like the color term. This reformatting is hard and may not always be possible as the sum is refined to include ever more convoluted interactions. But if the kinematics oblige, getting the gravity result is as easy as changing 2 × 3  to 3 × 3.

“Once you’ve realized this relationship, then gravity comes for free,” Borsten said.

The procedure doesn’t make much physical sense, as gravitons are not literally pairs of gluons. But it’s a powerful mathematical shortcut. Since developing the double copy, Bern has taken advantage of the massively discounted lunch to challenge the conventional wisdom that all particle theories of gravity give nonsensical, infinite answers.

Bern, Carrasco and others have spent years grinding away at an exotic theory called supergravity, which balances gravitons with partner particles in a mathematically pleasing way. Using the double copy, they’ve completed increasingly precise supergravity calculations. While supergravity is too symmetric to reflect our world, its simplicity makes it the lowest apple on the tree of possible particle theories of gravity. Bern and company hope to extend their computational successes to more realistic theories.

Seeing Double in Black Holes

Encouraged by the double copy’s success in dealing with gravitons — the smallest possible ripples in space-time — Donal O’Connell of the University of Edinburgh and Ricardo Monteiro and Chris White at Queen Mary University of London have used it to reimagine the most extreme trick in gravity’s repertoire.

Black holes famously warp space-time intensely enough to trap light, and spinning black holes drag the warped space-time fabric around with them. The equations are super complicated. If you look at the equations for a spinning black hole, “your eyes will probably bleed,” O’Connell said.

The researchers split the black hole’s warped space-time into two pieces: flat space-time and a term representing a strong deviation from flatness. Then, Monteiro explained, they asked themselves whether the deviation term is the double copy of something.

It is. Stationary and spinning black holes alike act as if they are double copies of charged particles, the group reported in 2014. “You reduce this complicated thing to something unbelievably simple,” O’Connell said.

Black holes are not literally two copies of electrons. But their mathematical relationship is loosening the stranglehold that Einstein’s relativity theory exerts on the gravitational realm. “My secret master plan is to show that you can compute anything using the double copy that you can compute with the classical Einstein equations,” O’Donnell said.

Recently, double copy practitioners have jumped into gravitational wave astronomy, the new discipline that detects distant objects and events by means of the ripples they kick up in space-time. In just a few years, Bern and his colleagues have used the shortcut to make gravitational wave predictions that already rival state-of-the-art calculations from general relativity.

A Common Language

The double copy has revealed a hidden, simpler side of gravity, but even theorists who have devoted their careers to exploring the relationship wonder where the simplicity is coming from.

“Is it telling us something important and primal, or is it some trick?” said Carrasco.

Researchers note that electromagnetism, the weak force and the strong force each follow directly from a specific kind of symmetry — a change that doesn’t change anything overall (the way rotating a square by 90 degrees gives us back the same square).

Intriguingly, when rewritten with the double copy, gravity appears to obey a symmetry similar to those of the three quantum forces. It’s “like there’s a fourth, mother symmetry,” O’Connell said, “a symmetry underlying the whole lot.”

The path to a complete theory of quantum gravity is long and uncertain, and the double copy might not lead all the way there. But its ability to cut through the verbiage that fills calculations gives theorists hope that the two dueling formulations of modern physics aren’t the final story. “This is a striking example that there are languages to learn that aren’t manifest in the way we traditionally talk about theories,” Carrasco said.

Coinsmart. Beste Bitcoin-Börse in Europa

Continue Reading


Qubit-efficient encoding schemes for binary optimisation problems




Benjamin Tan1, Marc-Antoine Lemonde1, Supanut Thanasilp1, Jirawat Tangpanitanon1, and Dimitris G. Angelakis1,2

1Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore 117543
2School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece 73100

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We propose and analyze a set of variational quantum algorithms for solving quadratic unconstrained binary optimization problems where a problem consisting of $n_c$ classical variables can be implemented on $mathcal O(log n_c)$ number of qubits. The underlying encoding scheme allows for a systematic increase in correlations among the classical variables captured by a variational quantum state by progressively increasing the number of qubits involved. We first examine the simplest limit where all correlations are neglected, i.e. when the quantum state can only describe statistically independent classical variables. We apply this minimal encoding to find approximate solutions of a general problem instance comprised of $64$ classical variables using $7$ qubits. Next, we show how two-body correlations between the classical variables can be incorporated in the variational quantum state and how it can improve the quality of the approximate solutions. We give an example by solving a $42$-variable Max-Cut problem using only $8$ qubits where we exploit the specific topology of the problem. We analyze whether these cases can be optimized efficiently given the limited resources available in state-of-the-art quantum platforms. Lastly, we present the general framework for extending the expressibility of the probability distribution to any multi-body correlations.

One promising application where quantum computers are expected to become a disruptive innovation is in the field of combinatorial optimization. So far, most quantum algorithms for combinatorial problems entail mapping each classical variable to single qubit in the quantum device. While this mapping in principle allows for an efficient search over the exponentially large number of possible solutions, the quantum resources required and restricted connectivity of current quantum hardware limits the problem sizes to toy models. Current state-of-the-art quantum experiments have found approximate solutions for a fully connected problem of only $17$ variables while modern classical methods can find solutions for problem sizes with over $10^4$ variables. In our work, we introduce an alternative encoding scheme that could allow intermediate-scale quantum devices to tackle problem sizes rivaling the biggest instances that can be solved using modern classical methods.

We adopt a fundamentally different approach by using a quantum state to encode correlations between restricted subsets of variables. In the simplest allowed encoding, each subset consists of a single variable, allowing for approximate solutions to be found using exponentially fewer qubits. The flexibility of our encoding scheme allows for additional qubits to systematically increase the correlations captured by the quantum state. Using numerical simulations, we demonstrate this encoding scheme on a $64$-variable optimization problem using only $7$ qubits and $104$ gates in the limiting case where no correlations are captured. We also demonstrate, with a $42$-variable example using $8$ qubits, how capturing two-body correlation yields better results. Lastly, we include results showing how this reduction in resources is advantageous compared to standard quantum approaches when implemented on noisy quantum hardware.

Moving forward, we aim to explore the possibilities of enhancing the performance of this encoding scheme to compete alongside state-of-the-art classical algorithms

► BibTeX data

► References

[1] Deanna M. Abrams, Nicolas Didier, Blake R. Johnson, Marcus P. da Silva, and Colm A. Ryan. Implementation of xy entangling gates with a single calibrated pulse. Nature Electronics, 3 (12): 744–750, Nov 2020. ISSN 2520-1131. 10.1038/​s41928-020-00498-1.

[2] Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation. Rev. Mod. Phys., 90: 015002, Jan 2018. 10.1103/​RevModPhys.90.015002.

[3] Arya K. Babbush R. et al. Arute, F. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. 10.1038/​s41586-019-1666-5.

[4] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. Quantum algorithms for quantum chemistry and quantum materials science. Chemical Reviews, 120 (22): 12685–12717, Oct 2020. ISSN 1520-6890. 10.1021/​acs.chemrev.9b00829.

[5] Andreas Bengtsson, Pontus Vikstål, Christopher Warren, Marika Svensson, Xiu Gu, Anton Frisk Kockum, Philip Krantz, Christian Križan, Daryoush Shiri, Ida-Maria Svensson, and et al. Improved success probability with greater circuit depth for the quantum approximate optimization algorithm. Physical Review Applied, 14 (3), Sep 2020. ISSN 2331-7019. 10.1103/​physrevapplied.14.034010.

[6] Lee Braine, Daniel J Egger, Jennifer Glick, and Stefan Woerner. Quantum algorithms for mixed binary optimization applied to transaction settlement. arXiv preprint arXiv:1910.05788, 2019.

[7] Fernando G.S.L. Brandão, Aram W. Harrow, and Michał Horodecki. Local Random Quantum Circuits are Approximate Polynomial-Designs. Communications in Mathematical Physics, 346 (2): 397–434, 2016. ISSN 14320916. 10.1007/​s00220-016-2706-8.

[8] Colin D. Bruzewicz, John Chiaverini, Robert McConnell, and Jeremy M. Sage. Trapped-ion quantum computing: Progress and challenges. Applied Physics Reviews, 6 (2): 021314, 2019. 10.1063/​1.5088164.

[9] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature Communications, 12 (1), Mar 2021. ISSN 2041-1723. 10.1038/​s41467-021-21728-w.

[10] Brian Coyle, Daniel Mills, Vincent Danos, and Elham Kashefi. The born supremacy: quantum advantage and training of an ising born machine. npj Quantum Information, 6 (1), Jul 2020. ISSN 2056-6387. 10.1038/​s41534-020-00288-9.

[11] Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao. Expressive power of parametrized quantum circuits. Physical Review Research, 2 (3), Jul 2020. ISSN 2643-1564. 10.1103/​physrevresearch.2.033125.

[12] Suguru Endo, Zhenyu Cai, Simon C. Benjamin, and Xiao Yuan. Hybrid quantum-classical algorithms and quantum error mitigation. Journal of the Physical Society of Japan, 90 (3): 032001, Mar 2021. ISSN 1347-4073. 10.7566/​jpsj.90.032001.

[13] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014a.

[14] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem. arXiv preprint arXiv:1412.6062, 2014b.

[15] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The quantum approximate optimization algorithm and the sherrington-kirkpatrick model at infinite size. arXiv preprint arXiv:1910.08187, 2019.

[16] Dimitris Fouskakis and David Draper. Stochastic optimization: a review. International Statistical Review, 70 (3): 315–349, 2002. 10.1111/​j.1751-5823.2002.tb00174.x.

[17] F. Glover M. Lewis Z.P Lü H.B Wang Y. Wang G. Kochenberger, J.K. Hao. The unconstrained binary quadratic programming problem: a survey. Journal of Combinatorial Optimization, 28 (1): 58–81, 2014. 10.1007/​s10878-014-9734-0.

[18] Michael R Garey and David S Johnson. Computers and intractability, volume 174. freeman San Francisco, 1979.

[19] Lov K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 79: 325–328, Jul 1997. 10.1103/​PhysRevLett.79.325.

[20] LLC Gurobi Optimization. Gurobi optimizer reference manual, 2020. URL http:/​/​

[21] Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley, Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo, and et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 17 (3): 332–336, Feb 2021. ISSN 1745-2481. 10.1038/​s41567-020-01105-y.

[22] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M. Chow, and Jay M. Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549 (7671): 242–246, 2017. 10.1038/​nature23879.

[23] Richard M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA, 1972. ISBN 978-1-4684-2001-2. 10.1007/​978-1-4684-2001-2_9.

[24] Nathan Killoran, Thomas R. Bromley, Juan Miguel Arrazola, Maria Schuld, Nicolás Quesada, and Seth Lloyd. Continuous-variable quantum neural networks. Phys. Rev. Research, 1: 033063, Oct 2019. 10.1103/​PhysRevResearch.1.033063.

[25] Tjalling C. Koopmans and Martin Beckmann. Assignment problems and the location of economic activities. Econometrica, 25 (1): 53–76, 1957. ISSN 00129682, 14680262. 10.2307/​1907742.

[26] Nathan Lacroix, Christoph Hellings, Christian Kraglund Andersen, Agustin Di Paolo, Ants Remm, Stefania Lazar, Sebastian Krinner, Graham J. Norris, Mihai Gabureac, Johannes Heinsoo, and et al. Improving the performance of deep quantum optimization algorithms with continuous gate sets. PRX Quantum, 1 (2), Oct 2020. ISSN 2691-3399. 10.1103/​prxquantum.1.020304.

[27] Jose I. Latorre. Image compression and entanglement. arXiv preprint arXiv:0510031, 2005.

[28] Wim Lavrijsen, Ana Tudor, Juliane Müller, Costin Iancu, and Wibe de Jong. Classical optimizers for noisy intermediate-scale quantum devices. arXiv preprint arXiv:2004.03004, 2020. 10.1109/​QCE49297.2020.00041.

[29] Wolfgang Lechner, Philipp Hauke, and Peter Zoller. A quantum annealing architecture with all-to-all connectivity from local interactions. Science Advances, 1 (9): 1–6, 2015. ISSN 23752548. 10.1126/​sciadv.1500838.

[30] Harry Markowitz. Portfolio selection. The Journal of Finance, 7 (1): 77–91, 1952. 10.2307/​2975974.

[31] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan. Quantum computational chemistry. Rev. Mod. Phys., 92: 015003, Mar 2020a. 10.1103/​RevModPhys.92.015003.

[32] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan. Quantum computational chemistry. Reviews of Modern Physics, 92 (1), Mar 2020b. ISSN 1539-0756. 10.1103/​revmodphys.92.015003.

[33] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, 18 (2): 023023, feb 2016. 10.1088/​1367-2630/​18/​2/​023023.

[34] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9 (1): 4812, 2018. 10.1038/​s41467-018-07090-4.

[35] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, Abhinav Kandala, Antonio Mezzacapo, Peter Müller, Walter Riess, Gian Salis, John Smolin, Ivano Tavernelli, and Kristan Temme. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology, 3 (3): 030503, jun 2018. 10.1088/​2058-9565/​aab822.

[36] J. S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Didier, E. Schuyler Fried, S. Hong, P. Karalekas, C. B. Osborn, A. Papageorge, E. C. Peterson, G. Prawiroatmodjo, N. Rubin, Colm A. Ryan, D. Scarabelli, M. Scheer, E. A. Sete, P. Sivarajah, Robert S. Smith, A. Staley, N. Tezak, W. J. Zeng, A. Hudson, Blake R. Johnson, M. Reagor, M. P. da Silva, and C. Rigetti. Unsupervised machine learning on a hybrid quantum computer. arXiv preprint arXiv:1712.05771, 2017.

[37] Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine S. Collins, Arinjoy De, Paul W. Hess, Harvey B. Kaplan, Antonis Kyprianidis, Wen Lin Tan, Christopher Baldwin, and et al. Quantum approximate optimization of the long-range ising model with a trapped-ion quantum simulator. Proceedings of the National Academy of Sciences, 117 (41): 25396–25401, Oct 2020. ISSN 1091-6490. 10.1073/​pnas.2006373117.

[38] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5 (1): 4213, 2014. 10.1038/​ncomms5213.

[39] M. Powell. A view of algorithms for optimization without derivatives. Mathematics TODAY, 43, 01 2007.

[40] John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2: 79, August 2018. ISSN 2521-327X. 10.22331/​q-2018-08-06-79.

[41] Xiaogang Qiang, Xiaoqi Zhou, Jianwei Wang, Callum M. Wilkes, Thomas Loke, Sean O’Gara, Laurent Kling, Graham D. Marshall, Raffaele Santagati, Timothy C. Ralph, Jingbo B. Wang, Jeremy L. O’Brien, Mark G. Thompson, and Jonathan C. F. Matthews. Large-scale silicon quantum photonics implementing arbitrary two-qubit processing. Nature Photonics, 12 (9): 534–539, 2018. 10.1038/​s41566-018-0236-y.

[42] Arthur G. Rattew, Shaohan Hu, Marco Pistoia, Richard Chen, and Steve Wood. A domain-agnostic, noise-resistant, hardware-efficient evolutionary variational quantum eigensolver. arXiv preprint arXiv:1910.09694, 2019.

[43] Troels F. Rønnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V. Isakov, David Wecker, John M. Martinis, Daniel A. Lidar, and Matthias Troyer. Defining and detecting quantum speedup. Science, 345 (6195): 420–424, 2014. ISSN 0036-8075. 10.1126/​science.1252319.

[44] M Saffman. Quantum computing with atomic qubits and rydberg interactions: progress and challenges. Journal of Physics B: Atomic, Molecular and Optical Physics, 49 (20): 202001, oct 2016. 10.1088/​0953-4075/​49/​20/​202001.

[45] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26 (5): 1484–1509, 1997. 10.1137/​S0097539795293172.

[46] Kevin J Sung, Jiahao Yao, Matthew P Harrigan, Nicholas C Rubin, Zhang Jiang, Lin Lin, Ryan Babbush, and Jarrod R McClean. Using models to improve optimizers for variational quantum algorithms. Quantum Science and Technology, 5 (4): 044008, Oct 2020. ISSN 2058-9565. 10.1088/​2058-9565/​abb6d9.

[47] IBM Quantum team. Retrieved from https:/​/​ Ibmq, 2020.

[48] G Wendin. Quantum information processing with superconducting circuits: a review. Reports on Progress in Physics, 80 (10): 106001, sep 2017. 10.1088/​1361-6633/​aa7e1a.

[49] Madita Willsch, Dennis Willsch, Fengping Jin, Hans De Raedt, and Kristel Michielsen. Benchmarking the quantum approximate optimization algorithm. Quantum Information Processing, 19 (7), Jun 2020. ISSN 1573-1332. 10.1007/​s11128-020-02692-8.

[50] Stephen J. Wright. Continuous optimization (nonlinear and linear programming). In Nicholas J. Higham, Mark R. Dennis, Paul Glendinning, Paul A. Martin, Fadil Santosa, and Jared Tanner, editors, The Princeton Companion to Applied Mathematics, chapter 4, page 281–293. Princeton University Press, Princeton, 2015.

[51] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X, 10 (2), Jun 2020. ISSN 2160-3308. 10.1103/​physrevx.10.021067.

Cited by

[1] V. E. Zobov and I. S. Pichkovskiy, “Clustering by quantum annealing on three-level quantum elements qutrits”, arXiv:2102.09205.

[2] Adam Glos, Aleksandra Krawiec, and Zoltán Zimborás, “Space-efficient binary optimization for variational computing”, arXiv:2009.07309.

The above citations are from SAO/NASA ADS (last updated successfully 2021-05-04 12:10:34). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-05-04 12:10:32: Could not fetch cited-by data for 10.22331/q-2021-05-04-454 from Crossref. This is normal if the DOI was registered recently.

Coinsmart. Beste Bitcoin-Börse in Europa

Continue Reading
Aviation4 days ago

American Airlines Passenger Arrested After Alleged Crew Attack

Blockchain3 days ago

The Reason for Ethereum’s Recent Rally to ATH According to Changpeng Zhao

Blockchain2 days ago

Chiliz Price Prediction 2021-2025: $1.76 By the End of 2025

Blockchain3 days ago

Mining Bitcoin: How to Mine Bitcoin

Blockchain3 days ago

Mining Bitcoin: How to Mine Bitcoin

Fintech4 days ago

Talking Fintech: Customer Experience and the Productivity Revolution

PR Newswire2 days ago

Teamsters Lead Historic Defeat of CEO Pay at Marathon Petroleum

Blockchain5 days ago

Bitcoin Gains Bullish Momentum, Signals Another Major Rally

Blockchain5 days ago

Ethereum Market Capital Overtakes Bank of America

Aviation5 days ago

Lufthansa To Equip Entire Boeing 777F Fleet With Sharkskin Technology

Blockchain3 days ago

Mining Bitcoin: How to Mine Bitcoin

Startups5 days ago

Equity Monday: TechCrunch goes Yahoo while welding robots raise $56M

Cyber Security4 days ago

Alaska Court System Temporarily Disconnected the Internet After a Cybersecurity Threat

AR/VR1 day ago

Apple is giving a laser company that builds some of its AR tech $410 million

Blockchain5 days ago

Ripple Releases $1.6 Billion XRP from Escrow Account

Startups5 days ago

Top-5 Working Marketing Strategies on 2021 for Moving Company

Crowdfunding5 days ago

Cryptocurrency ATM Network Bitcoin Depot Launches More Than 350 New ATMs Across the U.S.

Esports3 days ago

TFT 11.9 B-patch nerfs Mordekaiser and LeBlanc

Blockchain3 days ago

Amid XRP lawsuit, Ripple appoints former US Treasurer to its board, and names new CFO

Cyber Security4 days ago

Incident Detection and Response Basics Greatly Matter