2 added 107 characters in body edited Jul 23 '18 at 14:42 DaftWullie 23.5k11 gold badge99 silver badges5555 bronze badges Does “quantum registers with n qubits are able to hold $$2^n$$ values and therefore scale exponentially” actually hold that straightforwardly? No, it doesn't. That's the popularised explanation of where quantum computers get their speed-up, but it's far more nuanced than that. To illustrate this, imagine you have a function $$f:x\in\{0,1\}^n\mapsto y\in\{0,1\}^m$$. Sure, in quantum you can produce the state $$|\Psi\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle|f(x)\rangle$$ so, in some sense,the function $$f$$ has been evaluated at every $$x$$. But what answers can you get? What you certainly cannot read out is every different value of $$f(x)$$: when you measure (assuming projective measurements) you get a maximum of 1 bit of information for every measurement, $$n+m$$ bits. But there are $$2^n$$ inputs, each with $$m$$ bits to learn, so you need to be able to determine $$m2^n$$. This is nonot really any better than doing things classically (in facta sense, it's a bit worse because a single measurement will pick an $$x$$ at random, but classically you'd normally only get the $$m$$ bits of information from the final outcome). The real power of quantum computation comes from doing something clever with that state $$|\Psi\rangle$$. This usually relies on some special properties that you know about $$f(x)$$, such as "it has a global property which is parametrised by $$k$$. Find $$k$$.". For example, in the Deutsch-Jozsa algorithm, the structure is that either all $$f(x)$$ are the same, or there's a perfect 50:50 split between answers (Here, $$k$$ is one bit of information). That sort of comparison between different function evaluations in a classical domain obviously needs lots of different function evaluations, whereas in the quantum domain, sometimes one can perform the right measurement that compares different parts of the superposition and gives you the right information out. Does “quantum registers with n qubits are able to hold $$2^n$$ values and therefore scale exponentially” actually hold that straightforwardly? No, it doesn't. That's the popularised explanation of where quantum computers get their speed-up, but it's far more nuanced than that. To illustrate this, imagine you have a function $$f:x\in\{0,1\}^n\mapsto y\in\{0,1\}^m$$. Sure, in quantum you can produce the state $$|\Psi\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle|f(x)\rangle$$ so, in some sense,the function $$f$$ has been evaluated at every $$x$$. But what answers can you get? What you certainly cannot read out is every different value of $$f(x)$$: when you measure (assuming projective measurements) you get a maximum of 1 bit of information for every measurement, $$n+m$$ bits. But there are $$2^n$$ inputs, each with $$m$$ bits to learn, so you need to be able to determine $$m2^n$$. This is no better than doing things classically (in fact, it's a bit worse because a single measurement will pick an $$x$$ at random). The real power of quantum computation comes from doing something clever with that state $$|\Psi\rangle$$. This usually relies on some special properties that you know about $$f(x)$$, such as "it has a global property which is parametrised by $$k$$. Find $$k$$.". For example, in the Deutsch-Jozsa algorithm, the structure is that either all $$f(x)$$ are the same, or there's a perfect 50:50 split between answers (Here, $$k$$ is one bit of information). That sort of comparison between different function evaluations in a classical domain obviously needs lots of different function evaluations, whereas in the quantum domain, sometimes one can perform the right measurement that compares different parts of the superposition and gives you the right information out. Does “quantum registers with n qubits are able to hold $$2^n$$ values and therefore scale exponentially” actually hold that straightforwardly? No, it doesn't. That's the popularised explanation of where quantum computers get their speed-up, but it's far more nuanced than that. To illustrate this, imagine you have a function $$f:x\in\{0,1\}^n\mapsto y\in\{0,1\}^m$$. Sure, in quantum you can produce the state $$|\Psi\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle|f(x)\rangle$$ so, in some sense,the function $$f$$ has been evaluated at every $$x$$. But what answers can you get? What you certainly cannot read out is every different value of $$f(x)$$: when you measure (assuming projective measurements) you get a maximum of 1 bit of information for every measurement, $$n+m$$ bits. But there are $$2^n$$ inputs, each with $$m$$ bits to learn, so you need to be able to determine $$m2^n$$. This is not really any better than doing things classically (in a sense, it's a bit worse because a single measurement will pick an $$x$$ at random, but classically you'd normally only get the $$m$$ bits of information from the final outcome). The real power of quantum computation comes from doing something clever with that state $$|\Psi\rangle$$. This usually relies on some special properties that you know about $$f(x)$$, such as "it has a global property which is parametrised by $$k$$. Find $$k$$.". For example, in the Deutsch-Jozsa algorithm, the structure is that either all $$f(x)$$ are the same, or there's a perfect 50:50 split between answers (Here, $$k$$ is one bit of information). That sort of comparison between different function evaluations in a classical domain obviously needs lots of different function evaluations, whereas in the quantum domain, sometimes one can perform the right measurement that compares different parts of the superposition and gives you the right information out. 1 answered Jul 23 '18 at 7:40 DaftWullie 23.5k11 gold badge99 silver badges5555 bronze badges Does “quantum registers with n qubits are able to hold $$2^n$$ values and therefore scale exponentially” actually hold that straightforwardly? No, it doesn't. That's the popularised explanation of where quantum computers get their speed-up, but it's far more nuanced than that. To illustrate this, imagine you have a function $$f:x\in\{0,1\}^n\mapsto y\in\{0,1\}^m$$. Sure, in quantum you can produce the state $$|\Psi\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle|f(x)\rangle$$ so, in some sense,the function $$f$$ has been evaluated at every $$x$$. But what answers can you get? What you certainly cannot read out is every different value of $$f(x)$$: when you measure (assuming projective measurements) you get a maximum of 1 bit of information for every measurement, $$n+m$$ bits. But there are $$2^n$$ inputs, each with $$m$$ bits to learn, so you need to be able to determine $$m2^n$$. This is no better than doing things classically (in fact, it's a bit worse because a single measurement will pick an $$x$$ at random). The real power of quantum computation comes from doing something clever with that state $$|\Psi\rangle$$. This usually relies on some special properties that you know about $$f(x)$$, such as "it has a global property which is parametrised by $$k$$. Find $$k$$.". For example, in the Deutsch-Jozsa algorithm, the structure is that either all $$f(x)$$ are the same, or there's a perfect 50:50 split between answers (Here, $$k$$ is one bit of information). That sort of comparison between different function evaluations in a classical domain obviously needs lots of different function evaluations, whereas in the quantum domain, sometimes one can perform the right measurement that compares different parts of the superposition and gives you the right information out.