Skip to content
Can a quantum computer solve optimization problems more Efficiently than a classical computer? episode artwork

Oct 27, 2016

Can a quantum computer solve optimization problems more Efficiently than a classical computer?

from Sommerfeld Theory Colloquium (ASC) Hosted by Peter Young

In this talk I will discuss connections between the physics of complex systems such as spin glasses and attempts to solve optimization problems by ”Adiabatic Quantum Computing” (AQC), a version of ”Quantum Annealing” (QA). An optimization problem is one in which one has to minimize (or maximize) an energy function in which there is competition between different terms so no single configuration of the variables minimizes each term in the energy. In statistical physics this competition is called ”frustration”. It leads to a complex energy ”landscape” with many valleys separated by barriers, so simple algorithms easily get trapped in local minima which have a higher energy than the global minimum. Many problems in science, and engineering are formulated as optimization problems. In quantum annealing one tries to avoid being trapped in a local minimum by adding quantum fluctuations so the system can tunnel to regions of lower energy. The strength of the quantum fluctuations is gradually reduced to zero during the annealing schedule. This method applies to problems with binary variables, known as qubits in the quantum case. There is considerable interest in AQC at present, in large part because a company, D-Wave, has produced an actual device, the latest version of which has about one thousand qubits. In addition, there has been considerable theoretical work mainly using computer simulations to see if there is a ”quantum speedup” compared with analogous classical algorithms in which thermal, rather than quantum, fluctuations are used to escape from local minima. In the talk I will discuss difficulties in obtaining a quantum speedup due to (i) (quantum) phase transitions that the system can undergo during the annealing schedule, and (ii) the sensitivity of the state of the system to the precise values of the interactions, i.e. chaos. A related chaotic effect is that the state of the system can change dramatically with small changes in the temperature (temperature-chaos), for thermal annealing, and the strength of the quantum fluctuations, for quantum annealing.

Episode details come from the podcast's RSS feed.

Embed this episode

Ready to play

Can a quantum computer solve optimization problems more Efficiently than a classical computer?

No transcript yet.

Requests help us decide what to transcribe next.

Trauma Talks : With Russ Tellup rtellup Hi, I’m Russ Tellup, a Trauma-Informed Somatic Coach and Level 1 Brainspotting practitioner. In my podcast "Trauma Talks," I dive into the neuroscience of trauma, exploring somatic healing practices, Polyvagal Theory, and IFS (Internal Family Systems) parts work. I also occasionally address the complexities of narcissistic abuse, offering insights and tools for healing. Join me each week as we navigate the journey of recovery, resilience, and self-discovery together. AI for Creative Professionals: Practical Tools for Designers, Writers & Marketers Tiana Ned AI for Creative Professionals: How to use AI tools without losing your creative edgeTiana shows creative professionals how to work with AI tools instead of competing against them. Each episode covers specific tools and techniques you can use right away.What you’ll learn:➤ Which AI tools actually help with design, writing, and marketing➤ How to write prompts that work➤ Ways to keep your personal style when using AI➤ Career moves that make sense as the industry changes➤ Real stories from creatives who adapted successfully➤ When AI helps and when you should do it yourselfPerfect for:➤ Designers, writers, marketers, video creators, UX professionals, photographers, podcasters, and anyone who makes things for a living.No abstract theory. Just practical steps you can take today.Tiana shares AI tools and techniques from her own freelance work. She tests everything herself before sharing what actually works.New episodes every week. Hit subscribe to keep your skills current.Topics: For You Leaders Kirk Dando Have you ever thought, "Running a business shouldn't be this hard." Then you need to listen to the For You Leaders podcast. Come listen to Kirk Dando and glean from his experience leading 11,000+ executives and business leaders around the world. From startups to hyper-growth companies, Kirk has seen it all. We'll bring you interviews with some of today's best CEOs. Short on theory and long on practical examples, you will leave every episode equipped to be a better leader. The Let Them Theory | Free Audiobook | All The Chapters Explained Megan & Ross The Let Them Theory by Mel Robbins | Podcast Series DescriptionGet ready to transform your life with The Let Them Theory by Mel Robbins, an electrifying podcast series that brings the revolutionary insights of Mel Robbins’ bestselling book to your ears! This bold, no-nonsense show dives deep into the game-changing "Let Them + Let Me" philosophy, empowering you to break free from the weight of others’ expectations, ditch people-pleasing habits, and unleash your true potential. With each episode, Mel delivers practical, science-backed strategies to let go of control, set unshakable boundaries

Frequently asked questions

When was this Sommerfeld Theory Colloquium (ASC) episode published?

This episode was published on October 27, 2016.

Can I download this Sommerfeld Theory Colloquium (ASC) episode?

Yes. Use the download control on the episode player to save the publisher-provided media file.