Skip to main content

Questions tagged [quantum-information]

Theoretical issues related to the quantum treatment of information

Filter by
Sorted by
Tagged with
8 votes
2 answers
215 views

Largest set allowing one-step unstructured quantum search

What is the largest set admitting a deterministic quantum search algorithm, for a single marked element, that operates with only a single call to the oracle? The question is interesting since Grover'...
Jamie Vicary's user avatar
10 votes
0 answers
152 views

Threshold for non-zero quantum capacity of depolarizing channels

In "Quantum-channel capacity of very noisy channels", DiVincenzo, Shor and Smolin showed that it is possible to perform quantum communication over depolarizing channels provided that the fidelity was ...
Joe Fitzsimons's user avatar
-3 votes
1 answer
173 views

Lower bounds on $Q_{\epsilon}(IP)$

I want to show that $Q_{\epsilon}(IP) \geq (1-O(\epsilon))n$, where $IP:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ is the usual mod 2 inner product. I have Nayak's lower bound, but I am not sure ...
MathematicalPhysicist's user avatar
5 votes
1 answer
180 views

Communicating a string of zeros and ones quantumly

Alice wants to communicate an arbitrary $x \in \{0 ,1\}^n$ to Bob. Alice and Bob communicate in rounds, in each round Alice (or Bob) applies a unitary transformation on his/her part and transmits a ...
MathematicalPhysicist's user avatar
11 votes
1 answer
527 views

Distinguishing between $N$ quantum states

Given a quantum state $\rho_A$ chosen uniformly at random from a set of $N$ mixed states $\rho_1 ... \rho_N$, what is the maximum average probability of correctly identifying $A$? This problem can be ...
Joe Fitzsimons's user avatar
6 votes
1 answer
141 views

Known properties of a specific class of quantum states

Recently, I have been studying a quantum protocol for the "Hidden Matching" problem that makes use of states that can be expressed as $|\psi\rangle=\frac{1}{\sqrt{n}}\sum_{i=1}^n (-1)^{x_i}|i\rangle$,...
Juan Miguel Arrazola's user avatar
7 votes
1 answer
216 views

A promise problem to decide whether two given pure quantum states are close or far apart

Consider this problem in quantum cryptography: We have two pure states $\phi_1,\phi_2$ as input and constants $0 \leq \alpha <\beta \leq 1 $, where "Yes instances" are those for which $$\left|\...
MathematicalPhysicist's user avatar
14 votes
2 answers
989 views

Complexity of optimization over unitary group

What is the computational complexity of optimizing various functions over the unitary group $\mathcal{U}(n)$? A typical task, arising often in quantum information theory, would be maximizing a ...
Marcin Kotowski's user avatar
14 votes
2 answers
1k views

Best method of Error Correction in Quantum Key Distribution

As far as I can tell, almost all implementations of QKD use Brassard and Salvail's CASCADE algorithm for error correction. Is this really the best known method of correcting errors in a shared ...
user avatar
6 votes
1 answer
422 views

Quantum capacity for ensemble of Pauli channels

In Preskill's quantum computing notes Chapter 7 approximate page 82, he shows that a Pauli channel has capacity $Q \geq 1-H(p_I,p_X,p_Y,p_Z)$ where $H$ is Shannon entropy and $p_I, p_X, p_Y, p_Z$ are ...
Martin Leslie's user avatar
10 votes
1 answer
91 views

Optimal measurement for MUBs

Let $\mathcal{B} = \{B_1, \dots, B_k\}$ be a set of Mutually Unbiased Bases (MUB) in $\mathbb{C}^n$, i.e. each $B_i$ is an orthonormal basis and for $v \in B_i, w \in B_j, i \neq j $ we have $|\langle ...
Marcin Kotowski's user avatar
5 votes
0 answers
192 views

Do the quantum communication complexity lower bounds hold when parties can send a "duplicated" qubits?

This question continues from the previous question where I mistakenly asked a question that is too general. In quantum communication complexity, we always assume that Alice and Bob have unlimited ...
Danu's user avatar
  • 763
1 vote
2 answers
364 views

Are Alice and Bob allowed to copy qubits in quantum communication complexity model?

In quantum communication complexity, we always assume that Alice and Bob have unlimited computational power and are still prove lower bounds such as the $\Omega(n)$ lower bounds of parity. What ...
Danu's user avatar
  • 763
12 votes
4 answers
1k views

Master Equations and Operator Sum Form

I'm more of a quantum optics guy than a quantum info guy, and deal mainly in master equations. I'm interested in operator-sum form, and I'd like to derive the errors in this form for a small quantum ...
qubyte's user avatar
  • 353
6 votes
1 answer
945 views

Analytic solutions in semidefinite programming (SDP)

From my experience in the application of semidefinite programming (SDP) to quantum information, I have learnt that the solution to an SDP can sometimes be expressed as an analytic formula. For example,...
Juan Miguel Arrazola's user avatar
9 votes
0 answers
115 views

Non-tomographical certification of projectors, using product states?

I'm interested in operational ways of demonstrating (with high probability of confidence, in an error-free setting) that a POVM operator on n-qubit states is a projector. Specifically, I'm interested ...
Niel de Beaudrap's user avatar
6 votes
1 answer
301 views

Proof that Entanglement Cannot Increase the Capacity of a Noiseless Classical Channel

I am aware that quantum entanglement cannot increase the asymptotic capacity of a noiseless classical channel. However, can anyone provide some type of reference in the literature that contains a ...
Vincent Russo's user avatar
11 votes
2 answers
595 views

Nonlocal Games and Quantum Communication

I'm currently on the look out for some good reference material relating non-local games with beneficial aspects in quantum communication. For instance, I am aware that non-local games are good at ...
Vincent Russo's user avatar
10 votes
4 answers
495 views

Quantum Bell-Type Inequalities

I'm curious if someone could recommend some supplementary material for gaining a deeper understanding of the paper : "Some Results and Problems on Quantum Bell-Type Inequalities - Tsirelson". ...
Vincent Russo's user avatar
5 votes
1 answer
264 views

Quantum Channel Decoding

Let a quantum channel $\Phi(\cdot)$ between two Hilbert spaces $\mathcal{H}_{in}$ and $\mathcal{H}_{out}$. What is the quantum channel $\Phi_{inv}(\cdot)$ that best reverses $\Phi(\cdot)$ ? $\forall $...
Antonio Valerio Miceli-Barone's user avatar
20 votes
1 answer
707 views

Does cryptography have an inherent thermodynamic cost?

Reversible computing is a computational model that only allows thermodynamically reversible operations. According to Landauer's principle, which states that erasing a bit of information releases $kT ...
rphv's user avatar
  • 583
8 votes
0 answers
359 views

Approximation of Quantum Channels

Background: In quantum information theory, a wide class of processes acting on stochastic quantum states can be described using the formalism of Quantum Channels: A quantum channel is a linear, ...
Antonio Valerio Miceli-Barone's user avatar
9 votes
2 answers
265 views

Polynomial algorithms for UPB (Unextendable Product Bases)

Consider a Hilbert space $H = H_1 \otimes \dots \otimes H_n$. An Unextendable Product Basis (UPB) is a set of product vectors $\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n ...
Marcin Kotowski's user avatar
27 votes
5 answers
9k views

Is there any connection between the diamond norm and the distance of the associated states?

In quantum information theory, the distance between two quantum channels is often measured using the diamond norm. There are also a number of ways to measure distance between two quantum states, such ...
Joe Fitzsimons's user avatar
21 votes
7 answers
28k views

Universities for Quantum Computing / Information?

Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research? The aim here is to collect a useful list for someone considering ...
Vincent Russo's user avatar
12 votes
2 answers
3k views

Does the trace norm of the difference of two density matrices being one imply these two density matrices can be simultaneously diagonalizable?

I believe the answer to this question is well-known; but, unfortunately, I don't know. In quantum computing, we know that mixed states are represented by density matrices. And the trace norm of the ...
Jeremy Yan's user avatar
11 votes
7 answers
2k views

Quantum Computation - Postulates of QM

I have just started (independent) learning about quantum computation in general from Nielsen-Chuang book. I wanted to ask if anyone could try finding time to help me with whats going on with the ...
Akash Kumar's user avatar
  • 1,973

1 2
3