Theoretical issues related to the quantum treatment of information

learn more… | top users | synonyms

-4
votes
0answers
34 views

Why does 9 qubit Shor code have distance 3? [migrated]

Distance of a Stabilizer code($S$) is defined by minimum weight of an element in $N(S)-S$ . Why 9 qubit Shor code has distance 3? Is there a way to directly see $N(S)-S$ from $S$?
4
votes
1answer
50 views

Is it possible to MAC a quantum state with a classical key under reasonable assumption?

Assume that classical one-way functions secure against quantum adversaries exist. Is it possible, given a quantum state $Q$ and classical secret key $k$, produce a quantum state $AuthQ$ such that: ...
2
votes
1answer
72 views

Is it possible to encrypt quantum states under reasonable assumptions?

Is it possible to encrypt a quantum state, such that a $BQP$ attacker who does not know the secret key cannot obtain any information about the original state, but a $BQP$ decryptor with the key can ...
0
votes
0answers
52 views

In the algorithm of quantum phase estimation, how the deviation of unitary operation affect the result of obtained phase?

Given an unitary operation $U$ and one of its eigenvector state $|u\rangle$ such that $U|u\rangle=e^{2\pi i \phi}|u\rangle$, the algorithm of quantum phase estimation can be utilized to estimate the ...
0
votes
0answers
65 views

Quantum Data Compression Schemes

Quantum Computation has given speedups in algorithms, and even though we do not know the exact relationship of $BQP$ to $NP$ -we have many algorithms in quantum computation that give speedup in ...
3
votes
0answers
76 views

Quantum GCD circuit: On reversibility and clearing ancillae

Originally posted on PHYS, however, obviously it has more to do with CS I am currently trying to implement a circuit for computing the greatest common divisor in the Quantum Computing Language. In my ...
1
vote
1answer
47 views

How the hardness of hidden subgroup problem in $S_n$ changes as the order of the subgroup grows?

In Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In this paper it is showed that no hidden subgroup algorithm can distinguish the trivial ...
0
votes
0answers
40 views

Measurements in non-Abelian hidden subgroup algorithms

More than one measurement take place in a non-Abelian hidden subgroup algorithm. In this question, I would like to verify whether my understandings about them are right. I am using Andrew Childs' ...
0
votes
0answers
18 views

Choice of basis for non-Abelian hidden subgroup problems

I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et al. In section 1.1 it is said that, It is still possible that a clever choice of basis ...
3
votes
2answers
94 views

Is there any hidden subgroup of a symmetric group which can be efficiently determined?

There have been a number of cases where efficient hidden subgroup algorithms have been found for specific non-Abelian groups with very specific structures. Why haven't we found any efficient quantum ...
3
votes
0answers
68 views

Why hidden subgroup problem is easy for very large subgroup?

I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et al. On page 2, it is said that solving the hidden subgroup problem becomes very easy when the ...
0
votes
2answers
91 views

Entropy inequality of joint von Neumann entropy given some marginal inequalities

Assume that I have a pure, multipartite state $\omega_{ABCD}$ and a unitary $U(\omega_{ABCD})=\tau_{ABCD}$. The effect of $U$ on $\omega$ results in $$ S(\omega_B)<S(\tau_B) $$ and $$ ...
0
votes
1answer
52 views

Question about discarding the second register in the standard approach of hidden subgroup algorithm

My questions: What does discarding the second register mean for the standard approach of hidden subgroup algorithm? Why does discarding let the first register end up in a mixed state? My ...
-3
votes
1answer
125 views

Dimension of the Fourier transform for $S_5$ [closed]

My question: What is the dimension of the Fourier transform for $S_5$? My effort: The dimensions of the seven irreps of $S_5$ are $1,1,4,4,5,5,6$. According to the notes of Andrew Childs, the ...
0
votes
0answers
72 views

Fourier transformation of the automorphism group of a graph

Following is an example of permutation cycle graph $\Gamma$ for a given permutation $\pi = \left(1\text{ } 2\right) \left(3\text{ } 4\text{ } 5\text{ } 6\right)$. The adjacency matrix $A$ is given ...
1
vote
0answers
47 views

First register in the hidden subgroup representations of Simon's and graph isomorphism problems

The Simon's problem involves a function which takes binary strings as inputs. One seeks to find the period of the function which acts on those inputs. In the standard method, the first register has ...
12
votes
1answer
202 views

Generating “infinite” randomness from a constant number of sources

I recently came across a paper by Coudron and Yuen on randomness expansion using quantum devices. The main result of the work is that it is possible to generate "infinite" randomness from a constant ...
0
votes
0answers
39 views

Exponential acceleration of quantum metropolis sampling

In this paper (http://arxiv.org/abs/0911.3635), they propose a quantum MCMC algorithm. My question is whether they achieve exponential (or polynomial) acceleration compared with the classical ...
0
votes
0answers
48 views

Complexity of quantum shuffle transform

I define the shuffle permutation matrix by quoting from Hoyer first. Shuffle permutation matrix: The shuffle permutation matrix of dimension $mn \times mn$, denoted by $\Pi_{mn}$ as shorthand for ...
3
votes
0answers
51 views

Does simulating chiral gauge theories lie within BQP?

In theoretical physics, there is a branch of quantum field theory dealing with chiral gauge theories. It has been conjectured by Feynman [1] and others that all quantum field theories can be simulated ...
1
vote
1answer
161 views

How does one determine if a mixed bipartite quantum state is entangled or not?

My question is based on the structure of the NP-hardness proof in section 6 (page 17) of this paper, http://arxiv.org/pdf/quant-ph/0303055v1.pdf Mathematically one can think of being given a ...
5
votes
1answer
92 views

Shor's quantum error correction code with unknown basis

$\newcommand{\ket}[1]{\lvert #1 \rangle}$I've met a problem in quantum secret sharing which involves the use of a quantum error-correction code. (let's make it simple to be the 9-qubit Shor code) In ...
-7
votes
1answer
286 views

Travelling sales man with Quantum Computers [closed]

I know that it takes billions of years to solve the travelling sales man when n = 25 (Number of cities). I am wondering how fast can a quantum computer solve the travelling sales man problem (for ...
10
votes
4answers
438 views

The utility of Renyi entropies?

Most of us are familiar with — or at least have heard of — the Shannon entropy of a random variable, $H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr]$, and all the related information-theoretic ...
2
votes
0answers
84 views

Proofs to verify quantum states without revealing their description

Consider the following function $$f_s: k \rightarrow \lvert \psi_k \rangle$$ where $s,k$ are bit strings, and $\lvert \psi_k \rangle$ is a $n$-qubit state. Assume the function is a one-to-one ...
0
votes
0answers
27 views

Hardness of finding similar (quantum) states

Consider a quantum state $\lvert \psi \rangle$, we know from the no cloning theorem, that it cannot be perfectly cloned. Also, loosely speaking, that it can be imperfectly cloned s.t. one can produce ...
3
votes
1answer
118 views

How well can an arbitrary (unknown) quantum state be imperfectly cloned?

How well can an arbitrary unknown (quantum) state $\rvert \psi \rangle = \alpha\rvert 0 \rangle + \beta \rvert 1 \rangle$, be imperfectly/approximately cloned? Given an unknown state ${\rvert \psi ...
3
votes
1answer
230 views

Why do we need a sphere to graphically represent a qubit? [closed]

Bloch sphere is a common visualisation of possible qubit values, but I fail to understand why do we need a sphere to represent them. Assuming we want to represent the single qubit a|0> + b|1> ...
-1
votes
1answer
78 views

The Arrow of Time in a Non-Physical Realm [closed]

Could there be a logically consistent theory supporting the transmission of non-physical information to a point in time previous to the time it was sent using a computer network (quantum theory, etc)? ...
1
vote
1answer
87 views

Why are sub-normalized states studied in quantum computation?

By basic postulates of QM, any state of a system is described by a normalised density operator. Now i fail to see why people study sub-normalized states ( e.g.: In generalised fidelity etc). I'd be ...
1
vote
1answer
168 views

What is the Quantum Cheshire Cat experiments' import to Quantum Computing?

What is the significance of the Quantum Cheshire Cat to Quantum Computing? To recap, the Quantum Cheshire Cat experiment proved it was possible to separate a neutrons' spin from the neutron. Or, in ...
4
votes
4answers
885 views

Factoring as a decision problem

I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision ...
-2
votes
1answer
116 views

Prerequisites for theoretical computer science [closed]

I am a freshman and a Computer Science major,I have a very poor understanding in the area of electrical and electronics.I want to pursue a career in theoretical computer science esp. Quantum ...
5
votes
1answer
546 views

Applications of HHL's algorithm for solving linear equations

In HHL's algorithm for solving a system of linear equations (HHL = Harrow, Hassidim and Lloyd) the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge ...
7
votes
0answers
52 views

Explicit error bounds on the abelian hidden subgroup problem

What are some explicit forms for the error probability in the typical quantum abelian hidden subgroup algorithm as a function of oracles queries? Ettinger, Hoyer, and Knill give a result that the ...
19
votes
2answers
488 views

Quantum algorithms based on transforms other than Fourier transforms

In Quantum Computation and Quantum Information by Nielsen and Chuang they say that many of the algorithms based on quantum Fourier transforms rely on the Coset Invariance property of Fourier ...
13
votes
1answer
291 views

Oracular separations between poly- and log-depth quantum circuits

The following problem appears in Aaronson's list Ten Semi-Grand Challenges for Quantum Computing Theory. Is $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ In other words, can the "quantum" part of ...
0
votes
1answer
173 views

Quantum Fourier Transform question regarding measurement

When we use the quantum fourier transform, for a function, the output is entangled, so if a measurement is made on the output, the result may not be that of the function that one wanted in the first ...
2
votes
0answers
49 views

How the errors of the measured quantities of an adiabatic Hamiltonian are inversely proportional to the square root of the number of measurements?

I am going through the paper, Solving the graph-isomorphism problem with a quantum annealer, by Hen et. al. In the last line of the second paragraph of the second column of page 2, it says, Since ...
4
votes
2answers
351 views

Are two-qubit unitaries necessary for universal quantum computation?

I was going through Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians by Daniel Nagaj. In the first sentence of the fifth paragraph on the fourth page, he said, Two-qubit ...
11
votes
1answer
173 views

Any evidence that Linial, Shraibman lower bound on quantum communication complexity is not tight?

As far as I know, the factorization norm lower bound given by Linial and Shraibman is essentially the only lower bound known for quantum communication complexity (or at least it subsumes all others). ...
1
vote
1answer
249 views

Running Simon's algorithm on D-wave machine

I was wondering whether Simon's algorithm could be run on a D-wave machine. The Simon's algorithm is a promise problem. On the other hand the D-wave machine can run only quadratic unconstrained ...
0
votes
0answers
75 views

The quantum capacity of a trace-decreasing CP map

Assume a qubit quantum channel (trace-preserving CP (==completely positive) map) $\mathcal{N}:C^2\to C^2$ whose quantum capacity is known. Now I construct a new channel $\mathcal{M}:C^2\to C^{2+n}$ ...
-6
votes
1answer
174 views

Is the sub-bit model of quantum computation equivalent to other models? [closed]

In a comment to this question Peter Shor asked me for a reference about the third described in the question point of view, namely, that quantum computers can be described as computers that can ...
4
votes
0answers
100 views

Games where $\omega(G) < \omega^*(G) < \omega^{ns}(G) < 1$?

A two player game $G = (I,O,V,p)$ is such that, if two non-communicating players Alice and Bob are given questions $(x,y)\in I^2$ drawn from the probability distribution $p$, they are supposed to ...
4
votes
2answers
285 views

Simulation of every physical quantum system on quantum computer

Let me quote from the section 9.3 of Classical and Quantum Computation by Kitaev, Shen and Vyalyi. With high confidence, we may claim that every physical quantum system can be efficiently ...
2
votes
0answers
706 views

From CHSH inequality to CHSH game

I have been going through Certifiable quantum dice: or, true random number generation secure against quantum adversaries by Umesh Vazirani and Thomas Vidick. They have used entangled particles as ...
0
votes
1answer
85 views

Confusion with the proof of constraints for a particular adiabatic quantum evolution

[This might be related to one of my previous unanswered questions.] This proof belongs to the paper, How to Make the Quantum Adiabatic Algorithm Fail by Edward Farhi, Jeffrey Goldstone, Sam Gutmann ...
3
votes
1answer
87 views

Questions about Farhi's pre-Adiabatic paper

I have been going through Eddie Farhi's 6-pages long pre-Adiabatic paper, An Analog Analogue of a Digital Quantum Computation. I guess I understand most of the math and physics but I am struggling ...
6
votes
0answers
163 views

Local Hamiltonian and combinatorial search problems

I was going through the PhD thesis of Daniel Nagaj. At the beginning of chapter two he indicated a relation between the local Hamiltonian perspective of adiabatic quantum computation and combination ...