# Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

370 questions
Filter by
Sorted by
Tagged with
115 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 ...
16 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 ...
2k 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 ...
138 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 ...
152 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 ...
30 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?
96 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 ...
142 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 ...
98 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 ...
4k views

### Physics results in TCS?

It seems clear that a number of subfields of theoretical computer science have been significantly impacted by results from theoretical physics. Two examples of this are Quantum computation ...
82 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 ...
14 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 ...