Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
9
votes
3answers
801 views

1-way Quantum Finite Automata Example Question

I'm attempting to clarify my understanding in the example presented in Section 2.2 of 1-way Quantum Finite Automata: Strengths Weaknesses and Generalizations (this alternative link may also be useful)....
13
votes
0answers
301 views

Is there any known nontrivial result on QIP systems having a space-bounded verifier?

Is there any known nontrivial result on quantum interactive proof (QIP) systems having a space-bounded verifier? The only paper I know is An application of quantum finite automata to interactive ...
6
votes
1answer
472 views

Quantum algorithms for determining whether two sets intersect

Grover's algorithm is a quantum algorithm that is able to locate a special record in an $N$ element unsorted database in $\Theta(\sqrt{N})$ time. What quantum algorithms are known to determine whether ...
10
votes
1answer
404 views

Uniform way of quantifying “branching” in nondeterministic, probabilistic, and quantum computation?

The computation of a nondeterministic Turing machine (NTM) is well known to be representable as a tree of configurations, rooted at the starting configuration. Any transition in the program is ...
15
votes
5answers
577 views

Software package for decomposing quantum circuits

Is there any software package allowing decomposition of unitaries from $U(2^n)$ into quantum circuits over a predefined universal gate set?
1
vote
0answers
149 views

Is there a lower bound for the decisional Grover search problem?

What is known about the decisional version of the search problem? By decisional version of the search problem, I mean the problem in which you wish to determine whether there are $0$, or exactly $t$ ...
11
votes
1answer
115 views

Decidability/algorithm for checking universality of a quantum gate set

Given a finite set of quantum gates $\mathcal{G} = \{G_1, \dots, G_n\}$, is it decidable (in computation theoretic sense) whether $\mathcal{G}$ is a universal gate set? On one hand, "almost all" gate ...
15
votes
0answers
73 views

Lower bounds for quantum circuits using the geodesic framework

(this question is a crosspost from cstheory. I've incorporated the one answer there into the question) Some of us have been reading Michael Nielsen's paper on a geometric approach to using quantum ...
10
votes
1answer
262 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 ...
15
votes
5answers
571 views

What is the complexity class for quantum subroutines taking in arbitrary quantum states as inputs?

The complexity class BQP corresponds to polynomial time quantum subroutines taking in classical inputs and spitting out a probabilistic classical output. Quantum advice modifies that to include copies ...
19
votes
3answers
828 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 ...
18
votes
3answers
377 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 ...
27
votes
1answer
4k 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 ...
0
votes
0answers
383 views

Is it possible to add quantum physics theory to traditional machine learning algorithms to get more accurate results

Lets suppose your data set includes locations in several dimensions and the kind of entity which is the class of the data set, is there other kind of information you need to add (such as times, ...
18
votes
2answers
206 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 ...
24
votes
2answers
127 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 ...
4
votes
1answer
347 views

Quantum cellular automata

This questions is cross-posted from MathOverflow A little background: As far as I know there is no standard definition of a quantum cellular automaton in the literature. Different authors use ...
10
votes
2answers
382 views

Does there exist a quantum algorithm ala Deutsch's algorithm that computs AND instead of XOR?

Deutsch's algorithm is a well known quantum computing $f(0) + f(1)\mod{2}$ with only one one evaluation of $f$. If we replace $+$ with $\cdot$ the problem seems to become rather different. My ...
14
votes
1answer
756 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 ...
7
votes
0answers
193 views

Are the minimal quantum and classical span programs the same?

A span program is a linear-algebraic way of specifying a boolean function introduced here which has found recent application in quantum query complexity. A span program for a function $f: \{0,1\}^n \...
8
votes
4answers
3k views

Von Neumann architectures and quantum computing

Can you do quantum computing in a von neuman architecture? If not, why? What is the constraint? If you control a qbit, can a quantum computer use the von neuman architecture? Thanks.
17
votes
2answers
397 views

Is PARITY in QAC_0 (if that even makes sense)

As is well known PARITY cannot be done in poly-sized constant-depth circuits, and in fact const-dept circuits require EXP number of gates. What about QUANTUM circuits? a) Can PARITY be done with a ...
28
votes
2answers
931 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 ...
-6
votes
1answer
368 views

Quantum complexity class vs classical complexity class [closed]

What is the relation between BQP complexity class and P and NP?
13
votes
2answers
619 views

One-shot quantum hitting times

In the paper Quantum Random Walks Hit Exponentially Faster (arXiv:quant-ph/0205083) Kempe gives a notion of hitting time for quantum walks (in the hypercube) that is not very popular in the quantum ...
17
votes
1answer
484 views

Using the extra power of the negative adversary method

The negative adversary method ($ADV^\pm$) is an SDP that characterizes quantum query complexity. It is a generalization of the widely used adversary method ($ADV$), and overcomes the two barriers that ...
20
votes
2answers
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 ...
1
vote
1answer
207 views

Computational Library to compute Quantum Cluster States

I want to write a simulator for a quantum computing model that I am working on and I was wondering what would be the correct library / implementation strategy to implement quantum cluster states? ...
1
vote
1answer
298 views

Branch prediction in quantum algorithms

Are there any good examples of branching efficiency / prediction in quantum algorihms? Specifically suppose I have a set of CNOT gates one after the other that have the control line on the same line ...
16
votes
1answer
815 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 ...
6
votes
3answers
671 views

Why does the Complexity Class PostBQP makes proving PP greater than or equal to QMA easier?

PP was proved greater than QMA in by Kitaev and Watrous 2000 - Parallelization, Amplification, and Exponential Time Simulation of Quantum Interactive Proof Systems. Later Aaronson proved that PostBQP ...
11
votes
1answer
476 views

Why must QMA complete problems be promise problems?

I'm reading Watrous's excellent survey paper on paper on quantum complexity theory. In it he states that it would be surprising if a QMA -complete problem were found to have a vacuous promise (I.e. Be ...
28
votes
2answers
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) ...
32
votes
11answers
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 ...
4
votes
1answer
695 views

Qubits and permutation symmetry

To put it straight - are qubits fermions, bosons or else? For example, the Bell states that are frequently used in quantum computations have different symmetry (00 + 11 is symmetric, 10 - 01 is ...
2
votes
0answers
873 views

Are quantum computers turing complete? [closed]

I have gained some interest in quantum computing ever since I have been reading Scott Aaronson's blog. The fact that using this computational model, you would be able to factor integers in polynomial ...
10
votes
2answers
429 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-...
5
votes
1answer
382 views

How efficiently can a 1-sparse Hamiltonian be simulated (quantum mechanically)?

In quantum computation there is a fair amount of interest in the task of simulating quantum physics. One instance of this is the problem of simulating the evolution of a system under the action of ...
7
votes
4answers
444 views

Is there a standard definition of Quantum Randomness?

I hope this question is not too vague. For classical bit generators there is the classical statistical definition which (informally) states that a source is ideally random if its output $X_1,X_2,\...
34
votes
2answers
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 ...
-8
votes
1answer
436 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 ...
10
votes
1answer
451 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 (...
9
votes
3answers
575 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 ...
2
votes
2answers
378 views

Time-entanglement phenomenon

Please let me mention certain idea here, although it is probably vague (and new, at least as related to experiment mentioned below, as far as I know). The general notion of algorithm is model of ...
1
vote
2answers
354 views

Quantum evolutions

I was reading Quantum Computation Explained to my Mother. While considering the following problem: Problem 1 Suppose we are given a mysterious boolean operator F (a black box) which takes one ...
7
votes
2answers
466 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 ...
9
votes
1answer
681 views

Lower bounds on the Threshold function

In decision tree complexity of a boolean function, a very well know lower bound method is to find a (approximate) polynomial that represents the function. Paturi gave a characterization for symmetric ...
-3
votes
2answers
438 views
3
votes
1answer
264 views

Background Required to understand Quantum Monte Carlo techniques?

I'm trying to decide whether or not to do a project for a professor. The project involves writing a survey paper (of high enough quality to get his research group up to speed for a peripheral project)...
1
vote
0answers
260 views

Separating the QIP hierarchy

Background: I'm a CS grad student. I've taken a course on computational complexity. Question: Can you suggest an introductory book on quantum computation, especially regarding the details of ...

1
4 5 6
7
8