Skip to main content

Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
22 votes
1 answer
875 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 ...
Aaron Sterling's user avatar
48 votes
17 answers
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 ...
Joe Fitzsimons's user avatar
32 votes
2 answers
2k views

NP-intermediate problems with efficient quantum solutions

Peter Shor showed that two of the most important NP-intermediate problems, factoring and the discrete log problem, are in BQP. In contrast, the best known quantum algorithm for SAT (Grover's search) ...
Huck Bennett's user avatar
  • 4,908
18 votes
1 answer
987 views

Reading up on $BQP = BPP^{BQNC}$

What should I read to understand this problem? The power of small-depth quantum circuits. Is $BQP = BPP^{BQNC}$? In other words, can the "quantum" part of any quantum algorithm be compressed ...
Joshua Herman's user avatar
32 votes
11 answers
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 ...
Casebash's user avatar
  • 475
22 votes
1 answer
1k views

Consequences of $BQP \subseteq P/poly$?

While Adleman's theorem shows, that $\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}$, I'm not aware of any literature investigating the possible inclusion of $\mathsf{BQP} \subseteq \mathsf{P}/\text{...
Martin Schwarz's user avatar
21 votes
3 answers
1k views

Is there a Quantum equivalent of the Time hierarchy theorem ?

My favourite theorem in complexity theory is the Time hierarchy theorem. However, this was done in 1965. I wanted to know then if there was anything similar for Quantum Computing. Also, if not ...
Zelah 02's user avatar
  • 1,578
16 votes
6 answers
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?
Deyaa's user avatar
  • 544
15 votes
2 answers
1k views

Quantum analogues of SPACE complexity classes

We often consider complexity classes where we are bounded in the amount of space our Turing machine can use, for example: $\textbf{DSPACE}(f(n))$ or $\textbf{NSPACE}(f(n))$. It seems that early in ...
Artem Kaznatcheev's user avatar
14 votes
1 answer
967 views

What is known about multi-prover interactive proofs with short messages?

Beigi, Shor and Watrous have a very nice paper on the power of quantum interactive proofs with short messages. They consider three variants of 'short messages', and the specific one I care about is ...
Joe Fitzsimons's user avatar
12 votes
1 answer
774 views

What is the proof that quantum computers can efficiently simulate arbitrary quantum mechanical systems?

JBV suggested I turn some comments into a question, so here goes. Another question [1] asks about applications of QM computing. One answer [2] was "efficiently simulating quantum mechanics". ...
vzn's user avatar
  • 11k
10 votes
4 answers
776 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, ...
Artem Kaznatcheev's user avatar
5 votes
0 answers
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 ...
89 votes
2 answers
13k views

Was the reduction in Shor's algorithm originally discovered by Shor?

This is a "historical question" more than it is a research question, but was the classical reduction to order-finding in Shor's algorithm for factorization initially discovered by Peter Shor, or was ...
user avatar
54 votes
3 answers
3k views

Rigorous security proof for Wiesner's quantum money?

In his celebrated paper "Conjugate Coding" (written around 1970), Stephen Wiesner proposed a scheme for quantum money that is unconditionally impossible to counterfeit, assuming that the issuing bank ...
Scott Aaronson's user avatar
36 votes
2 answers
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 ...
Giorgio Camerani's user avatar
27 votes
5 answers
9k views

Is there any connection between the diamond norm and the distance of the associated states?

In quantum information theory, the distance between two quantum channels is often measured using the diamond norm. There are also a number of ways to measure distance between two quantum states, such ...
Joe Fitzsimons's user avatar
27 votes
5 answers
951 views

Quantum proofs of classical theorems

I'm interested in examples of problems where a theorem which seemingly has nothing to do with quantum mechanics/information (e.g. states something about purely classical objects) can nevertheless be ...
Marcin Kotowski's user avatar
26 votes
1 answer
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 ...
András Salamon's user avatar
26 votes
5 answers
1k views

Universal sets of gates for SU(3)?

In quantum computing we are often interested in cases where group of special unitary operators, G, for some d-dimensional system gives either the whole group SU(d) exactly or even just an ...
user avatar
24 votes
3 answers
1k views

Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?

Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
Jason's user avatar
  • 241
21 votes
7 answers
28k views

Universities for Quantum Computing / Information?

Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research? The aim here is to collect a useful list for someone considering ...
Vincent Russo's user avatar
20 votes
2 answers
1k views

$\ell_p$-norm preserving Turing machines

Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine. For people working ...
Marcos Villagra's user avatar
20 votes
4 answers
826 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 ...
Alexandre Passos's user avatar
19 votes
1 answer
1k views

Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$

In his 1995 paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor discusses an improvement on the order-finding part of his ...
Frédéric Grosshans's user avatar
18 votes
5 answers
3k views

Real world applications of quantum computing (except for security)

Let's assume that we have built an universal quantum computer. Except for security-related issues (cryptography, privacy, ...) which current real world problems can benefit from using it? I am ...
Piotr Migdal's user avatar
15 votes
1 answer
876 views

Is there a quantum NC algorithm for computing GCD?

From the comments on one of my questions on MathOverflow I get the feeling that the question regarding GCD being in $\mathsf{NC}$ vs. $\mathsf{P}$ is akin to the question regarding Integer ...
Turbo's user avatar
  • 13k
12 votes
1 answer
317 views

Fast classical simulation of quantum algorithms

Are there examples of cases where the classical simulation of a quantum algorithm for a problem outperforms the best previously known classical algorithm for this problem? "Outperforms" doesn't have ...
delete000's user avatar
  • 828
10 votes
2 answers
524 views

Restricting entries of unitary operators to real numbers and universal gate sets

In Bernstein and Vazirani's seminal paper "Quantum Complexity Theory", they show that a $d$-dimensional unitary transformation can be efficiently approximated by a product of what they call "near-...
Henry Yuen's user avatar
  • 3,798
10 votes
1 answer
506 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 (...
Artem Kaznatcheev's user avatar
10 votes
1 answer
322 views

Lower bounds for quantum circuits using the geodesic framework

Some of us have been reading Michael Nielsen's paper on a geometric approach to using quantum lower bounds (in brief, the construction of a Finsler metric on $SU(2^n)$ such that the geodesic distance ...
Suresh Venkat's user avatar
9 votes
1 answer
485 views

Evidence that there is some problem in BQP distinct from BPP?

Are there any evidences (1 physics, 2 mathematics AND 3 computer science) that particular problems such as integer factorization, discrete logarithm are in BQP but not in BPP? There do not seem to be ...
user avatar
9 votes
2 answers
808 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 ...
Suresh Venkat's user avatar
9 votes
2 answers
864 views

Is adiabatic quantum computing as powerful as the circuit model?

Much of the quantum computing literature focuses on the circuit model. Adiabatic quantum computing is not based on applying a sequence of unitary operators, but on changing a time-dependent ...
vzn's user avatar
  • 11k
8 votes
1 answer
467 views

Quantum Money where not even the Bank can counterfeit

The Quantum Money system proposed in "Quantum Copy-Protection and Quantum Money" has the following properties: The bank can produce bank notes in the form of quantum states. Anyone can verify that ...
Christopher King's user avatar
8 votes
2 answers
360 views

Given a subset of the hypercube and a copy translated by s, find s

Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible ...
boinkboink's user avatar
7 votes
2 answers
447 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 ...
Antonio Valerio Miceli-Barone's user avatar
7 votes
1 answer
205 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 ...
Geoffrey Irving's user avatar
7 votes
2 answers
595 views

Quantum query complexity and certificate complexity

A certificate for an input $x$ is a subset of bits $S \subseteq \{1,...,n\}$ such that for all inputs $y$, $(\forall i \in S \quad y_i = x_i) \rightarrow f(y) = f(x)$. Then $C_x(f)$ is the minimum ...
Artem Kaznatcheev's user avatar
6 votes
1 answer
254 views

Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits?

This is another attempt to formalize my former question on the topic. I'm looking for a problem for which all known classical algorithms take exponential time, but given ANY number of few qubits (...
domotorp's user avatar
  • 14k
5 votes
0 answers
192 views

Do the quantum communication complexity lower bounds hold when parties can send a "duplicated" qubits?

This question continues from the previous question where I mistakenly asked a question that is too general. In quantum communication complexity, we always assume that Alice and Bob have unlimited ...
Danu's user avatar
  • 763
5 votes
2 answers
309 views

Witness verifiable quantum advantage

Update: A slightly different version of this question has been answered here. As far as I can see, a major issue with Google's recent quantum supremacy claim is that it is hard to verify the results. ...
domotorp's user avatar
  • 14k
4 votes
6 answers
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 ...
Shane's user avatar
  • 2,233
3 votes
1 answer
104 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 ...
Omar Shehab's user avatar
3 votes
1 answer
177 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 \...
Subhayan's user avatar
  • 831
1 vote
1 answer
185 views

Is unbounded quantum fanout operation experimentally feasible?

It is known that the "unbounded quantum fanout operation" is very powerful: (See, for example, Hoyer et al. : http://theoryofcomputing.org/articles/v001a005/v001a005.pdf). In particular, it is known ...
Chris Blake's user avatar
1 vote
2 answers
364 views

Are Alice and Bob allowed to copy qubits in quantum communication complexity model?

In quantum communication complexity, we always assume that Alice and Bob have unlimited computational power and are still prove lower bounds such as the $\Omega(n)$ lower bounds of parity. What ...
Danu's user avatar
  • 763
1 vote
1 answer
138 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 ...
Geoffrey Irving's user avatar