Author Topic: Episode 37: Quantum Computing  (Read 1806 times)

Offline bn

  • Titanium Physicist
  • Administrator
  • Godzilla!!!
  • *****
  • Posts: 1065
  • Karma: +1/-0
  • Compressing Hearts, Super Robo Style
    • View Profile
    • The Titanium Physicists Podcast
Episode 37: Quantum Computing
« on: October 16, 2013, 10:26:35 PM »
So we made a new episode. and it's pretty good.

but the sound is bad.
Titanium Physicists has a pro-bee-analogy agenda. That's certainly no secret.

Offline scikopas

  • Miocene Terror Bird
  • *******
  • Posts: 100
  • Karma: +0/-0
    • View Profile
    • LASER-Let's Agree Science and Engineering are Rad
Re: Episode 37: Quantum Computing
« Reply #1 on: October 17, 2013, 12:25:13 PM »
I was too interested in the episode to focus on the sound being off, this show was great.
PhD student in Materials Science at Arizona State University currently working on high-temperature superconductors and quantum computers or something.
my (materials) science podcast: LASER (Let's Agree Science and Engineering are Rad!) twitter @scikopas

Offline bobmath

  • Miocene Terror Bird
  • *******
  • Posts: 100
  • Karma: +0/-0
    • View Profile
Re: Episode 37: Quantum Computing
« Reply #2 on: October 17, 2013, 12:34:29 PM »
I love this subject, glad you covered it.

You mostly talk about it from the physics side. I'm a computer guy, so I find the computational side easier to think about. I'm going to blather about that a bit, and try to explain some of the terminology you dropped in the podcast.

Take the factorization problem as an example. You can factor the number 21 with the trial division procedure by dividing by each number below 21 and checking which ones give you a remainder of zero. A quantum computer would construct a superposition of the numbers less than 21 as X, then compute 21/X, and try to get the wavefunction for X to collapse to a state where the remainder is zero.

Factoring big numbers rapidly gets more difficult. Every time you add a digit to the number being factored, you have 10 times the number of trial divisors to check. I wrote a very simple little program to do this, and it can factor a 7-digit number in 1.2 seconds, a 8-digit number in 12 seconds, and a 9-digit number in about 120 seconds. Extrapolating, a 14-digit number would over four months. This is an "exponential time" algorithm. (The current factoring record is a 232-digit number in about two years, using hundreds of computers and sophisticated algorithms that have subexponential complexity.)

One obvious improvement is that you don't need to try division by even numbers. If the number you're factoring isn't divisible by 2, it's not going to be divisible by any other even number. That means your program only has to do half the work, which is a "constant factor" or "linear" improvement.

A somewhat less obvious improvement is that you only have to check divisors up to the square root of the number you're factoring. This is a "quadratic" improvement. Now, every time you add 2 digits, you have to do 10 times as much work.

Implementing this in a quantum computer would presumably give you another quadratic improvement, so now adding 4 digits makes the problem 10 times harder. So to oversimplify the situation, quantum computering potentially doubles the size of problem you can tackle... unless someone invents a better quantum computer!
« Last Edit: October 17, 2013, 12:40:45 PM by bobmath »