Theoretical issues related to the quantum treatment of information
2
votes
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 ...
7
votes
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 ...
1
vote
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 ...
0
votes
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 ...
12
votes
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 ...
0
votes
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 ...
2
votes
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 ...
7
votes
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 ...
9
votes
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 ...
-2
votes
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 ...
5
votes
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 ...
10
votes
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 ...
5
votes
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 ...
5
votes
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 ...
14
votes
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 ...
11
votes
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 ...
6
votes
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 ...
10
votes
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 ...
4
votes
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 ...
0
votes
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 ...
12
votes
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 ...
8
votes
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 ...
6
votes
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 ...
9
votes
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 ...
10
votes
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".
...
5
votes
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 ...
17
votes
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
...
8
votes
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, ...
8
votes
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 ...
14
votes
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 ...
8
votes
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 ...
10
votes
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 ...
10
votes
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 ...
