Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
24
votes
3answers
891 views

Can we quantify the “degree of quantumness” in a quantum algorithm ?

Entanglement is often held up as the key ingredient that makes quantum algorithms well... quantum, and this can be traced back to the Bell states that destroy the idea of quantum physics as a hidden-...
9
votes
2answers
411 views

The complexity of Area-lawed Hamiltonians

I have recently thought about "importing" some physics-related question into quantum CS: The notion of the area-law phenomenon in Hamiltonian systems usually stands for a local Hamiltonian on some ...
22
votes
1answer
2k views

How does the BosonSampling paper avoid easy classes of complex matrices?

In The computational complexity of linear optics (ECCC TR10-170), Scott Aaronson and Alex Arkhipov argue that if quantum computers can be efficiently simulated by classical computers then the ...
10
votes
1answer
238 views

Dependent corrections in measurement-based Universal Blind Quantum Computation

In Universal Blind Quantum Computation the autors describe a measurement-based protocol which allows an almost classical user to perform arbitrary computations on a quantum server without revealing ...
22
votes
1answer
816 views

How much computational power fits into a cubic centimeter?

This question is a followup on the question about DNA algorithms asked by Aadita Mehra. In comments there, Joe Fitzsimmons said, in part: [T]he radius of the system must scale proportionately to ...
18
votes
4answers
851 views

If P = BQP, does this imply that PSPACE (= IP) = AM?

Recently, Watrous et al proved that QIP(3) = PSPACE a remarkable result. This was a surprising result to myself to say the least and it set me off thinking... I wondered what if Quantum Computers ...
15
votes
6answers
7k 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?
6
votes
2answers
354 views

Energy cost of adiabatic quantum computation

I'm not sure whether this question is completely on-topic, since it is a physics-related question. But I'll ask anyway and apologize if I'm off-topic. In Adiabatic Quantum Computation is Equivalent ...
8
votes
2answers
506 views

Understanding QMA

This question comes out of an answer Joe Fitzsimons gave to a different question. Most natural complexity classes have a one-line "intuitive description" that helps characterize core problems in that ...
5
votes
0answers
608 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 ...
20
votes
4answers
725 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
4 5 6 7
8