As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [classical-computing]

For questions about the relation between quantum computing and classical computing, such as their relative performance.

130 questions
Filter by
Sorted by
Tagged with
345 views

### Can a quantum computer count up by 1 faster than a classical computer?

Let's say you want to generate all images of size NxN, black/white pixels. This is equivalent to counting from 0 to 2^(N^2)-1. ...
1 vote
75 views

88 views

### Deutsch-Jozsa Algorithm - classical solution

so I'm self-studying quantum computing and have a question about the proposed classical solution to the Deustch-Jozsa problem. So given your function $f: \{0,1\}^n \rightarrow \{0,1\}$ say you were to ...
30 views

### What is reservoir computing in simple terms, and how can it be used with quantum computing?

For those who are familiar with the notion of Reservoir Computing, can you explain the concept with simple terms and how it can be used with quantum computing ?
1 vote
28 views

### Find the minimal and maximal of $\widehat{S}_f (\rho \| U^* \sigma U)$

I have been study the minimal (maximal) of a $f-$divergence. Fumio Hiai introduced the $\widehat{S}_f (\rho \| \sigma)$ divergence in his article. \widehat{S}_f (\rho \| \sigma) := \text{Tr} \sigma^{...
76 views

### Understanding the Gottesman-Knill Theorem

I come from a theoretical CS background, and I am trying to gain a better appreciation of the exact formal statement of the Gottesman-Knill theorem in terms that I am more familiar with. My question ...
60 views

### Where is "quantum search" in the complexity hierarchy?

Grover's algorithm is one of the most popular quantum algorithms that solves the problem of "quantum search." But what is this problem, and what are its characteristics. When considering ...
97 views

### Is there something wrong with cross-entropy benchmarking, or is it still considered as a reasonable path towards quantum supremacy?

My question is strongly related with this one. Google's quantum supremacy claim uses Random Circuit Sampling. The principle is the following one: a realistic noise model for random circuits performed ...
864 views

### Are there many practical problems for which Grover's algorithm beats the best heuristic classical algorithm?

It's well known that, given an oracle for a function $f$ from a very large set $S$ (of order $N \gg 1$) to $\{0, 1\}$, Grover's algorithm can find an element of $S$ that maps to 1 with $\sim \sqrt{N}$ ...
189 views

### How does one convert a truth table to a square permutation matrix?

Given a classical circuit of $m$ inputs and $n$ outputs, composed of various AND gates, OR gates, NOT gates, etc., a truth table is a $2^{m}\times(m+n)$-sized matrix, where, in general, the first $m$ ...
24 views

### Applying a clock in quantum computing?

In quantum computing, I feel it mostly looks like designing hardware with Hardware Description Language (HDL) experience such as VHDL or Verilog. So the term program language for quantum computing ...
1k views

### Why do people say that Grover's algorithm does not parallelize well?

I've seen several sources, including NIST, claim that Grover's algorithm is unlikely to be useful for attacking a symmetric-key algorithm like AES-128 or a hashing algorithm because "Grover's ...
3k views

### Why do computer scientists care about the phase of qubits?

When I design some classical register, flip-flop, binary counter, small byte of RAM, etc from scratch with classical logic gate, I never deal with such binary direction because classical bit doesn't ...
7k views

### Why is it harder to build quantum computers than classical computers?

Is it because we don't know exactly how to create quantum computers (and how they must work), or do we know how to create it in theory, but don't have the tools to execute it in practice? Is it a mix ...
40k views

### Is quantum computing just pie in the sky?

I have a computer science degree. I work in IT, and have done so for many years. In that period "classical" computers have advanced by leaps and bounds. I now have a terabyte disk drive in my bedroom ...
24 views

### Mapping a classical cipher into quantum implementation of Grover Oracle

I am translating simple ciphers into quantum implementation in order to create oracle for Grover algorithm. I have started the task with a light weight SPECK cipher (got both classical and quantum ...
167 views

### Can there be an equivalent classical circuit for a quantum circuit?

It is known that any classical circuit or algorithm can be implemented on a quantum computer using universal quantum gates. My question is, can there be a circuit with classical statistics which are ...
1 vote
254 views

### Is there any real world problem where I can see quantum computing being better than classical computing?

Is there any paper or piece of code showing, on a REAL quantum computer, that a specific real world problem (possibly related to computer science, machine learning or finance and possibly NOT related ...
165 views

### What are the practical advantages of quantum GANs with respect to classical ones?

I read some papers on Quantum GANs, for instance this one and this one. I also noticed all the main quantum computing frameworks have a tutorial on quantum GANs, e.g. qiskit. However I don't really ...
20 views

### Why does having two classical registers sometimes only yeild one bit?

I was running some qiskit code on qasm_simulator to test something and I realized that, when I have two separate classical registers, sometimes only one bit is generated, and I'm trying to understand ...
1 vote
189 views

### How does Fujitsu's digital annealer work?

I have read Fujitsu's white paper for a brief introduction to their device: http://marketing.us.fujitsu.com/rs/407-MTR-501/images/quantum-inspired-computing.pdf As far as I know, Fujitsu's hardware is ...
365 views

1 vote
209 views

### Would the interest in building quantum computers decrease if a classical algorithm for factoring all integers in polynomial time is discovered?

Quoting Wikipedia: No algorithm has been published that can factor all integers in polynomial time, that is, that can factor a $b$-bit number $n$ in time $O(b^k)$ for some constant $k$. Neither the ...
152 views

### Will standard programming languages be applicable for quantum computing?

I'm new to quantum computers and computing, so it's possible my question is pointless or unnecessary ... but what about current programming languages such as Java, C++, Python in terms of quantum ...
3k views

### Can a quantum computer simulate a normal computer?

Similar to the question Could a Turing Machine simulate a quantum computer?: given a 'classical' algorithm, is it always possible to formulate an equivalent algorithm which can be performed on a ...
4k views

### Quantum circuits explain algorithms, why didn't classical circuits?

When explaining a quantum algorithm, many revert to 'circuit-speak' by drawing a diagram of how qubits split off into transformations and measurements, however, rarely if not never would someone ...
1 vote
40 views

3k views

### Why can't quantum computation replace classical computation?

I am not a total novice of quantum computation (have read the first 6 chapters of Nielsen and Chuang, though not familiar with every part), but there are some fundamental questions that I don't know ...
2k views

### Are circuits with more than 1000 gates common?

I have seen circuits with 30 qubits and around 500 gates. Also circuits with 32 qubits and 6000 gates. Are circuits with more than 1000 gates common in quantum computing? Are there many quantum ...
790 views

### What is the simplest algorithm to demonstrate intuitively quantum speed-up?

What's the simplest algorithm (like Deutsch's algorithm and Grover's Algorithm) for intuitively demonstrating quantum speed-up? And can this algorithm be explained intuitively? Ideally this would be ...