Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [classical-computing]

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

146 questions
Filter by
Sorted by
Tagged with
38 views

### What is the F12 rule for the Game of Life

This is more of a help call to find a specific rule set for the game of life. I'm currently reading the "Entanglement in the Quantum Game of Life", however they refere to the classical F12 ...
725 views

I recently built a dynamic full adder gate with Qiskit. The gate essentially copies the classical computing method for a full adder by emulating the classical gates e.g. AND == Toffoli (Quantum AND ...
42 views

### Simulating any fixed time classical circuit in time poly(t) on a quantum computer

I'm analyzing the paper "Quantum walk algorithm for element distinctness" by Ambainis and at the bottom of page 24 (the last line of "Additional requirements" in section 6.2) ...
1 vote
105 views

### How can I Combine Qiskit's VQE Tutorial and TSP Simulator to solve the TSP on a real backend efficiently?

I have a university project where I am trying to solve the Traveling Salesman Problem by using a real quantum backend, rather than just the VQE simulator, as in this tutorial. I found this code on ...
202 views

### Classical computation required in Shor's algorithm: are they heavy?

A quantum computer also requires to perform classical computations. I would like to know if to implement Shor's algorithm, there is a heavy classical computation cost (i.e. that would require a ...
478 views

### How does the Curry-Howard correspondence apply to quantum programs?

In words of Wikipedia, The Curry–Howard correspondence is the observation that two families of seemingly unrelated formalisms—namely, the proof systems on one hand, and the models of computation ...
35 views

### Is it safe to assume that any hybrid algorithm can be transformed into a purely quantum form with comparable complexity?

Suppose we have a definite function of interest from numbers to numbers (from a finite set). In general, we have a lot of options when we construct algorithms that compute it (with some errors, ...
1 vote
22 views

### Quantum code for Substitution Box

How to write quantum code(qiskit) for n-bit Substitution Box with minimum number of gate and qubit.
42k 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 ...
8k 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 ...
43 views

### How should large quantum computers use Clifford simulators like Stim?

High-level architecture question: When we have the ability to do useful quantum computations with plenty of qubits, error correction and fault tolerance, do Clifford simulators still have a role to ...
170 views

### What is the computational power of classically mixed states?

It is my understanding that mostly one considers as the "classical" state, a single bit string (eg 00101), with a discrete number of deterministic gates applied to it. All computers that ...
183 views

### Is there a fast sparse Hadamard transform?

Suppose I give you an $n$-qubit state vector as a classical list of numbers (or as an oracle that can query the amplitudes). I tell you this state vector will contain exactly $k$ non-zero amplitudes, ...
56 views

Consider Grover's Algorithm, which identifies a specific $N$-bit string from the set of all $N$-bit strings. The string test function only has to be called $2^{\frac{N}{2}}$ times instead of $2^{N-1}$ ...
1 vote
41 views

### What are problems so computationally difficult that they'll likely only be solved with quantum computers? [duplicate]

Of course, there are the exceedingly well-known examples of this, eg. breaking RSI encryption, possibly protein folding, etc. What are some more obscure or overlooked ways that the greater computing ...
1 vote
28 views

### Who is currently working on coherent Ising machines (classical analog devices)?

Can you share some papers on that subject? Review papers would be highly appreciated. What are limitations in terms of connectivity between different spins?
1k views

### Is it possible to "calculate" the absolute value of a permanent using Boson Sampling?

In boson sampling, if we start with 1 photon in each of the first $M$ modes of an interferometer, the probability of detecting 1 photon in each output mode is: $|\textrm{Perm}(A)|^2$, where the ...
54 views

### Why are quantum computing networks so far behind classical methods?

I'm new to quantum computing, and computing in general, but it seems like quantum computing networks are really lagging behind what we have achieved with classical networks. I know that there are ...
37 views

### Advantage of quantum computers over classical computers in fully modeling interactions between atoms?

I'm trying to better understand the advantage quantum computers offer in terms of their ability to more accurately model chemical reactions. As a way to come to a deeper understanding, my question is: ...
1 vote
61 views

### What does Quantum Circuit Wires and Separated mean?

From Quantum Circuits, there are two statements that are not clear. Quantum Circuits Quantum circuits are collections of quantum gates interconnected by quantum wires. The actual structure of a ...
1 vote
123 views

373 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 ...
53 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
29 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^{...
139 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 ...
73 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 ...
366 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 ...
1k 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}$ ...
456 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$ ...
1 vote
37 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 ...
4k 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 ...
332 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
632 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 ...
239 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 ...
32 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
547 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 ...
383 views

1 vote
255 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 ...
408 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 ...
### Can a Hankel matrix $H$ be efficiently decomposed into a linear combination of unitaries (LCU), so that $H=\sum_k a_k U_k$
Suppose I have a Hankel matrix of arbitrary size $N\times M=2^n\times 2^m$ for integers $n<m$ (the qubit numbers of two circuits I have at my possession), given by: \$H=\begin{pmatrix}x_1&x_2&...