SIC-POVM sickness

Posted by marozols

I contracted the SIC-POVM sickness a month ago after reading a paper by Gelo Tabia and Marcus Appleby who explore the qutrit case in great detail. I got over it in a week or so just to contract it again today when a paper by Gilad Gour came out. It has a very promising title that ends with “…symmetric informationally complete measurements exist in all dimensions”. Unfortunately, it begins with “General…”. Let’s see what the paper is about. Update: Chris Ferrie has pointed out to me that a similar result has already been obtained by Marcus Appleby (see Sect. 4 of this paper).

Intuition

The geometric intuition of this result can be summarized as follows:

Choose an arbitrary orthonormal basis for the linear space of all $d \times d$ Hermitian matrices.
Construct a simplex out of these basis vectors in some specific way (see below).
Shrink it sufficiently small so that it fits inside the positive-semidefinite cone.

The last step always works, because the convex body formed by all density matrices contains a ball around the maximally mixed state. The required amount of shrinking is determined by parameter $t$ in Theorem 1 (it is also related via Eq. (7) to parameter $a$ that measures the “purity” of the resulting SIC-POVM).

Details and example

The second step can be described more precisely as follows. Let $\{f_1, \dotsc, f_{d^2-1}\}$ be an arbitrary orthonormal basis of $\mathbb{R}^{d^2-1}$ (think of it as the space of all $d \times d$ traceless Hermitian matrices). Then a regular simplex with vertices $p_1, \dotsc, p_{d^2}$ can be obtained as follows:

$p_i := f - d(d+1) f_i$

$p_{d^2} := (d+1) f$

where $i = 1, \dotsc, d^2-1$ and $f$ is the sum of all $f_i$ (these expressions correspond to Eq. (5) in the paper). For example, if $d=2$ and $f_i := e_i$ is the i-th standard basis vector, then vectors $p_i$ are the rows of the following matrix:

$P = \begin{pmatrix} -5 & 1 & 1 \\ 1 & -5 & 1 \\ 1 & 1 & -5 \\ 3 & 3 & 3 \end{pmatrix}$

They look like this in 3D (the orange arrows):
Simplex
Note that

$P \cdot P^{\mathsf{T}}= \begin{pmatrix} 27 & -9 & -9 & -9 \\ -9 & 27 & -9 & -9 \\ -9 & -9 & 27 & -9 \\ -9 & -9 & -9 & 27 \end{pmatrix}$

hence vectors $p_1, p_2, p_3, p_4$ indeed form a simplex in $\mathbb{R}^3$ . In fact, this construction works in any dimension — there is nothing special about it being of the form $d^2-1$ .

Open questions

The hard question (which is still open) is how to choose the basis $f_i$ so that you need to shrink the simplex as little as possible. In other words, you want the matrices associated to $p_i$ to have rank one. All we know about this case is that the matrices $F_i$ associated to the basis vectors $f_i$ must have certain eigenvalues given by Eq. (11) in the paper. How close do we get to this if $F_i$ are generalized Pauli matrices or Haar random?

It would be interesting to know if anything extra can be said about the matrices $F_i$ if the SIC-POVM obeys Weyl-Heisenberg symmetry (in prime dimensions this is without loss of generality due to Huangjun Zhu).

Ctrl+Z for Mathematica!

Posted by marozols

As embarrassing as it may be, the world’s most sophisticated computer algebra system Mathematica lacks a proper undo feature!

It took over 20 years and millions of users until eventually Reema Al-Aifari, a mathematician from Austria, stood up and demanded that Ctrl+Z is finally properly implemented! If you are among these millions, you probably know exactly what I’m talking about, so please consider signing her petition!

My experience

The rest of this post is a rant about my own experience with Mathematica. I have been using it for 10 years almost daily starting from version 5.0 onward. I think it is a great tool and I have to admit that nowadays I program almost exclusively in Mathematica. The reason is that typically, for the kind of problems I need to solve,

writing the program takes more time than running it.

And even if I have to wait a bit for the answer, it is still OK, since often I need to run the program only once. In other words, the strength of Mathematica is the ability to develop code fast. However, it’s not all just wonderful and pink… (or orange?)

Undo

Throughout these years I have acquired a habit of working with Mathematica as if there would not be any undo feature at all. In fact, even if you try to use undo, there is no way to know exactly how much of your work would be undone (by the only precious undo you have!), so why bother — just make a copy of the cell you’re about to edit before you do anything you might regret. Another option, of course, is to follow the official documentation of the undo feature and just close the file (without saving the changes!!!) and then reopen whatever you had when you last saved! Now, how ridiculous is that?

Selection

Of course, we’re not in 1988 anymore, so some progress has been made. For example, you might have noticed that now you can not only use arrow keys to select more text while holding shift, but also less (in case you selected too much). Why did it take 20 years to implement that?

Bugs (What’s that?)

The thing that annoys me the most is that, by definition,

Mathematica has no bugs.

It only has features! When a new version is released, all the great new features are listed, accompanied by beautiful colorful pictures. But where is the list of bugs that were (or weren’t) fixed? How do I know if a certain function has a known bug and whether it has been fixed in the new release or not? All that is mentioned are some “improvements” and “stability enhancements”, but no details are given.

I understand that Mathematica is not an open source project, but I don’t see what is the advantage of not making the list of known bugs public. I don’t think that it would harm Mathematica‘s reputation. On the contrary, it would be easier to avoid pitfalls that others have fallen into and thus get more reliable answers to your computation. After all, this program is for doing mathematics and therefore it is important to know when it gives correct answers and when it doesn’t.

I believe that most Mathematica users genuinely want the product to be better and some even report the bugs they have found. At least I did. But I kind of gave up on it, since it did not really seem like Wolfram appreciates any feedback from users (maybe things have improved more recently). This is in sharp contrast with the situation in the web browsers market, where a special hacking contest called Pwn2Own is organized, and researchers can actually get significant monetary prizes for finding security flaws in web browsers such as IE, Chrome or Firefox. Finding bugs in complicated software such as Mathematica is also highly nontrivial, but there is zero incentive to do so.

Conclusion

Mathematica is an extremely powerful tool with a significant and wide range of applications. However, the consequences of it not working correctly can also be significant. Hence, it would be good to know when that can happen. Also, if users desperately want some feature, maybe they have a point and it would be worthwhile to implement it.

I don’t know if the petition will make any difference. But I also don’t know any Mathematica user who would not be complaining to his or her colleagues about how frustrating Mathematica can sometimes be.

So, Stephen, please don’t be a stubborn child. We don’t need no new kind of science, just admit what’s wrong with your program!

Thank you!

Nonlocality without entanglement

Posted by marozols

After much work we finally uploaded our paper titled “A framework for bounding nonlocality of state discrimination” on the arXiv (this is joint work with Andrew Childs, Debbie Leung, and Laura Mančinska).

Let me informally explain what quantum nonlocality without entanglement is about and briefly summarize the main results of our paper.

Can you tell an apple from an orange?

Let me describe a slightly strange game. Imagine that some crazy biotechnology corporation like Monsanto comes up with a way to grow a new genetically modified fruit called abo. An abo fruit consists of two halves: each of the halves is either an apple (A), banana (B), or orange (O).

In total there are 9 different possible abo fruits: apple-apple, apple-banana, apple-orange, banana-apple, banana-banana, etc. Moreover, let’s assume that each combination is equally likely.

Now, two friends Amandine and Bobby that live in two different places decide to play the following game. They ask somebody to buy an abo fruit, cut it in two halves and mail one half to each of them. Their task is to determine which of the 9 possible combinations it is. (We assume that abo fruits don’t go bad, since they have been properly sprayed with Monsanto’s chemicals.)

Since Amandine and Bobby live in different places, we allow them to talk over Skype to make their decision. In fact, they can even use the video mode to show each other the half of the fruit they have. Technically, this is called LOCC (local operations and classical communication).

If you think about this for a bit, you should realize that this is clearly a very silly game! Each of the parties can easily identify their half of the fruit as either an apple, orange, or banana, and inform the other party. Thus, no fun in the classical case.

Quantum fruits?

Imagine that Monsanto’s technology advances to the point when they can create superpositions of different plant DNA and produce quantum abo fruits, where each half of the fruit is an arbitrary combination of an apple, banana, and orange. For example,

$\displaystyle \frac{|\text{apple}\rangle + |\text{banana}\rangle}{\sqrt{2}} \otimes |\text{orange}\rangle$

is a valid quantum abo fruit (Amandine has something between an apple and banana, but Bobby has an orange). If you buy it at supermarket, it might look something like this:

To be fair, we should allow only 9 different kinds of quantum abo fruits to be produced. Moreover, we require that they can be discriminated globally, i.e., when Amandine and Bobby are together and perform a joint observation of the whole fruit (in other words, the corresponding quantum states form an orthonormal product basis).

Now the question is: can Amandine and Bobby always tell the 9 quantum abo fruits apart over Skype? Surprisingly, the answer to this question is “No”.

Sausage states…

Let us consider a specific construction (also known as domino states). If we replace fruits by numbers, we can write these 9 states as

$|\psi_1\rangle = |1\rangle \otimes |1\rangle$
$|\psi_{2,3}\rangle = |0\rangle \otimes |0 \pm 1\rangle$
$|\psi_{4,5}\rangle = |2\rangle \otimes |1 \pm 2\rangle$
$|\psi_{6,7}\rangle = |1 \pm 2\rangle \otimes |0\rangle$
$|\psi_{8,9}\rangle = |0 \pm 1\rangle \otimes |2\rangle$

where $|i \pm j\rangle := (|i\rangle \pm |j\rangle) / \sqrt{2}$ . Clearly, these all are product states, and one can easily check that they are mutually orthogonal.

Alternatively, we can depict them as “sausages” on a grill, where Amandine has the first half (rows), but Bobby has the second half of the state (columns):

These states were introduced by Charles Bennett, David DiVincenzo, Christopher Fuchs, Tal Mor, Eric Rains, Peter Shor, John Smolin, and William Wootters in 1998 in their paper “Quantum nonlocality without entanglement”.

They show that these states cannot be locally discriminated even if Amandine and Bobby are allowed to talk on Skype as long as they want. No matter what they do, they will always have at least some small amount (at least 0.00000531 bits) of uncertainty left about what their joint state is. (Technically, we say that these states cannot be discriminated by LOCC asymptotically.) Thus, despite there being no entanglement, these states exhibit some nonlocal properties. That’s why this phenomenon is called quantum nonlocality without entanglement.

Intuitively, the problem is that Amandine cannot just identify her half of the state as being either 0, 1, or 2, since this would destroy the superposition in case the state was, say $|\psi_8\rangle$ or $|\psi_9\rangle$ , and a similar argument holds for Bobby. In other words, the reduced states on Amandine’s side are not orthonormal, so there is no preferred basis in which to perform the first measurement. However, it is very hard to make this argument rigorous and obtain a quantitative estimate of the degree of failure.

Our contributions and the proof idea

We provide a framework for bounding the amount of nonlocality in a given set of bipartite quantum states in terms of a lower bound on the probability of error in any LOCC discrimination protocol. The main idea is to establish a trade-off between disturbance and information gain, i.e., to show that the more information we learn about a quantum system, the more we disturb it.

To explain this more formally, let us consider the problem of discriminating arbitray n bipartite states $|\psi_1\rangle, \dotsc, |\psi_n\rangle$ . Assume that Amandine and Bobby execute some protocol for discriminating these states, and we stop them at some point during the protocol. Let $p_1, \dotsc, p_n$ be the posterior probability distribution and $|\phi_1\rangle, \dotsc, |\phi_n\rangle$ be the corresponding post-measurement states.

Definition. We say that states $|\psi_i\rangle$ satisfy a trade-off between disturbance and information gain with constant $\eta$ if

$\eta \, \varepsilon \leq \delta$

holds in every branch when the protocol has been stopped, where

$\varepsilon = \max_k p_k - \frac{1}{n}$

is the information gain and

$\delta = \max_{i \neq j} |\langle\phi_i|\phi_j\rangle|$

is the disturbance. The largest constant $\eta$ that satisfies this inequality we call the nonlocality constant of the given states.

Intuitively, $\varepsilon$ measures how far the posterior probability distribution is from uniform, but $\delta$ measures how nonorthogonal the post-measurement states have become.

Now our main result can be stated as follows:

Theorem. Any LOCC protocol for discriminating states drawn uniformly from $|\psi_1\rangle, \dotsc, |\psi_n\rangle$ errs with probability

$p_{\text{error}} \geq \displaystyle \frac{2}{27} \, \frac{\eta^2}{n^5}$

where $\eta$ is the nonlocality constant of these states.

Our proof of this theorem is based on Helstrom bound. Our second main contribution is a systematic method for bounding the nonlocality constant $\eta$ for a large class of product bases. In particular, we obtain specific bounds for domino states, rotated domino states, and a more general family of domino-type states.

For more details see our paper.

Three myths about quantum computing — Part 3: Teleportation and superdense coding

Posted by marozols

This is the last post in the series on myths about quantum computing.

One of the most exciting things about quantum information is quantum teleportation—the ability to transmit quantum data by sending only classical bits. Superdense coding is another surprising protocol which lets you transmit two classical bits by sending only one qubit.

It is often mistakenly believed that these two features of quantum information do not have a classical equivalent. The goal of this post is to explain why this is not the case, and to clarify other related misconceptions.

Bell states

Let us first briefly discuss some simple facts that are useful for explaining how quantum teleportation works. Let $z, x \in \{0,1\}$ . Then the following four two-qubit states are orthonormal and form a basis:

$|\beta_{zx}\rangle = \dfrac{|0,x\rangle + (-1)^z |1,\bar{x}\rangle}{\sqrt{2}}$

This is known as Bell basis. One can prepare $|\beta_{zx}\rangle$ from the standard basis state $|z,x\rangle$ as follows:

$|\beta_{zx}\rangle = \mathrm{CNOT} \cdot (H \otimes I) \cdot |z,x\rangle$

One of the most important properties of Bell states is that any Bell state can be mapped to any other by applying local Pauli matrices on only one of the systems:

$|\beta_{zx}\rangle = (Z^z X^x \otimes I) \cdot |\beta_{00}\rangle = (I \otimes X^x Z^z) \cdot |\beta_{00}\rangle$

Quantum teleportation

The setting for quantum teleportation is as follows. Assume that Alice has a single-qubit quantum state $|\psi\rangle$ that she wants to send to Bob. Moreover, they have met beforehand and established a joint two-qubit quantum state

$|\beta_{00}\rangle = \dfrac{|0,0\rangle + |1,1\rangle}{\sqrt{2}}$

known as EPR pair, shared between them. Here is a schematic diagram of how quantum teleportation works:

Here “Bell” denotes the measurement in the Bell basis whose outcomes are classical bits z and x, and $Z^z X^x$ is the correction operator that Bob has to apply to recover the original state.

Quantum teleportation works because of the following identity:

$|\psi\rangle \otimes |\beta_{00}\rangle = \displaystyle \frac{1}{2} \sum_{z,x \in \{0,1\}} |\beta_{zx}\rangle \otimes X^x Z^z |\psi\rangle$

which holds for any single qubit state $|\psi\rangle$ . From this identity we see that when Alice performs the Bell measurement, she gets two uniformly random bits z and x, and Bob’s state collapses to $X^x Z^z |\psi\rangle$ which is a distorted version of $|\psi\rangle$ . Once Bob receives z and x, he can apply $Z^z X^x$ to recover $|\psi\rangle$ . Note that an adversary who intercepts z and x cannot learn anything about $|\psi\rangle$ , since both bits are uniformly random.

The usual argument why quantum teleportation is surprising, is that it allows to transmit a quantum state $|\psi\rangle$ with two continuous degrees of freedom (say, the angles in the Bloch sphere) by sending only two classical bits. This may seem quite paradoxical, since it appears as if two real numbers have been transmitted by sending just two bits. However, this is not the case at all, since the two parameters describing $|\psi\rangle$ cannot be recovered (to any reasonable degree of precision) from a single copy of $|\psi\rangle$ . For example, we know by Holevo’s theorem that one cannot learn more than one bit of information by measuring $|\psi\rangle$ .

Classical teleportation

What is the classical equivalent of the above procedure? Let us first set up some terminology and notation. Since we will be dealing with probability distributions, let

$\mu = \dfrac{1}{2} [0] + \dfrac{1}{2} [1]$

denote the uniform distribution over {0,1}. Similarly, let

$\beta = \dfrac{1}{2} [0,0] + \dfrac{1}{2} [1,1]$

be the classical version of the EPR state $|\beta_{00}\rangle$ .

Intuitively, one should think of probability distributions as a way of describing a coin that has been flipped and (without looking at it) put inside a sealed envelope. Note that one can perform operations on such coin, even though its exact state is not known. For example, by flipping the envelope around one can perform the logical NOT. One could also imagine some more complicated procedures for performing joint operations on two coins in a joint unknown state.

We will use the term pbit to refer to a probabilistic bit that describes a coin inside the envelope. Note that a pbit has one degree of freedom. However, once the envelope has been opened, the state of the coin becomes certain, i.e., either [0] or [1], so we will describe it by a deterministic bit or dbit. Note that this is analogous to how measurements work in the quantum case, except that in the classical case there is only one measurement basis—the standard basis.

Now we are ready to describe the classical teleportation. Our task is the following: we would like to transmit one pbit by sending one dbit. In other words, we want to transmit one degree of freedom per one classical bit being sent, just as in the quantum case.

At first, this might seem trivial—can’t we just send the bit over and be done? Unfortunately, not. Recall that we want to transmit a pbit or an “unobserved coin”, but we are allowed to send only a dbit. In other words, your envelope will always be opened and its content revealed, just as if you were a journalist sending an e-mail from China. Let us depict this situation with the following diagram:

Here the dark pipe represents a pbit in state $\pi$ , but the white pipe a dbit obtained by observing $\pi$ . The dashed line between Alice and Bob represents Chinese government.

To make this scheme work, we will use a shared resource between Alice and Bob as in the quantum case. A natural classical equivalent of the EPR state $|\beta_{00}\rangle$ is the probability distribution $\beta$ defined above. To preserve our pbit $\pi$ , we will XOR it with Alice’s half of $\beta$ , and send the result over to Bob. Even though the pbit $\pi$ is turned into a dbit due to Chinese government spying on Alice, Bob can still XOR it with his half of $\beta$ and recover the original pbit $\pi$ :

This indeed gives the correct result, since the original pbit essentially gets XORed with the same value twice. Intuitively, one can think of it being transmitted “back in time” through the black pipe that represents $\beta$ . Just as in the quantum case, the party who intercepts the transmitted bit learns nothing about $\pi$ , since the transmitted bit is uniformly random. In fact, this scheme is equivalent to one-time pad.

Quantum superdense coding

Quantum superdense coding is the dual protocol of quantum teleportation (this can be made more precise by considering coherent communication). It allows to send two classical bits by transmitting a single qubit and consuming one shared EPR pair.

Initially Alice and Bob share an EPR state $|\beta_{00}\rangle$ . Alice encodes her two classical bits z and x in her half of $|\beta_{00}\rangle$ by performing $Z^z X^x$ . This maps the joint state of Alice and Bob to Bell state $|\beta_{zx}\rangle$ as discussed above. Then Alice sends her qubit over to Bob, who can recover both bits by performing a measurement in the Bell basis:

Quantum superdense coding works because of the following identity:

$(H \otimes I) \cdot \mathrm{CNOT} \cdot (Z^z X^x \otimes I) \cdot |\beta_{00}\rangle = |z,x\rangle$

This immediately follows from the properties of Bell states discussed above. Since all Bell states are maximally entangled, their reduced states are completely mixed, so the transmitted qubit contains no information about the two encoded classical bits z and x.

Classical “supersparse” coding

Classical superdense coding is very similar to classical teleportation, except the roles of dbit and pbit are reversed, i.e., Alice wants to transmit a dbit by sending a pbit. This seems to be even simpler than teleportation, since we are given more resources and asked to perform a simpler task! In fact, there is nothing “superdense” about this task, as it only wastes resources. In this sense it would be more appropriate to call it “supersparse” coding!

The only catch is that for complete analogy with the quantum case, the transmitted pbit should be uniformly random, so that a potential eavesdropper could learn nothing about the original message. Here is a protocol that achieves the task of transmitting a dbit b in the desired way:

Note that the only difference between this picture and the one for classical teleportation is the color of pipes.

Conclusion

Quantum teleportation should not seem more surprising than the classical one, since in both cases one degree of freedom is transmitted per one classical bit being sent. The only quantitative difference is a factor of two in the amount of resources consumed: one ebit is consumed for sending two degrees of freedom in the quantum case versus one shared random bit per single degree of freedom in the classical case. Recall that we observed the same factor-of-two difference in the case of the amount of information needed to specify a quantum versus a classical probabilistic state within the exponential state space.

Thus, given the existence of a classical equivalent, quantum teleportation should not seem too surprising. At least, no more than by a factor of two!

p.s. As Matthew Leifer has pointed out to me, these and many other analogies between quantum entanglement and secret classical correlations have been described in the paper “A classical analogue of entanglement” by Daniel Collins and Sandu Popescu.

Three myths about quantum computing — Part 2: No-cloning theorem

Posted by marozols

This is the second post in the series on myths about quantum computing.

One of the first things we learn about quantum information is that it cannot be copied. This may seem rather surprising and counter-intuitive, since classical information stored on your computer can be easily copied (in fact, it is extremely challenging to come up with methods that would prevent this). One might even conclude that there must be something special about quantum information that does not allow us to copy it.

My goal in this post is to argue that this is not the case. The main point is that classical probability distributions cannot be copied either. This observation should make the quantum no-cloning theorem seem less surprising.

Quantum no-cloning theorem

Let us consider the standard argument why quantum states cannot be copied—the main idea is that unitary transformations have to preserve inner products.

Theorem 1 (Quantum no-cloning theorem). Transformation that acts as

$|0\rangle \otimes |\psi\rangle \mapsto |\psi\rangle \otimes |\psi\rangle$

for any quantum state $|\psi\rangle$ , is not unitary.

Proof. Let $|\psi_1\rangle$ and $|\psi_2\rangle$ be two quantum states, and assume that U is a unitary operation that implements the desired transformation. Then

$U \bigl( |0\rangle \otimes |\psi_1\rangle \bigr) = |\psi_1\rangle \otimes |\psi_1\rangle$

$U \bigl( |0\rangle \otimes |\psi_2\rangle \bigr) = |\psi_2\rangle \otimes |\psi_2\rangle$

If we take the inner product of the corresponding sides of these two equations, we get

$\langle\psi_1|\psi_2\rangle = \langle\psi_1|\psi_2\rangle^2$

where we used the assumption that U is unitary. When we solve this, we get that either $\langle\psi_1|\psi_2\rangle = 0$ or $\langle\psi_1|\psi_2\rangle = 1$ . This means that using a unitary transformation we can only copy states from an orthonormal set. However, the set of all quantum states is not orthonormal, so there is no unitary transformation that would copy an arbitrary unknown quantum state. $\blacksquare$

Classical no-cloning theorem

Recall from the previous post that quantum states and classical probability distributions are not that much different. Let us see if we can come up with a no-cloning argument that would also work in the classical case.

First, observe that independent probability distributions are combined in exact same way as quantum states—using the Kronecker product. (There is nothing “quantum” about the $\otimes$ operation!) In probabilistic classical computing the set of allowed transformations are those that map probability distributions to probability distributions. Such transformations are called stochastic. In general, they do not preserve inner products, so our previous argument will not go through.

Let us consider an alternative argument, based on linearity. For simplicity, let us consider only probability distributions over {0,1}.

Theorem 2 (Classical no-cloning theorem). Transformation that acts as

$\begin{pmatrix} 1 \\ 0 \end{pmatrix} \otimes \pi \mapsto \pi \otimes \pi$

for any probability distribution $\pi$ , is not stochastic.

Proof. Let

$\pi = \begin{pmatrix} p \\ q \end{pmatrix}$

be an arbitrary probability distribution over {0,1}. We would like to have a stochastic operation that implements the transformation

$\begin{pmatrix} p \\ q \\ 0 \\ 0 \end{pmatrix} \mapsto \begin{pmatrix} p^2 \\ pq \\ qp \\ q^2 \end{pmatrix}$

for any p and q. However, this is not possible, since the above transformation is clearly not linear. $\blacksquare$

Note that the only property we needed in this proof was linearity, so one can use exactly the same argument also for the quantum case.

Three myths about quantum computing — Part 1: Exponential size state space

Posted by marozols

This is the first post in the series on myths about quantum computing. In this post I will discuss the first misconception about quantum computers—that the exponential size of their state space is the main feature that distinguishes them from their classical cousins—and explain why this should not be used as an argument to suggest that quantum computers are likely to be more powerful than the classical ones.

Consider a system S with states labelled by n-bit strings. Assume that S is initialized in all-zeroes state “00…0″ and undergoes some kind of physical evolution. Let us consider three scenarios.

Deterministic classical world

If the evolution is deterministic, then one can specify the current state of the system by giving the corresponding label. Thus, one needs n bits of information to describe the state in this case.

Quantum world

If S is a quantum system, it can be in a superposition of all possible states. To describe this superposition, one has to assign a complex number to each state. Thus, in total one has to specify 2ⁿ complex numbers (say, to some finite precision), which is exponentially more information than in the deterministic case!

If you have never heard of this before (or remember your excitement when you heard it the first time), this definitely is mind-boggling. In fact, this is often mentioned as the main obstacle for efficiently simulating quantum computers, and also as a hand-waving argument to convince wider public that quantum computers are likely to be exponentially more powerful than classical ones.

Probabilistic classical world

One should not get too excited about the above observation, but instead think more carefully whether this comparison of deterministic and quantum computers is fair. Since the output of a quantum computer is intrinsically probabilistic, one should be looking at probabilistic evolution in the classical case, not deterministic.

If the transitions between states of the system S are described by probabilities, then the resulting state is a probability distribution over {0,1}ⁿ. To describe such distribution, one needs to specify 2ⁿ real numbers—one for each n-bit string. This is also exponentially more information than in the deterministic case!

Thus, with this comparison the only difference in the amount of information needed to describe classical and quantum states is a factor of two (since probability can be specified by a single real number whereas two real numbers are needed to specify one complex quantum amplitude).

Conclusion

The fact that an exponential amount of information is needed to describe the state space of a particular computational model does not immediately imply that it is exponentially more powerful. To be more specific, let us consider the classes of decision problems that can be solved in polynomial time by the three computational models discussed above:

The following inclusions are trivial:

$\mathrm{P} \subseteq \mathrm{BPP} \subseteq \mathrm{BQP}$

However, as of now, none of these inclusions is known to be strict.

Thus, one should not use the exponential size of the state space as an argument to claim that quantum computers are likely to be hard to simulate by deterministic classical computers, since the same argument could also be used in favor of probabilistic classical computers.

To me it seems that the main difference between probabilistic and quantum computers is the underlying field of numbers (non-negative real numbers versus complex numbers). It is a major open problem to show if this subtle difference can be used to separate the corresponding two complexity classes.

Three myths about quantum computing

Posted by marozols

In this series of posts I will discuss some misconceptions about quantum computing.

One often hears people saying that quantum physics is “strange” and that our classical intuition “breaks down” in the quantum world. I will try to argue that one should not brag about the weirdness of quantum mechanics without carefully investigating the corresponding phenomena in the classical world. In fact, many quantum phenomena no longer seem surprising once their lesser cousins in the classical probabilistic world are understood.

To illustrate my point, I will consider three basic properties of quantum information

and discuss how they translate to the classical case.

These topics are usually covered in the first class of an introductory quantum computing course, so none of what I discuss should come as a surprise to somebody who has taken such a course or read an introductory textbook on the topic. However, I have to admit that I was equally shocked both, when I learned these basic facts about quantum information in class, as when I later realized that they have a corresponding classical counterpart.

I would like to acknowledge all my “non-quantum” friends with whom I have had conversations about quantum physics. I would probably still believe in these misconceptions if I had not tried to explain you in simple terms why quantum physics is supposed to be so strange. Maybe it is not so strange after all…

p.s. For those of you who have never attempted to explain what you are doing to somebody who does not have a PhD degree in your area of expertise, consider the following three quotes by the founders of quantum mechanics:

Most of the fundamental ideas of science are essentially simple, and may, as a rule, be expressed in a language comprehensible to everyone.
—Albert Einstein

The physicist may be satisfied when he has the mathematical scheme and knows how to use it for the interpretation of the experiments. But he has to speak about his results also to non-physicists who will not be satisfied unless some explanation is given in plain language. Even for the physicist, the description in plain language will be the criterion of the degree of understanding that has been reached.
—Werner Heisenberg

If you cannot—in the long run—tell everyone what you have been doing, your doing has been worthless.
—Erwin Schrödinger

Mamuta memuāri

math, music, me

SIC-POVM sickness

Ctrl+Z for Mathematica!

Nonlocality without entanglement

Three myths about quantum computing — Part 3: Teleportation and superdense coding

Three myths about quantum computing — Part 2: No-cloning theorem

Three myths about quantum computing — Part 1: Exponential size state space

Three myths about quantum computing

Follow “Mamuta memuāri”