1
$\begingroup$

I read in this article that the amount of bits that can be emulated by a certain number of qubits is 2^(number of qubits). This is because each qubit can be in one of 2 states after it collapses, and so before all the quantum... whatevers collapse, that is the function that gets that result. At least, that was generally what it was saying, but I probably mangled the explanation myself; sorry.

Anyway, this relation (2^n) happens to be the same as the relation between memory registers and RAM in classical computers (i.e. if the computer has n bits in the register, it can have up to 2^n bytes in RAM). Is this important? Does it mean qubits will become like the memory registers and their states like the RAM when we switch to quantum computers? Or is it just something that seems important but is actually meaningless in practice?

By the way, there don't seem to be any tags for some things I referenced, like RAM & memory registers. Is that because the site is so new, or am I just not looking hard enough?

$\endgroup$
  • $\begingroup$ "same as the relation between memory registers and RAM in classical computers" In what sense? $\endgroup$ – phs Feb 17 '14 at 23:30
  • $\begingroup$ I think it was registers, but it may have been the bus or something. If there are n bytes in the bus (or whatever) there are 2^n bytes in RAM. Similarly, if there are n qubits, there are 2^n states they can all be in at one time (up, down, up....; down, up down....; etc.) Edited my question. $\endgroup$ – trysis Feb 17 '14 at 23:35
  • 2
    $\begingroup$ You might read scottaaronson.com/democritus/lec10.html, especially the section on Quantum Computing and NP-complete Problems. $\endgroup$ – D.W. Feb 17 '14 at 23:54
  • 1
    $\begingroup$ On the "classical computer" half of your comparison, you appear to be thinking of the relationship between the size of an address ($n$) and the size of the space it can describe ($2^n$). When the size of an address is convenient, it is common to make bus widths match that size, so that addresses are easy to send to and from memory. $\endgroup$ – phs Feb 18 '14 at 0:10
  • $\begingroup$ Yes, I think that is what I meant. That's called the register, right? $\endgroup$ – trysis Feb 18 '14 at 0:42
3
$\begingroup$

This coincidence just shows that the function $n \mapsto 2^n$ shows up in many places. For example, an $n$ bit register can store up to $2^n$ different values. If wireless frequency is parametrized using $n$ bits, then there are up to $2^n$ possible frequencies (in fact, there are probably a bit less). If an IP address is $n$ bits, then there are at most $2^n$ possible IP addresses (in fact, there are fewer). If a cryptographic key is $n$ bits long, then there are $2^n$ possible keys. And so on.

$\endgroup$
  • $\begingroup$ Thank you. I thought this was the case, I was just wondering if there were any deeper connection in this particular case, as they seem superficially similar in other ways as well. $\endgroup$ – trysis Feb 18 '14 at 0:23
  • $\begingroup$ "If an IP address is $n$ bits, then there are at most $2^n$ possible IP addresses (in fact, there are fewer)." - please elaborate. $\endgroup$ – G. Bach Feb 18 '14 at 0:31
  • $\begingroup$ There are that many IP addresses, exactly, but I think he meant we can't actually use all of them at one time, because many people use more than they actually need. He may also be referring to private, link-local, multicast, etc. networks, with 1,000's or 1,000,000's of addresses each. $\endgroup$ – trysis Feb 18 '14 at 0:40
  • $\begingroup$ @G.Bach Some of them are reserved: en.wikipedia.org/wiki/…. $\endgroup$ – Yuval Filmus Feb 18 '14 at 2:43
  • $\begingroup$ Ah alright, I thought you might mean those, but it never hurts to ask. $\endgroup$ – G. Bach Feb 18 '14 at 2:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.