Questions tagged [quantum-computing]
Quantum computation and computational issues related to quantum mechanics
398
questions
88
votes
2
answers
12k
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 ...
user1338
80
votes
8
answers
44k
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 ...
- 921
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 ...
- 13.7k
47
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
...
- 13.6k
42
votes
2
answers
6k
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 ...
- 807
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 ...
- 6,782
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 ...
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 ...
- 475
31
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) ...
- 4,788
31
votes
2
answers
5k
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 ...
- 3,768
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 ...
user1338
29
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 ...
- 6,013
28
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 ...
- 283
28
votes
2
answers
1k
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 ...
- 7,629
28
votes
0
answers
523
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 ...
- 8,821
27
votes
5
answers
941
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 ...
- 2,806
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 ...
- 371
26
votes
5
answers
966
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 ...
Earl
26
votes
1
answer
581
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 ...
- 6,013
25
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 ?
- 32k
25
votes
5
answers
8k
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 ...
- 13.6k
25
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 ...
- 18.9k
25
votes
2
answers
369
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:
...
- 503
24
votes
3
answers
927
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-...
- 32k
24
votes
2
answers
160
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 ...
- 13.6k
24
votes
1
answer
509
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 ...
- 6,013
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?
- 231
23
votes
1
answer
609
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. ...
- 13.7k
23
votes
2
answers
1k
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 ...
user1338
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 ...
- 541
22
votes
3
answers
8k
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 ...
- 331
22
votes
1
answer
865
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 ...
- 6,994
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 ...
- 935
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 ...
- 1,578
21
votes
1
answer
996
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 ...
- 832
21
votes
2
answers
1k
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 ...
- 6,013
21
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{...
- 5,446
20
votes
4
answers
815
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
20
votes
2
answers
644
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 ...
- 6,013
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 ...
- 3,280
20
votes
1
answer
705
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
...
- 583
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 ...
- 401
19
votes
2
answers
651
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 ...
- 485
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 ...
- 493
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 ...
19
votes
1
answer
305
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 ...
- 431
18
votes
4
answers
977
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 ...
- 1,578
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 ...
- 361
18
votes
3
answers
408
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 ...
- 10.2k
18
votes
2
answers
244
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 ...
- 283