Quantum questions

0 answers

## Quantum annealing vs adiabatic quantum computation

I had this impression that quantum annealing is an optimization technique which may or may not produce exact solutions. On the other hand adiabatic quantum computation always gives exact solutions ...

1 answer

## Is the D-Wave architecture a close implementation of quantum interactive proof?

A very high level architecture is, as mentioned here, shown in this picture. The component on the left is classical while the one on the right is the D-Wave box. I understand that in QIP, Arthur is …

1 answer

## The complexity of sampling (approximately) the Fourier transform of a Boolean function

One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P. Here and …

1 answer

## Why spectral norms are used for computing the complexity of adiabatic Hamiltonian?

In the context of adiabatic quantum computation the spectral norm was first used in the first adiabatic paper by Farhi et. al. when he demonstrated the relation of it to the conventional quantum ...

0 answers

## Is SVP in Lattices equivalent with decoding random linear codes problem in terms of hardness?

Is there any equivalence (reduction) of the Decoding of random linear codes problem which the McEliece cryptosystem is based with the SVP problem where recent lattice base cryptography put its ...

0 answers

## 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 ...

0 answers

## 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 …

2 answers

## Is adiabatic quantum computing as powerful as qubit computing?

Much of quantum computing literature focuses on qubit-based computation. Adiabatic quantum computing is not based on qubits. I am looking for insight into any of the following. Is adiabatic quantum …

1 answer

## 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 ...

1 answer

## 1st & 2nd quantization from TCS

Last year I attended Scott Aaronson's talk Hawking Quantum Wares at the Classical Complexity Bazaar. Being intrigued by his argument that "[e]ven if quantum mechanics hadn't existed, theoretical ...

2 answers

## Quantum oracle implementation overhead

I am a physicist getting acquainted with one of the typical constructs for formulation and analysis of quantum algorithms (such as search problems or query complexity models), namely the "oracle ...

0 answers

1 answer

## Quantum oracle for non-negative vector (closed)

I was wondering if anyone knew on whether it is possible to construct a quantum oracle that was able to detect whether a given state vector was "non-negative"? Essentially I have a classical problem …

Jan 8 at 7:54
1 answer

## Reference request: number-theory-free proof that maximal stabilizer groups determine unique states

Context. I am writing on topics such as the Gottesman-Knill theorem, using Pauli stabilizer groups, but in the case of d-dimensional qudits — where d may have more than one prime factor. (I ...

1 answer

## Things that imply BQP Derandomization

I am aware that it is generally believed that P = BPP, but BQP != P (since factoring is in BQP, and factoring seems hard.) For BPP, we have the hardness vs randomness result: which states that ...

1 answer

## Polynomial speedups with algorithms based on semidefinite programming

This is a followup of a recent question asked by A. Pal: Solving semidefinite programs in polynomial time. I am still puzzling over the actual running time of algorithms that compute the solution of …

2 answers

## 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 …

2 answers

## Major advance for measurement based quantum computing?

http://arxiv.org/abs/1211.3405 The Measurement Based Quantum Computing Search Algorithm is Faster than Grover's Algorithm If this recent paper is true, it seems like a major advance for ...

2 answers

## Quantum PAC learning

Background Functions in $AC^0$ are PAC learnable in quasipolynomial time with a classical algorithm that requires $O(2^{log(n)^{O(d)}})$ randomly chosen queries to learn a circuit of depth d [1]. If …

5 answers

## 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 ...

1 answer

## Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?

Forgive me wise men for my simple words, for I am but a noob. There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum ...

0 answers

## On optimality of Grover algorithm with high success probability

It is well-known that bounded error quantum query complexity of the function $OR(x_1,x_2,\ldots, x_n)$ is $\Theta(\sqrt{n})$. Now the question is what if we want our quantum algorithm to succeed for …

5 answers

## 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 …

Nov 23 '12 at 17:11
3 answers

## Complexity of optimization over unitary group

What is the computational complexity of optimizing various functions over the unitary group $\mathcal{U}(n)$? A typical task, arising often in quantum information theory, would be maximizing a ...

3 answers

## Are there any known implementations for quantum computing constructs?

Quantum Computation is an active area of research that aims to take advantage of quantum physics (e.g. quantum entanglement) to advance the efficiency capabilities of computers (does not alter the ...

Oct 15 '12 at 20:29
15 30 50 per page