# Tagged Questions

Theoretical issues related to the quantum treatment of information

1answer
85 views

### Why spectral norms are used for computing the complexity of adiabatic Hamiltonian?

In the context of adiabatic quantum computation the spectral norm was first used in the first adiabatic paper by Farhi et. al. when he demonstrated the relation of it to the conventional quantum ...
2answers
388 views

### Is adiabatic quantum computing as powerful as qubit computing?

Much of quantum computing literature focuses on qubit-based computation. Adiabatic quantum computing is not based on qubits. I am looking for insight into any of the following. Is adiabatic quantum ...
1answer
142 views

### 1st & 2nd quantization from TCS

Last year I attended Scott Aaronson's talk Hawking Quantum Wares at the Classical Complexity Bazaar. Being intrigued by his argument that "[e]ven if quantum mechanics hadn't existed, theoretical ...
1answer
88 views

### Finding all solutions by Grover search(not superposition)

When there are multiple marked elements, grover search provides only superposition of them. If I want to find all the marked elements, not superposition, I could try this: 1) Do Grover search, get ...
1answer
162 views

### Polynomial speedups with algorithms based on semidefinite programming

This is a followup of a recent question asked by A. Pal: Solving semidefinite programs in polynomial time. I am still puzzling over the actual running time of algorithms that compute the solution of ...
1answer
275 views

### Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?

Forgive me wise men for my simple words, for I am but a noob. There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum ...
1answer
298 views

### Using MATLAB's CVX Package for Semidefinite Programming in Quantum Information

I'm attempting to formulate the semidefinite programs used in the paper "Hedging Bets with Correlated Quantum Strategies" (specifically those on page 7) into CVX so that I can play around with the ...
2answers
149 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 ...
0answers
99 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 ...
1answer
134 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 ...
1answer
137 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 ...
1answer
252 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 ...
1answer
122 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 ...
1answer
145 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 ...
3answers
271 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 ...
1answer
118 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 ...
1answer
89 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 ...
1answer
24 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 ...
0answers
157 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 ...
2answers
253 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 ...
4answers
246 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 ...
0answers
87 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 ...
1answer
228 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 ...
2answers
289 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 ...
4answers
347 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". ...
1answer
184 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 ...
1answer
472 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 ...
0answers
198 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, ...
2answers
204 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 ...
3answers
903 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 ...
6answers
5k 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 ...
2answers
795 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 ...
7answers
917 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 ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 26, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9049215912818909, "perplexity_flag": "middle"}