# Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

370 questions
Filter by
Sorted by
Tagged with
24 views

### Am I manipulating the content of states when I manipulate a superposition of indices?

I posted this question on quantumcomputing forum but I think maybe is more adequate to cstheory. I'm trying to understand something, I have been reading some papers about Grover's iterator, especially ...
229 views

### What are some “must-read” papers for someone getting into Quantum Cryptography?

I'm a graduate student that just finished a first course on quantum computation. I've also done a graduate-level course in (classical) cryptography. I'm interested in Quantum Cryptography and would ...
26 views

### What is known about the stabilizer rank of this simple state?

Consider the uniform superposition of all length-$n$ bit-strings of Hammming weight $w$, $$|\phi_w\rangle =\sum_{x\in \{0,1\}^n,|x|=w} |x\rangle$$ What is known or conjectured about the stabilizer ...
146 views

### The complexity of LH with constant gap

Kitaev's quantum equivalent of the Cook-Levin Theorem, provides a polynomial time classical reduction from a QMA verification circuit to a sum $H$ of local hamiltonians, such that the least eigenvalue ...
170 views

### Pursuing Theoretical Computer Science after CS major

So I am currently a sophomore majoring in Computer Science. In the Data Structures course that I am currently studying, I studied the basics of complexity of a program and big O-notation, etc. That ...
33 views

### Which algorithm for linear programming is suitable for the context of quantum computing?

There are two major types of algorithms for linear programming : extreme point based, interior point based. Which will be suitable for quantum computing?
103 views

### Quantum complexity of TQBF with an untrusted oracle

This is a follow up to Quantum complexity of TQBF, trying to model the situation where we have good heuristics. Let $L$ be the language of true, fully alternating totally quantified boolean formulas ...
149 views

### Quantum complexity of TQBF

There is no classical algorithm for $n$-bit TQBF with better than $O(2^n)$ complexity. Is that also the best known bound for quantum algorithms / circuits? Edit: As pointed out by Huck Bennett, in ...
110 views

### What are the general direction and target question in the field of quantum error correction?

After quantum error correction was introduced in mid '90s, in subsequent years many of the classical analogues regarding the structure of code (such as singleton bound, GV bound etc) were obtained in ...
97 views

### Survey on Quantum error correction

Are there any standard recent survey articles on quantum error correction (and may be including fault Tolerant computing)? The most standard ones that many people refer to are this and this. Both of ...
19 views

### Direct Diffie-Hellman by Shor's algorithm

Shor's algorithm appears to be capable of finding discrete logarithm even if the modulus is composite. Does the algorithm implicitly compute the Carmichael Lambda which goes in the exponent or somehow ...