# Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

401 questions
Filter by
Sorted by
Tagged with
346 views

### Reference request: number-theory-free proof that maximal stabilizer groups determine unique states

Context. I am writing on topics such as the Gottesman-Knill theorem, using Pauli stabilizer groups, but in the case of d-dimensional qudits — where d may have more than one prime factor. (I ...
• 8,821
2k views

### Consequences of $SAT \in BQP$

As a TCS amateur, I'm reading some popular, very introductory material on quantum computing. Here are the few elementary bits of information I've learned so far: Quantum computers are not known to ...
• 6,842
5k views

### Shor's factoring algorithm help

I'm having a little trouble fully understanding the final steps of Shor's factoring algorithm. Given an $N$ we want to factor, we choose a random $x$ which has order $r$. The first step involves ...
• 283
760 views

### Bounding the gap between quantum and deterministic query complexity

Although exponential separations between bounded-error quantum query complexity ($Q(f)$) and deterministic query complexity ($D(f)$) or bounded-error randomized query complexity ($R(f)$) are known, ...
• 10.3k
456 views

### Duality computers

There is a lot on the internet about quantum computers and how they could factor integers. However, there is a type of computer which also uses the principles of quantum mechanics, which can be used ...
501 views

### Span programs, witness size, and certificate complexity

A span program is a linear-algebraic way of specifying a boolean function introduced here. Recently, this model was used to show that the negative adversary method provides a tight characterization (...
• 10.3k
605 views

### Interactive Proofs via Postselection?

Define the computational model MPostBQP to be identical to PostBQP except we allow polynomially many qubit measurements before the post-selection and final measurement. Can we give any evidence ...
• 800
265 views

• 3,290
6k views

### Ternary (and beyond) computation and quantum computing?

Binary math is at the heart of most computing, in large part because of the ease with which two energy states can be achieved. I have always thought that having more states could improve computing ...
• 2,233
614 views

### Learning quantum CS [duplicate]

Possible Duplicate: What is the quantum computational model? What is the best way to study quantum branch of CS for the person with rather advanced background in classical CS? Does one need to ...
9k views

### Quantum computing project ideas

I'm undergraduate computer science student and I'm currently planning for my graduation project. I need some ideas in quantum computing field. any help?
• 544
2k views

### What is the quantum computational model?

I have occasionally heard people talk about quantum algorithms and about states and the ability to consider multiple possibilities at once, but I have never managed to get someone to explain the ...
• 475
817 views

### Is there an equivalent to derandomization for quantum algorithms?

With some randomized algorithms you can derandomize the algorithm, removing (at a possible cost in run time) the use of random bits and maximizing some lower bound on the objective (usually computed ...
• 1,459