Solving the Traveling Salesman Problem Using Quantum Computer

The story

How does it work?

D-Wave quantum computer

How the app works

1. Selecting cities

2. Clicking the “Find optimal route” button

3. Translation

4. Sending problem to the Quantum Computer

5. Inside the QPU

6. Grand finale

TSP — why it’s important?

Why it’s hard

Why it’s important

Putting quantum computers in the picture

Limits of classical computing

  • transistors are so small that quantum effects start affecting them, which is not necessarily desirable — further miniaturization is no longer possible.
  • it’s hard to dissipate heat from such small devices efficiently.
  • there are limits of how big speedup we can get from using devices in parallel, thus adding more and more cores does not improve the overall performance (see Amdahl’s law),
  • in general, it’s getting harder and harder for companies to justify the huge effort that has to be put on developing new processor generations.

The potential of quantum computing

Current state of quantum computing

Hybrid quantum computing

  • Divide 1 million cities into groups of 50 cities.
  • Solve each group using a quantum computer.
  • Combine smaller solutions together.

DIY

  1. Wired guide
  2. BCG report on QC
  3. Great talk by John Preskill and interview with him as well
  1. Leap — a platform which gives you access to the actual D-Wave machine. Right now it’s accessible only in North America, but access for people in Europe should be available in Spring 2019. It has plenty of tutorials and other resources that will help you start.
  2. Forest and IBM Q — also good platforms with access to real quantum computers and helpful communities.
  3. At Bohr.Technology we are interested in solving optimization problems with quantum computers. Here you can find algorithm very similar to the one we used for this demo. If you would like to help us develop these algorithms, feel free to apply to our bqResearch program
  4. If you are interested in how to solve TSP problem with a universal quantum computer, please take a look at the tutorials I’ve created.
  5. Quantum Open Source Foundation is also a place with plenty of great resources for beginners.

Team & closing notes

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Variables

Reconstructing 3D objects from 2D images

Why do you need to backup AWS workloads?

How I Taught Myself to Code

Programming & Code Deployment Practices That Benefit Application Security

Earn Coursera Certificates For Free On Some Programming Courses During the Coronavirus Epidemic.

Participation of your project in the CRODO IDO | How to apply for participation

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Michał Stęchły

Michał Stęchły

More from Medium

Overview On Quantum Computing

Deep Learning Algorithms

Beginning Machine Learning For Developers

How to Possibly Create a New Type of Quantum Computer.