27 votes
Accepted

Oracle Construction for Grover's Algorithm

The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to. For example, suppose you have a 3-sat problem: ...
  • 1,468
24 votes
Accepted

Factoring as a decision problem

Here the goal is to construct a decision problem D so that (a) if you can factor you can solve the decision problem in polynomial time and (b) if you can solve the decision problem you can factor in ...
19 votes
Accepted

Entropy and computational complexity

Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there ...
18 votes

The utility of Renyi entropies?

Renyi entropy is analogous, in some sense, to $\ell_p$-norms, so let's first recall why those norms are useful. Suppose we have a vector of numbers $a \in \mathbb{R}^n$. We want to have a single ...
  • 5,190
16 votes
Accepted

The utility of Renyi entropies?

Consider trying to make atomic guesses for an unknown random variable $X$ distributed over some finite set $A.$ In Shannon entropy, it is assumed that you can query bit by bit, i.e., if $A=\{1,\ldots,...
  • 2,016
15 votes

Generating "infinite" randomness from a constant number of sources

This is a great question, Suresh! Our randomness expansion result does not imply any complexity theoretic result. Here's one way to understand the result: we believe that quantum mechanics governs ...
  • 3,708
11 votes

The utility of Renyi entropies?

Renyi entropy (of order 2) is useful in cryptography for analyzing the probability of collisions. Recall that the Renyi entropy of order 2 of a random variable $X$ is given by $$H_2(X) = - \log_2 \...
  • 10.5k
9 votes

Factoring as a decision problem

Yes, there is a paper by John Watrous, which formally addresses the concerns raised on Lipton's blog (reported in user2917198's comment). Here is the reference: J. Watrous. An introduction to quantum ...
9 votes
Accepted

Applications of HHL's algorithm for solving linear equations

If by "classically using the solutions of the linear equation" you mean "accessing the information in the exactly same way a classical computer does" or, in other words, "obtaining the classical ...
9 votes
Accepted

Where can I find examples of error correcting codes of the following types?

If you just need any code $E : \{0,1\}^n \to \{0,1\}^m$ where $m=O(n)$ and where the distance is linear in $m$, then what you are looking for is called an "asymptotically good code". There are many ...
  • 5,190
8 votes
Accepted

Quantum annealing vs adiabatic quantum computation

Adiabatic quantum computing (AQC) is a computational model (as Peter said in the comments). Compare AQC with other models of computation such as: circuit-based quantum computing (CBQC) Adleman-...
8 votes
Accepted

theorems for universal set of quantum gates for SU(d)

I'm not aware of any proof that the Clifford group + any non-Clifford element gives a universal set of quantum gates. The closest related result that I know is that the Clifford group + any non-...
8 votes
Accepted

Quantum Money where not even the Bank can counterfeit

There are proposals for quantum money where it appears that not even the bank can produce two copies of a quantum money state with the same serial number. See Farhi et al's paper Quantum Money from ...
7 votes
Accepted

Is it possible to encrypt quantum states under reasonable assumptions?

One can encrypt an n-qubit state using a 2n-bit classical secret key. The idea is to use the key to select a random Pauli operator, and apply that operator to the secret as an encryption. (The inverse ...
7 votes

States and Probability distributions that the 5-qubits IBM computer can produce

I just ran the first state you suggest (i.e. the GHZ state with negative phase in the Hadamard basis). Basically what I did was to write a circuit which creates that state, apply one of 5 stabilizer ...
7 votes
Accepted

Fast classical simulation of quantum algorithms

Your question was inspired by the recent quantum-inspired classical advance in recommendation algorithm. Note that it is not the firs time such a thing happens. In 2015, similar developments happened ...
6 votes
Accepted

Why are sub-normalized states studied in quantum computation?

It is often mathematically very convenient to work with sub-normalized states independently of the question whether they have a direct physical meaning. However, you can always see them as states ...
6 votes
Accepted

How does one determine if a mixed bipartite quantum state is entangled or not?

In http://arxiv.org/pdf/quant-ph/0303055v1.pdf, it is shown that the weak membership problem for the set of separable states is NP-hard. As you can see in Definition 6.2 (page 18), this amounts to ...
6 votes

When is a non-unitary quantum system only theoretical?

Look at John Preskill's Lecture Notes; particularly Section 3.2. As you noted, you can do a NAND gate by using a Toffoli gate and throwing away some of the output qubits. This results in decoherence, ...
6 votes
Accepted

Why is it impossible to work with polylog length encoding schemes for quantum circuits?

Clearly you can work with abstract compressed representations of circuits. You can reason about them and manipulate them and turn them into concrete lists of gates. We do it all the time. But in ...
  • 1,468
6 votes
Accepted

Simulating quantum measurements by unitaries

The basic idea here is that any operation that uses measurement can be replaced by an operation that instead CNOTs qubits onto ancillae. Any circuit with an intermediate measurement can be converted ...
  • 1,468
6 votes

How can I get $\sum_n e^{i a_n} |n\rangle$ from $\sum_n a_n |n\rangle$?

It's not unitary, so it's impossible because all quantum transformations have to be unitary. Consider the states $$ \frac{3}{5} |0\rangle + \frac{4}{5} |1\rangle \quad \mathrm{and} \quad \frac{3}{5} |...
5 votes
Accepted

Dimension of the Fourier transform for $S_5$

A quantum Fourier transform is a unitary operation, so the number of basis states of the input and output must be the same. The number of basis states before the Fourier transform is 120, the number ...
5 votes

Travelling sales man with Quantum Computers

The set of problems that can be solved by an universal quantum computer in "polynomial time" (with at most 1/3 probability of error) is called BQP. Travelling salesman problem is in complexity class ...
5 votes
Accepted

How well can an arbitrary (unknown) quantum state be imperfectly cloned?

This problem has been studied in great detail, not just for the case of imperfectly cloning 1 qubit to get 2 copies, but more general problems of how to get m copies of a state given n copies, etc. I ...
5 votes
Accepted

Is it possible to MAC a quantum state with a classical key under reasonable assumption?

Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, Alain Tapp. "Authentication of Quantum Messages", FOCS 2002. http://www.cse.psu.edu/~ads22/pubs/PS-CSAIL/BCGST02-focs-final.pdf As with ...
5 votes
Accepted

When is a non-unitary quantum system only theoretical?

I complete here Peter’s answer with a characterization of physical maps as CPTP maps. As you know, if the system is isolated, the only operations you can implement are the unitary operations. But, ...
4 votes
Accepted

The Arrow of Time in a Non-Physical Realm

For the consequences of such transmission to theoretical computer science (the only aspect of your question that is on-topic here) see Aaronson and Watrous's "Closed Timelike Curves Make Quantum and ...
4 votes

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

Following up on the line of thinking presented by Alex Monras, there is actually a quite generic argument for this kind of bound that goes beyond diamond norm and applies to many other channel ...
4 votes
Accepted

Question about discarding the second register in the standard approach of hidden subgroup algorithm

Discarding in this context can be carried out by performing a Partial Trace. The system you're interested in is that of the first register. If you want to know only its state, as opposed to the ...

Only top scored, non community-wiki answers of a minimum length are eligible