Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
88 votes
2 answers
11k 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
  • 5,070
79 votes
8 answers
43k views

What would a very simple quantum program look like?

In light of the announcement of the world's first programmable quantum photonic chip, I was wondering just what software for a computer that uses quantum entanglement would be like. One of the first ...
user avatar
  • 911
54 votes
3 answers
2k 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 ...
user avatar
46 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 ...
user avatar
39 votes
2 answers
5k views

Do any quantum algorithms improve on classical SAT?

Classical algorithms can solve 3-SAT in $1.3071^n$ time (randomized) or $1.3303^n$ time (deterministic). (Reference: Best Upper Bounds on SAT ) For comparison, using Grover's algorithm on a quantum ...
user avatar
35 votes
1 answer
2k views

$BQP$ vs $QMA$?

The central problem of complexity theory is arguably $P$ vs $NP$. However, since Nature is quantum, it would seem more natural to consider the classes $BQP$ (ie decision problems solvable by a ...
user avatar
34 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 ...
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 ...
user avatar
  • 475
30 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) ...
user avatar
  • 4,493
30 votes
2 answers
4k views

Quantum matrix multiplication?

It doesn't seem like this is known - but are there any interesting lower bounds on the complexity of matrix multiplication in the quantum computing model? Do we have any intuition that we can beat ...
user avatar
  • 3,698
29 votes
4 answers
6k views

If P = NP were true, would quantum computers be useful?

Suppose that P = NP is true. Would there then be any practical application to building a quantum computer such as solving certain problems faster, or would any such improvement be irrelevant based on ...
user avatar
  • 5,070
28 votes
2 answers
958 views

Approximate counting problem capturing BQP

In the black-box model, the problem of determining the output of a BPP machine $M(x,r)$ on input $x$ is the approximate counting problem of determining $E_r M(x,r)$ with additive error 1/3 (say). Is ...
user avatar
  • 7,469
28 votes
3 answers
1k views

A Notion of Monotone Quantum Circuits

In computational complexity there is an important distinction between monotone and general computations and a famous theorem by Razborov asserts that 3-SAT and even MATCHING are not polynomial in the ...
user avatar
  • 5,983
28 votes
0 answers
488 views

Adiabatic quantum computing with level crossings

Question. In adiabatic evolution, to ensure that the ground state high overlap with the unique ground state of the system (i.e. to achieve arbitrarily small error) using adiabatic theorems, it is ...
user avatar
27 votes
1 answer
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 ...
user avatar
  • 273
27 votes
5 answers
914 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 ...
user avatar
27 votes
4 answers
1k views

Quantum approximation algorithms

It is generally considered unlikely that quantum computers will be able to solve NP-complete problems efficiently. In the classical case one approach to tackle such problems is to use approximation ...
user avatar
26 votes
5 answers
874 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
25 votes
1 answer
556 views

Approximately sampling from convex polyhedrons with quantum computers

Quantum computers are very good for sampling distributions that we don't know how to sample using classical computers. For example if $f$ is a Boolean function (from $\{-1,1\}^n$ to $\{-1,1\}$) that ...
user avatar
  • 5,983
24 votes
3 answers
1k views

Graph Isomorphism and hidden subgroups

I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?
user avatar
24 votes
3 answers
917 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-...
user avatar
24 votes
2 answers
351 views

Computational complexity of quantum optics

In "Requirement for quantum computation", Bartlett and Sanders summarize some of the known results for continuous variable quantum computation in the following table: MY question is three-fold: ...
user avatar
24 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 ...
user avatar
24 votes
2 answers
144 views

What is the best lower bound for the fault-tolerance threshold in quantum computing?

It is well established that there exists a noise threshold for quantum computation, such that below this threshold, the computation can be encoded in such a way that it yields the correct result with ...
user avatar
23 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?
user avatar
  • 231
23 votes
5 answers
7k 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 ...
user avatar
23 votes
1 answer
586 views

The randomized query complexity of the conjoined trees problem

An important 2003 paper by Childs et al. introduced the "conjoined trees problem": a problem admitting an exponential quantum speedup that's unlike just about any other such problem that we know of. ...
user avatar
23 votes
1 answer
1k views

Is the 2016 implementation of Shor's algorithm really scalable?

In the 2016 Science paper "Realization of a scalable Shor algorithm" [1], the authors factor 15 with only 5 qubits, which is fewer than the 8 qubits "required" according to Table 1 of [2] and Table 5 ...
user avatar
23 votes
1 answer
486 views

Sampling satisfiable 3-SAT formulas

Consider the following computational task: We want to sample a 3-SAT formula of $n$ variables (a variant: $n$ variables $m$ clauses) with respect to the uniform probability distribution, conditioned ...
user avatar
  • 5,983
22 votes
2 answers
7k views

Oracle Construction for Grover's Algorithm

In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's ...
user avatar
  • 331
22 votes
1 answer
845 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 ...
user avatar
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 ...
user avatar
21 votes
3 answers
939 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 ...
user avatar
  • 1,568
21 votes
2 answers
966 views

PPAD and Quantum

Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other ...
user avatar
  • 5,983
21 votes
2 answers
920 views

Are there descriptive complexity representations of quantum complexity classes?

The title more or less says it all, but I guess I could add a bit of background and some specific examples I'm interested in. Descriptive complexity theorists, such as Immerman and Fagin, have ...
user avatar
  • 5,070
20 votes
4 answers
774 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 ...
user avatar
20 votes
2 answers
638 views

Bounded depth probability distributions

Two related questions about bounded depth computing: 1) Suppose that you start with n bits, and to start with bit i can be 0 or 1 with some probability p(i), independently. (If it makes the problem ...
user avatar
  • 5,983
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 ...
user avatar
20 votes
1 answer
684 views

Does cryptography have an inherent thermodynamic cost?

Reversible computing is a computational model that only allows thermodynamically reversible operations. According to Landauer's principle, which states that erasing a bit of information releases $kT ...
user avatar
  • 583
20 votes
1 answer
824 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{...
user avatar
20 votes
2 answers
1k views

Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...
user avatar
19 votes
1 answer
763 views

Problems in BQP but conjectured to be outside P

Wikipedia listed four problems that are in $BQP$ but conjectured to be outside $P$: Integer factorization; Discrete logarithm; Simulation of quantum systems; Computing the Jones polynomial at certain ...
user avatar
  • 792
19 votes
2 answers
605 views

Quantum algorithms based on transforms other than Fourier transforms

In Quantum Computation and Quantum Information by Nielsen and Chuang they say that many of the algorithms based on quantum Fourier transforms rely on the Coset Invariance property of Fourier ...
user avatar
19 votes
2 answers
2k views

Runtime of Grover's algorithm

What is the time complexity (not query complexity) of Grover's algorithm? It seems clear to me that it is $\Omega(\log(N) \sqrt{N})$ since there are $\Omega(\sqrt{N})$ iterations and each iteration ...
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 ...
user avatar
19 votes
1 answer
294 views

Is there a geometrical picture for adiabatic quantum computation?

In adiabatic quantum computation (AQC), one encodes the solution to an optimization problem in the ground state of a [problem] Hamiltonian $H_p$. To get to this ground state, you start in an easily ...
user avatar
  • 441
18 votes
4 answers
911 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 ...
user avatar
  • 1,568
18 votes
2 answers
1k views

Computation beyond unitary matrices

Just out of curiosity, if the classical computation is about permutation matrices and quantum computing is about unitary matrices (of which the permutation matrices are a subgroup), then will there be ...
user avatar
  • 361
18 votes
3 answers
392 views

Models of computation strictly between classical and quantum in terms of query complexity

It is well known quantum computers are strictly more powerful than their classical counterparts in terms of query complexity. Are there other models (natural or artificial) that are strictly ...
user avatar
18 votes
2 answers
226 views

Temporally Flat One-Way Quantum Computing

I am a physicist at heart, and so I think One-Way Quantum Computing is brilliant. In particular, Graph State Measurement-based Quantum Computing (MBQC) has been a really nice development in Quantum ...
user avatar

1
2 3 4 5
8