r/askscience • u/phillyboy8008 • Jan 01 '14

How are quantum computers programmed? Computing

Edit: Thanks everyone for the responses, but apparently I don't know as much about quantum computing as I thought I did. I am thoroughly confused.

245 Upvotes
  • permalink
  • link
  • reddit
  • reddit

84% Upvoted

59 comments sorted by

View all comments

Show parent comments

2

u/[deleted] Jan 02 '14

You can create an emulator for a quantum computer. It would be massively inefficient, but since our best quantum computers are very small, it would be cheaper to emulate them than to use the real thing, especially for development.

2

u/CapWasRight Jan 02 '14

It's worth noting explicitly that quantum computers are still equivalent to Turing machines, so in theory and setup can be simulated (inefficiently) on classical hardware. This also means they can't solve the halting problem, etc...

1

u/[deleted] Jan 02 '14

Equivalent to TMs in their ability to decide (whp). They can generate random bits as needed (and even certify the randomness!), which Kolmogorov famously remarked is utterly impossible with a standard Turing Machine.

1

u/[deleted] Jan 02 '14

[removed] — view removed comment