38 votes
Accepted

How to understand the Haar measure from a quantum information perspective?

Computations in quantum information processing are implemented by means of unitary operations. Sometimes, we need to think not about a specific unitary operation required to execute a specific ...
David Bar Moshe's user avatar
33 votes
Accepted

How to derive the CNOT matrix for a 3-qubit system where the control & target qubits are not adjacent?

For a presentation from first principles, I like Ryan O'Donnell's answer. But for a slightly higher-level algebraic treatment, here's how I would do it. The main feature of a controlled-$U$ operation,...
Niel de Beaudrap's user avatar
23 votes
Accepted

Can arbitrary matrices be decomposed using the Pauli basis?

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\...
Danylo Y's user avatar
  • 7,289
18 votes
Accepted

Why isn't there a contradiction between the existence of CNOT gate/entanglement and the no-cloning theorem?

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 ...
Mariia Mykhailova's user avatar
15 votes
Accepted

Rigorous security proof for Wiesner's quantum money

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 ...
John Watrous's user avatar
  • 5,907
15 votes
Accepted

Is there a closure property for the entire Clifford hierarchy?

It is actually possible to show that there is a simple, single-qubit operator (identified in discussion with John van de Wetering), which is a product of elements of $\mathcal C^{(3)}$ but which does ...
Niel de Beaudrap's user avatar
14 votes
Accepted

Graphical Calculus for Quantum Circuits

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. ...
Niel de Beaudrap's user avatar
14 votes
Accepted

What does it mean for a density matrix to "act on a Hilbert space $\mathcal{H}"$?

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 ...
John Watrous's user avatar
  • 5,907
14 votes
Accepted

Is the Pauli group for $n$-qubits a basis for $\mathbb{C}^{2^n\times 2^n}$?

Yes, the set of tensor products of all possible $n$ Pauli operators (including $I$) form an orthogonal basis for the vector space of $2^n \times 2^n$ complex matrices. To see this first we notice ...
biryani's user avatar
  • 966
14 votes

Can arbitrary matrices be decomposed using the Pauli basis?

$\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 (...
glS's user avatar
  • 24.9k
13 votes

How to derive the CNOT matrix for a 3-qubit system where the control & target qubits are not adjacent?

This is a good question; it's one that textbooks seem to sneak around. I reached this exact question when preparing a quantum computing lecture a couple days ago. As far as I can tell, there's no ...
Ryan O'Donnell's user avatar
13 votes
Accepted

How to check if a quantum circuit can be constructed for a given matrix representation?

Correct, unitarity is a sufficient and necessary condition. From Nielson and Chuang page 18: Amazingly, this unitary constraint is the only constraint on quantum gates. Any unitary matrix specifies a ...
ryanhill1's user avatar
  • 2,503
13 votes
Accepted

Minimum number of 2 qubit gates to build any unitary

Theoretical lower bound In contrast to the answer by Bertrand, I will assume that along with a $CNOT$ gate we have arbitrary single-qubit unitaries on our disposal. In this case, one can derive the ...
Nikita Nemkov's user avatar
13 votes

Why can all quantum circuits be converted into circuits that use only real matrices?

The fact that "we need work only with quantum Turing machines (QTMs) with real-valued transitions" is proved by Bernstein and Vazirani in their paper Quantum complexity theory (1993). ...
Egretta.Thula's user avatar
12 votes
Accepted

How are arbitrary $2\times 2$ matrices decomposed in the Pauli basis?

The Pauli matrices form an orthogonal basis of $\mathcal{M}_2$, this vector space can be endowed with a scalar product called the Hilbert-Schmidt inner product $$ \langle A,B\rangle=\mathrm{Tr}(A^\...
user2723984's user avatar
  • 1,066
11 votes
Accepted

How to show a density matrix is in a pure/mixed state?

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 ...
DaftWullie's user avatar
  • 58.1k
11 votes
Accepted

How is the ground state of a Hamiltonian defined?

A couple of points: The ground state is by definition the eigenvector associated with the minimum valued eigenvalue. Lets consider the Pauli Z matrix as you have. First, \begin{align*} Z = \begin{...
Arthur-1's user avatar
  • 525
10 votes
Accepted

What are the possible non-entangling two-qubit gates?

There are no other non-entangling gates in $SU(d^2)$ in any dimension $d=2,3,\dots$. Note that the global phase is irrelevant to the problem, so we lose no generality by considering non-entangling ...
Adam Zalcman's user avatar
  • 22.4k
9 votes
Accepted

Quantum states are unit vectors... with respect to which norm?

Born's rule states that $|\psi(x)|^2 = P(x)$ which is the probability of finding the quantum system in the state $|x\rangle$ after a measurement. We need the sum (or integral!) over all $x$ to be 1: \...
user1271772 No more free time's user avatar
9 votes
Accepted

How can we be sure that for every $A$, $A^\dagger A$ has a positive square root?

A matrix is positive if and only if it is Hermitian (and thus unitarily diagonalizable) and all its eigenvalues are positive (that they are real follows automatically from it being Hermitian). If this ...
glS's user avatar
  • 24.9k
9 votes

When can a matrix be "extended" into a unitary?

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. ...
DaftWullie's user avatar
  • 58.1k
9 votes

How to show a density matrix is in a pure/mixed state?

By spectral theorem density matrices are diagonizable, since they are hermitian (also they are positive semi-definite and have trace 1). That means that there is a set of $n$ non-negative eigenvalues $...
Danylo Y's user avatar
  • 7,289
9 votes
Accepted

Is there an algorithm for determining if a given vector is separable or entangled?

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 $...
DaftWullie's user avatar
  • 58.1k
9 votes
Accepted

How do I prove that the Hadamard satisfies $H\equiv e^{i\pi H/2}$?

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 ...
glS's user avatar
  • 24.9k
9 votes
Accepted

Correct Formulation of N&C Exercise 4.11 and other textbooks misquoting

The errata is correct. I had a project student who erroneously took one of these mis-quotes and she spent ages working with it, realising it didn't make sense, and subsequently proving that the stated ...
DaftWullie's user avatar
  • 58.1k
9 votes
Accepted

How do I apply the Hadamard gate to one qubit in a two-qubit pure state?

First, you should note that the Hadamaard gate is nothing more than a $2 \times 2$ Discrete Fourier Transform matrix (two-point DFT). That is the reason why, $H \bigg( \dfrac{|0\rangle + |1\rangle}{2}\...
KAJ226's user avatar
  • 13.8k
9 votes

How to check if a quantum circuit can be constructed for a given matrix representation?

Right. But when you build a quantum computer, you want to have a certain set of gates that you want to implement, and all other gates (unitary matrices) can be built from that set of gates. This is ...
KAJ226's user avatar
  • 13.8k
9 votes
Accepted

If two unitary operators commute, do their roots also commute?

If $A$ and $B$ are any two diagonalizable matrices that commute, then for any matrix function $f$ (anything in the continuous functional calculus, such as square root), $f(A)$ and $f(B)$ will also ...
Sam Jaques's user avatar
  • 2,024
9 votes

If two unitary operators commute, do their roots also commute?

It's always possible to find some square roots that commute. But it's not guaranteed that all square roots commute. If two operations commute, then you can find square roots that commute by ...
Craig Gidney's user avatar
  • 37.1k
8 votes

Quantum states are unit vectors... with respect to which norm?

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 ...
DaftWullie's user avatar
  • 58.1k

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