15

Abel Molina, Thomas Vidick, and I proved that the correct answer is $c=3/4$ in this paper: A. Molina, T. Vidick, and J. Watrous. Optimal counterfeiting attacks and generalizations for Wiesner's quantum money. Proceedings of the 7th Conference on Theory of Quantum Computation, Communication, and Cryptography, volume 7582 of Lecture Notes in Computer ...


10

The best possible textbook reference at the moment is Coecke and Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press, 2017. It is written by one of the two inventors of the ZX calculus (Bob Coecke), and one of the people who has contributed the most to the development of ...


10

What is the proof that any given unitary matrix can be converted as above? Let $U$ be an arbitrary $2\times 2$ unitary matrix. This is equivalent to the rows/columns of $U$ forming an orthonormal system. Let us write a generic $U$ as $$U=\begin{pmatrix}a&b\\c&d\end{pmatrix}.$$ The constraints imposed on the coefficients $a,b,c,d$ by the requirement ...


8

First, the example that you give is not a density matrix (they must have trace 1). Second, you’re asking how to go from the matrix into an operator representation that is not unique. So, there are many ways of doing this. However, a particularly natural way of decomposing it is using the spectral decomposition. The weights are the eigenvalues and the states ...


8

The cloning theorem requires that the result of the cloning is two independent copies of the starting qubit, i.e., the state of the system in the end should be $\big(\alpha |0\rangle + \beta |1\rangle \big) \otimes \big(\alpha |0\rangle + \beta |1\rangle \big)$. This is not the state CNOT will give you. The qubits you get after applying CNOT as you ...


8

Marsl is correct, and his "hint" is really more a sketch of a solution than a hint. Rather than viewing the question or its solution as just formal algebra, you can also approach his same solution more conceptually. The conceptual reasoning is really identical to the algebra, just phrased differently. You can rely on the following two facts: 1) Trace ...


8

For any matrix $A$ we can write $$ A =\sum_{i,j,k,l}h_{ijkl}\cdot \frac{1}{4}\sigma_i\otimes\sigma_j\otimes\sigma_k\otimes\sigma_l, $$ where $$ h_{ijkl} = \frac{1}{4}\text{Tr}\big((\sigma_i\otimes\sigma_j\otimes\sigma_k\otimes\sigma_l)^\dagger \cdot A\big) = \frac{1}{4}\text{Tr}\big((\sigma_i\otimes\sigma_j\otimes\sigma_k\otimes\sigma_l) \cdot A\big) $$ ...


7

Some terminology seems a little bit jumbled here. Quantum states are represented (within a finite dimensional Hilbert space) by complex vectors of length 1, where length is measured by the Euclidean norm. They are not unitary, because unitary is a classification of a matrix, not a vector. Quantum states are changed/evolved according to some matrix. Given ...


7

"I'm looking for an explicit upper bound on the probability of successful counterfeiting ...". In "An adaptive attack on Wiesner's quantum money", by Aharon Brodutch, Daniel Nagaj, Or Sattath, and Dominique Unruh, last revised on 10 May 2016, the authors claim a success rate of: "~100%". The paper makes these claims: Main results. We show that in a ...


7

In linear algebra representation: The state of the qubit is $\alpha|0\rangle + \beta|1\rangle = \begin{bmatrix}\alpha \\ \beta \end{bmatrix}$. The Hadamard matrix is $\frac{1}{\sqrt{2}}\begin{bmatrix}1 & 1 \\ 1 & -1 \end{bmatrix}$. The state after applying a Hadamard gate can be calculated by multiplying the column vector representing the state ...


7

An observable only needs to be Hermitian, and can have any real eigenvalues. They don't even need to be distinct eigenvalues: if there are repeated eigenvalues, we say that the eigenspace for that eigenvalue is degenerate. (In the case of observables on a qubit, having a repeated eigenvalue makes the observable rather uninteresting, because absolutely all ...


7

A necessary and sufficient condition is that, given an $n\times n$ matrix $M$, you can construct a $2n\times 2n$ unitary matrix $U$ provided the singular values of $M$ are all upper bounded by 1. Sufficiency To see this, express the singular value decomposition of $M$ as $$ M=RDV $$ where $D$ is diagonal and $R$, $V$ are unitary. Now define $$ U=\left(\...


7

Imagine you have a vector that can be written in the form $$ |\psi\rangle=\sum_{i=0}^{d_A-1}\sum_{j=0}^{d_B-1}c_{ij}|i\rangle|j\rangle. $$ The coefficients can be arranged as a $d_A\times d_B$ matrix $C$, with the elements $c_{ij}$ (in your special case, you're talking about setting $d_A=d_B=\sqrt{m}$). Now, if you calculate $\rho_A=CC^\dagger$, this is ...


7

Hint: To make your induction work, write $$\eqalign{p^{\otimes n} - q^{\otimes n} & = & \left(p^{\otimes(n-1)}\otimes p \right)-\left(q^{\otimes (n-1)} \otimes q\right)\\ & = & \left(p^{\otimes(n-1)}-q^{\otimes (n-1)} \right)\otimes p+\left(q^{\otimes (n-1)} \right) \otimes (p-q)}$$ Then, use triangle inequality and finally the fact that ...


6

I guess you're looking at equations (130) and (131)? So, here, you have $|\psi\rangle=(|0\rangle|a\rangle+|1\rangle|b\rangle)/\sqrt{2}$ and $|\phi\rangle=|a| |0\rangle+|b| |1\rangle$. When it says to calculate $\langle\phi|\psi\rangle$, what it really means is $$ (\langle\phi|\otimes\mathbb{I})|\psi\rangle, $$ padding everything with identity matrices to ...


6

It is common that one refers to a density matrix (or, equivalently, a density operator) $\rho$ as acting on a particular space $\mathcal{H}$. This serves to establish the "type" of $\rho$ in computer science parlance. In particular, when there are multiple spaces under consideration, it may be helpful for a reader to know that $\rho$ corresponds specifically ...


6

Let $g_1 \cdots g_M$ be the basic gates that you are allowed to use. For the purposes of this $\operatorname{CNOT}_{12}$ and $\operatorname{CNOT}_{13}$ etc are treated as separate. So $M$ is polynomially dependent on $n$, the number of qubits. The precise dependence involves details of the sorts of gates you use and how $k$-local they are. For example, if ...


6

Let's represent $N^2$ as $2^a+b$, where $a$ is the greatest power of 2 that not exceeds $N^2$, and $b \ge 0$ (which is always possible to do - $a$ is just the number of bits in binary representation of $N^2$). Then $n = a+1$: $N^2 \le 2^{a+1}$, because otherwise $a$ would not be the greatest power of 2 that not exceeds $N^2$. $2^{a+1} \le 2N^2 = 2(2^a+b) = ...


6

This is actually a much easier problem. In the case of states, you're trying to use the PPT criterion, or others, to distinguish if $\rho$ can be written in the form $$ \rho=\sum_ip_i\sigma^A_i\otimes\sigma^B_i, $$ where $\sum_ip_i=1$ and the $\sigma^A_i$ and $\sigma^B_i$ are valid states on single sites. The difficulty actually comes from the freedom that ...


6

A density matrix $\rho$ has the properties of being Hermitian, non-negative and has trace 1. Any $2\times 2$ matrix can be written in the form $$ \rho=\frac{n_0\mathbb{I}+\vec{n}\cdot\vec{\sigma}}{2}. $$ The trace being 1 fixes that $n_0=1$, while the Hermitian property imposes that $\vec{n}\in\mathbb{R}^3$, where $\vec{\sigma}$ is the vector of the 3 Pauli ...


6

In the paper I called it the Burnside decomposition, but it looks like the standard name is the Wedderburn decomposition. That might simply have been a mistake in terminology on my part. Anyway, there are two good ways to get the summands to be $V \otimes V^*$. (Of course they are closely related.) 1) You can interpret $\mathbb{C}[G]$ as an associative ...


6

Yes, since the trace norm is the sum of the absolute value of the singular values, and the singular values can be found for each of the $a$ blocks independently.


6

Your reasoning is correct if your two Hamiltonians commute. But, as you say, it doesn't work if they don't commute. In that case, the trick is to find something that approximates the the thing you want. So, what you should really be thinking about is taking terms in the opposite order: $$ e^{iH_1t/2}e^{iH_2t/2}e^{iH_1t/2}e^{iH_2t/2}\approx(e^{i(H_1+H_2)t/2})...


6

First of all, note that the statement, as written, is wrong (or rather, it is correct only as long as the "$\equiv$" symbol is taken to mean "equal up to a phase"). An easy way to see it is by computing the determinant of $H=e^{i\pi H/2}$, which gives $-1=1$ (using $\det[\exp(A)]=\exp[\operatorname{Tr}(A)] $ for all $A$ and $\operatorname{Tr}(H)=0$). Now, ...


6

$\newcommand{\bs}[1]{{\boldsymbol #1}} \newcommand{\tildebssigma}{\tilde{\bs\sigma}} \newcommand{\bssigma}{{\bs\sigma}}$Yes, products of Pauli matrices form a basis for the set of Hermitian matrices (of dimensions that are powers of $2$). More specifically, fix an integer $n$ and let $N\equiv 2^n$, define $\bssigma\equiv(\sigma_x,\sigma_y,\sigma_y)$, and $\...


5

The numbers you are describing are very very large. To the point, it appears that they are numbers whose representation in decimal (or binary) are large enough that it there is little to no prospect of there being enough matter in the entire universe to store those numbers, in a place-value representation such as those. This being the case, no technology &...


5

Immediately, we can see that $$ A = |1\rangle\langle0| + |0\rangle\langle1|. $$ If the input and out bases are $\{|0\rangle, |1\rangle\}$, then $$ |0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad |1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \quad\textrm{and}\quad \langle0| = \begin{pmatrix} 1 & 0 \end{pmatrix}, \quad \langle1| = \begin{pmatrix}...


5

A set of $n$ vectors $V = \{\vec{v}_1, \ldots, \vec{v}_n\}$ are linearly dependant if there exists a set of scalars $a_1, \ldots, a_n$ (which are not all zero) such that $$ \sum_{i=1}^n a_i\vec{v_i} = \vec{0} $$ where $\vec{0}$ is the all-zero vector. Writing $V$ as a matrix with vectors as columns, this is equivalent to finding a solution to the matrix ...


Only top voted, non community-wiki answers of a minimum length are eligible