Questions tagged [nielsen-and-chuang]

For questions about exercises or passages from the popular quantum computing textbook *Quantum Computation and Quantum Information* by Michael Nielsen and Isaac Chuang.

Filter by
Sorted by
Tagged with
2 votes
1 answer
35 views

Why do we need to reverse the order of qubits in Quantum Fourier Transform? [duplicate]

Looking at Qiskit's QFT tutorial, their implementation of QFT requires you to swap the qubits at the end (Nielsen and Chuang do this too). I'm wondering why this is the case. Can we flip the gates ...
user avatar
1 vote
1 answer
48 views

Are the eigenvalues of projectors always zero and/or one?

Nielsen and Chuang, page 87, defining projective measurements, refers to projectors with "eigenvalue m." However, exercise 2.16 on page 70 seems to imply that the eigenvalue is always one or ...
user avatar
4 votes
2 answers
163 views

The construction of every element of the Clifford group using H,S and CNOT circuits

I am trying to understand the following theorem: Every element $U\in C_n$ of the Clifford group can be constructed using $H, S, CNOT$ gates. In Nielsen and Chuang's book this is left as an exercise (...
user avatar
  • 365
4 votes
1 answer
105 views

Cost of Modular Exponentiation in Shor's algorithm

In the Shor's algorithm, we need to compute the sequence of controlled $U^{2^j}$ operations used by the phase estimation procedure, where $U$ is defined as $$ U|y\rangle=|xy\;(\mod N)\rangle\text{ ...
user avatar
  • 279
4 votes
1 answer
58 views

Understanding the 3rd step of Nielsen and Chuang's description of the quantum order-finding algorithm

In Nielsen and Chuang's description of Quantum order-finding algorithm, the 3rd step of the procedure says $$\frac1{\sqrt{2^t}}\sum_{j=0}^{2^t-1}|j\rangle|x^j\mod N\rangle \approx \frac1{\sqrt{r2^t}}\...
user avatar
1 vote
0 answers
35 views

Is there a way to use stabilizer formalism for non-computational basis input states?

In Nielsen and Chuang, exercise 10.42 is to use stabilizers to prove the teleportation circuit works as claimed. It has a footnote that it only works given a restricted class of inputs (it doesn't ...
user avatar
  • 111
2 votes
1 answer
70 views

Is there a way to prove that the number of gates in Exercise 4.22 of Nielsen and Chuang's book is the smallest possible number?

I've been going over Nielsen and Chuang's Quantum Computation and Quantum Information and I ran into Exercise 4.22, which says, Prove that a $C^{2}(U)$ gate (for any single qubit unitary $U$) can be ...
user avatar
3 votes
1 answer
99 views

What is the technique for calculating $\text{Tr}_b[{U(\rho\otimes\rho_b)U^{\dagger}}]$?

I am stuck on calculating $\mathcal{E}(\rho)=\text{Tr}_b[{U(\rho\otimes\rho_b)U^{\dagger}}]$. For example, in the case when $U$ is the CNOT matrix $$U=\begin{pmatrix} 1 & 0 & 0 & 0\\\ 0 &...
user avatar
  • 177
4 votes
0 answers
51 views

Implementing "computable phase shfits" using T Toffoli ( problem 4.1 from Nielsen and Chuang's)

I am reading/studying the famous Nielsen and Chuang's book and ran into this interesting question and I don't quite understand the $f(x)$. It says it simply maps from $m$ to $n$ bits. But don't we ...
user avatar
1 vote
1 answer
54 views

Grover search in Quantum Computation and Quantum Information (Nielsen and Chuang)

in Nielsen and Chuang's book in Box 6.1 (page 256 for 10th edition) there is a example of Grover's search algorithm for 3 qubits (2 as search space + 1 for oracle). I am currently trying to implement ...
user avatar
  • 35
1 vote
1 answer
47 views

For bipartite mixed state, if one part is pure, then the global mixed state is a product state?

In Nielsen and Chuang, the chapter about Schmidt decomposition, there is an interesting result states that for a bipartite pure state $|\psi\rangle_{AB}$, if part A is a pure state, then $|\psi\...
user avatar
  • 533
3 votes
0 answers
28 views

Proof of upper and lower bound (Gilbert-Varshamov bound) for linear code

I am trying to prove the following bounds for a $[n, k]$ code that can correct $t$ errors \begin{align} 1-H\left(\frac{t}{n}\right)\geq \frac{k}{n}\geq 1-H\left(\frac{2t}{n}\right) \end{align} where \...
user avatar
  • 800
3 votes
2 answers
53 views

Are the states in the convex decomposition of a density matrix necessarily orthogonal?

In Nielsen and Chuang's QC&QI, I do not see a statement one way or another. In Steeb and Hardy's Problems and Solutions, orthogonality is asserted. If the $p_i$ in $\sum_i p_i |\psi_i\rangle\...
user avatar
2 votes
2 answers
109 views

How to compute the unitary from the $\chi$ matrix obtained from QPT

I am trying to do quantum process tomography for one qubit and obtain the unitary for the gates that are applied on the qubit. I have studied the theory on process tomography from mike and ike and the ...
user avatar
1 vote
0 answers
106 views

Definition(s) of $\delta$ in quantum phase estimation

I read the chapter on QPE (quantum phase estimation) in Nielsen and noticed that $\delta$ is defined there as follows: $0 \leq \delta \leq 2^{-t}$, see: 5.2.1 Performance and requirements The above ...
user avatar
  • 628
1 vote
1 answer
63 views

Factoring Decision Problem - why not in P? [closed]

Nielsen and Chuang, 10th Anniversary Edition, page 142, refers to the following (classical) computation problem: Given a composite integer m and L <m, does m have a non-trivial factor less than L? ...
user avatar
5 votes
1 answer
132 views

Register size in factoring 15 using Shor's algorithm

In Nielsen and Chuang's book: Quantum computation and quantum information (2016), there is an example in Box 5.4 which shows how to factor $15$ using Shor's algorithm. I am confused about a ...
user avatar
  • 51
4 votes
1 answer
118 views

Derivation of efficiency of Phase Estimation Algorithm

In the section Performance and requirements of the phase estimation algorithm of Page 224, Quantum Computation and Quantum Information by Nielsen and Chuang In order to obtain Eq. 5.27 we have ...
user avatar
  • 279
0 votes
1 answer
102 views

Equating the state of the Phase Estimation algorithm to $\frac{1}{2^{t/2}}\sum_{k=0}^{2^t-1} e^{2\pi i\phi k}|k\rangle$

It is stated in the Phase Estimation algorithm in Page 222, Quantum Computation and Quantum Information by Nielsen and Chuang that It seems to say that taking the inverse Quantum Fourier transform of ...
user avatar
  • 279
2 votes
1 answer
81 views

When discussing error correction, what are the objects in the expression $PE_i^\dagger E_j P=\alpha_{ij} P$?

I've started reading the book "Quantum Computation and Quantum Information" by Michael A. Nielsen and Issac L. Chuang, specifically chapter 10 (about quantum error correction), and I'm ...
user avatar
  • 41
1 vote
1 answer
50 views

Making sense of the terms Polynomial and Exponential Precision in a Quantum Circuit

The quantum circuit construction of the quantum Fourier transform apparently requires gates of exponential precision in the number of qubits used. However, such precision is never required in any ...
user avatar
  • 279
1 vote
1 answer
44 views

What is meant by a "projection operator" in the book "Quantum Computation and Quantum Information"?

I've started reading the book "Quantum Computation and Quantum Information" by Michael A. Nielsen and Issac L. Chuang, specifically chapter 10 (about quantum error correction), and I'm ...
user avatar
  • 41
1 vote
1 answer
52 views

What is the physical process causing a Bell state to be shared? [duplicate]

Nielsen and Chuang, QCQI, page 57, last paragraph, says "suppose Alice and Bob share between them a Bell state." I know how to prepare a Bell state, but what would be the physical process ...
user avatar
2 votes
1 answer
40 views

Can every unitary on $\mathcal{H}\otimes \mathcal{K}$ be modelled by quantum operations on $\mathcal{H}$?

In section 8.2.3 of Nielsen and Chuang, they discuss how unitary dynamics of a system and environment arise from quantum operations (i.e. Kraus operators $E_k$ such that $\sum_k E_k^*E_k=I$). ...
user avatar
  • 1,447
5 votes
1 answer
254 views

No-cloning theorem and distinguishing between two non-orthogonal quantum states revisited

There are a couple of posts on this question, but I think they are not satisfactory. The question is Nielsen and Chuang's QCQI, Exercise 1.2, page 57, which asks "Explain how a device which, upon ...
user avatar
0 votes
1 answer
105 views

Phase estimation algorithm: Bounding of probability in Nielsen and Chuang

I am currently studying the Quantum Phase Estimation (QPE) algorithm as described in Nielsen and Chuang, pages 223-224. We have the following situation there, we have the state: $$\frac{1}{2^t} \sum\...
user avatar
  • 628
0 votes
0 answers
29 views

prove that $E(U^m_{\Delta t},e^{-2miH\Delta t})\leq m\alpha \Delta t^3$ where $U_{\Delta t}=e^{-2iH\Delta t}+O(\Delta t^3)$

Let $H=\sum_{k=1}^LH_k$ and define $U_{\Delta t}=[e^{-iH_1\Delta t}e^{-iH_2\Delta t}\cdots e^{-iH_L\Delta t}][e^{-iH_L\Delta t}e^{-iH_{L-1}\Delta t}\cdots e^{-iH_1\Delta t}]=e^{-2iH\Delta t}+O(\Delta ...
user avatar
  • 279
1 vote
1 answer
72 views

Formulation of quantum phase estimation in Nielsen and Chuang is different then from other sources?

In a chapter of Quantum Computation and Quantum Information by Nielsen and Chuang (10th edition) about quantum phase estimation I get a little confused. Namely: Before applying inverse QFT our quantum ...
user avatar
  • 35
2 votes
1 answer
128 views

Phase estimation algorithm: Modulo part in Nielsen and Chuang

In Nielsen and Chuang the explanation of phase estimation states: We have the following state: $$\frac{1}{2^{t/2}} \sum\limits_{k=0}^{2^t-1} e^{2 \pi i \varphi k}|k\rangle$$ Now we apply the inverse ...
user avatar
  • 628
4 votes
0 answers
118 views

Prove a circuit with controlled $iR_x(\pi \alpha)$ is universal for quantum computation whenever $\alpha$ is irrational

Show that the three qubit gate $G$ defined by the circuit is universal for quantum computation whenever $\alpha$ is irrational. My Observations The unitary gate on the third qubit is activated only ...
user avatar
  • 279
1 vote
0 answers
124 views

Circuit to show that Hadamard, phase, controlled- and Toffoli gates are universal

Part 1 The final output state is, $|\psi_{out}\rangle=\frac{1}{4}[|00\rangle(3S+XSX)|\psi\rangle+|01\rangle(S-XSX)|\psi\rangle+|10\rangle(S-XSX)|\psi\rangle+|11\rangle(-S+XSX)|\psi\rangle]$ When the ...
user avatar
  • 279
2 votes
2 answers
70 views

Show that there are unitaries $U_m$ such that $M_m=U_m \sqrt{E_m}$, for any measurement $M_m$ and associated POVM $E_m$

Nielsen and Chuang's QCQI, section 2.2.6, page 92, asks Suppose a measurement is described by measurement operators $M_m$. Show that there exist unitary operators $U_m$ such that $M_m=U_m\sqrt{E_m}$, ...
user avatar
5 votes
3 answers
267 views

Why does a quantum operation being trace-preserving imply that $\sum_k E_k^\dagger E_k=I$?

I am reading Nielsen Chuang Chapter 8. They say that if a quantum operation is trace-preserving, then \begin{equation} Tr\left(\sum_k E_k^{\dagger}E_k \rho\right) = 1 \end{equation} which I understand....
user avatar
  • 59
1 vote
1 answer
90 views

Prove $E(R_n(\alpha),R_n(\theta)^n)<\epsilon/3$ from $E\big(R_n(\alpha),R_n(\alpha+\beta)\big)=|1-\exp(i\beta/2)|$

where $E(U,V)=\max_{|\psi\rangle}||(U-V)|\psi\rangle ||=||U-V||$ is the error when $V$ is implemented instead of $U$. See page 196, Quantum Computation and Quantum Information by Nielsen and Chuang. I ...
user avatar
  • 279
1 vote
0 answers
22 views

$E(U_j,V_j)\leq\Delta/(2m)$ if probabilities of outcomes obtained from the approximate circuit is within a tolerance $Δ>0$

Suppose we wish to perform a quantum circuit containing $m$ gates, $U_1$ through $U_m$. Unfortunately, we are only able to approximate the gate $U_j$ by the gate $V_j$ . In order that the ...
user avatar
  • 279
4 votes
1 answer
327 views

Why does quantum distinguishability ensure no faster-than-light communication?

On page 56-57 in Nielsen and Chuang, for a proposed scenario, it's said that: if Bob had access to a device that could distinguish the four states $|0\rangle$, $|1\rangle$, $|+\rangle$, $|−\rangle$ ...
user avatar
  • 599
1 vote
1 answer
52 views

In Schumacher’s noiseless channel coding theorem, how do we get the exponents in $|0\rangle ^{\otimes n(1−p)/2}|1\rangle ^{\otimes n(1−p)/2}$?

On pg. 55 in Nielsen and Chuang, it's said that: the $|0\rangle + |1\rangle$ product can be well approximated by a superposition of states of the form $|0\rangle ^{\otimes n(1−p)/2}|1\rangle ^{\...
user avatar
  • 599
3 votes
0 answers
47 views

What does the $I$ mean when measuring ${\rm Tr}(\rho (I\otimes\sigma\otimes\cdots))$ in quantum tomography?

In Nielsen and Chuang's QCQI, I learned that the quantum tomography for n qubit can be described easily in math as we need to measure $Tr(\rho W_k),\forall k$ where $W_k\in\{I,\sigma_x,\sigma_y,\...
user avatar
  • 2,408
0 votes
1 answer
171 views

Measurement of single qubit operator $U$ which is both Hermitian and unitary with eigenvalues $±1$

Suppose we have a single qubit operator $U$ with eigenvalues $±1$, so that $U$ is both Hermitian and unitary, so it can be regarded both as an observable and a quantum gate. Suppose we wish to measure ...
user avatar
  • 279
2 votes
1 answer
54 views

Why can the Hamiltonian $H=P_x(t)X+P_y(t)Y$ make an arbitrary unitary $U=R_x(b)R_y(c)R_x(d)$?

p.281 of Nielsen and Chuang's book says that A single spin might evolve under the Hamiltonian $H = P_x(t)X + P_y(t)Y$, where $P_{\{xy\}}$ are classically controllable parameters. From Exercise 4.10, ...
user avatar
0 votes
2 answers
36 views

Why can the state $\sum_x|x, f(x)\rangle$ be written without normalization factor?

It is stated on page 32 of Nielsen and Chuang that: In our single qubit example: , measurement of the state gives only either |0, f(0)> or |1, f(1)>! Similarly, in the general case, measurement ...
user avatar
  • 599
1 vote
1 answer
45 views

Derivation of the state after applying $U_f$ in the Deutsch–Jozsa algorithm

On page 35 in Nielsen and Chuang, it's said that for the following quantum circuit implementing the general Deutsch–Jozsa algorithm: Next, the function $f$ is evaluated (by Bob) using $U_f$, giving $$...
user avatar
2 votes
0 answers
76 views

Why is the first register of $|x,y\oplus f(x)\rangle$ called "data" register?

When talking about quantum parallelism, in Nielsen and Chuang, it's said that: it is possible to transform this state into $|x, y \oplus f(x)\rangle$, where $\oplus$ indicates addition modulo 2; the ...
user avatar
1 vote
0 answers
37 views

Generalizing quantum parallelism to bits or qubits

On pg. 31 in Nielsen and Chuang, it's said that: This procedure can easily be generalized to functions on an arbitrary number of bits, by using a general operation known as the Hadamard transform, or ...
user avatar
0 votes
1 answer
49 views

Derivation of the effect of the Hadamard transform on a state |x⟩ in the Deutsch–Jozsa algorithm

On pg. 35 of Nielsen and Chuang, there's the following paragraph: By checking the cases $x=0$ and $x=1$ separately we see that for a single qubit $H|x\rangle=\sum_x (-1)^{xz}|z\rangle/\sqrt{2}$. I'm ...
user avatar
5 votes
2 answers
372 views

How does the spectral decomposition of the Choi operator relate to Kraus operators?

In Nielsen and Chuang's QCQI, there is a proof states that Theorem 8.1: The map $\mathcal{E}$ satisfies axioms A1, A2 and A3 if and only if $$ \mathcal{E}(\rho)=\sum_{i} E_{i} \rho E_{i}^{\dagger} $$...
user avatar
  • 533
5 votes
1 answer
131 views

Prove that rank one projectors have the same partial trace iff they differ by a local unitary operation

In nielsen and chuang's QCQI book, there is a theorem called Unitary freedom in the ensemble for density matrices, which states that the sets $|\psi_i\rangle$ and $|\phi_i\rangle$ generate the same ...
user avatar
  • 533
2 votes
1 answer
78 views

In Nielsen & Chuang, shouldn't $P=\sum_{i=1}^k|i\rangle\!\langle i|$ in (2.35) equal the identity?

Nielsen and Chuang define Projectors as: An operator $A$ whose adjoint is $A$ is known as a Hermitian or self-adjoint operator. An important class of Hermitian operators is the projectors. Suppose $...
user avatar
0 votes
1 answer
43 views

Why do we want the no error limit to be 1?

In a textbook by Nielsen and Chuang, there's the following paragraph: The idea of quantum data compression is that the compressed data should be recovered with very good fidelity. Think of the ...
user avatar
  • 599
2 votes
1 answer
49 views

Reason for sending numbers from 0 to $2^n − 1$ in Deutsch–Jozsa algorithm

In Nielsen and Chuang, when talking about the Deutsch–Jozsa algorithm. The Deutsch’s problem is described as the following game. Alice, in Amsterdam, selects a number x from 0 to $2^n − 1$, and mails ...
user avatar

1
2 3 4 5