Questions tagged [classical-computing]

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

15 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7 votes
0 answers
130 views

Empirical Algorithmics for Near-Term Quantum Computing

In Empirical Algorithmics, researchers aim to understand the performance of algorithms through analyzing their empirical performance. This is quite common in machine learning and optimization. Right ...
hopefully coherent's user avatar
3 votes
0 answers
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 ...
trillianhaze's user avatar
3 votes
0 answers
96 views

What is the best way to use loop statements on a quantum computer?

I am interested in solving a time dependent linear partial differential equation of the form $Ax=b$ which, in classical computing, would amount to looping over solutions of $Ax=b$ where $b$ is updated ...
thespaceman's user avatar
2 votes
0 answers
23 views

Best classical algorithm for period finding on finite Abelian groups

Given a finite Abelian group $G = \prod_{j=1}^n \mathbb{Z}_{m_j}$ with $m_j \geq 2$ and a function $h: G \to \mathbb{C}$ that is $s$-periodic. I have already proven that for all $\xi \in G$ we have $\...
mrwarrdy's user avatar
2 votes
0 answers
148 views

When is a Quantum Computer Slower Than a Classical Computer?

Someone offhandedly mentioned to me that quantum computers are sometimes significantly (I guess they meant asymptotically) slower than classical computers. Unfortunately, I didn't get any arguments ...
Little Helper's user avatar
1 vote
0 answers
27 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^{...
Minh's user avatar
  • 111
1 vote
1 answer
75 views

Accuracy of Classical Counting problem

Consider a classical algorithm for the counting problem which samples uniformly and independently $k$ times from the search space, and let $X_1, ... ,X_k$ be the results of the oracle calls, that is, $...
Sooraj S's user avatar
  • 721
1 vote
0 answers
40 views

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&...
JoJo's user avatar
  • 89
1 vote
0 answers
121 views

Can hash functions speed up quantum simulation? (Generalizing May and Schlieper's idea)

Recently May and Schlieper have published a preprint (https://arxiv.org/abs/1905.10074) arguing that the modular exponential register in Shor's algorithms can be replaced with a universally hashed ...
botsina's user avatar
  • 157
1 vote
0 answers
76 views

Can Quantum Voting Machine replace Electronic Voting Machine (EVM) in future?

Some countries like India are using standalone electronic voting machines (EVM) for elections. They are not interconnected, use no power cables (run on battery), no wireless cards and are secure ...
Chaitanya Reddy's user avatar
1 vote
0 answers
591 views

Comparing CPU to QPU In terms of processing power

The current processors are limited by the speed of the electrons but quantum processors take advantage of the properties of subatomic particles. But the question is how to compare the processing power ...
R1-'s user avatar
  • 209
0 votes
0 answers
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 ?
Duen's user avatar
  • 266
0 votes
0 answers
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 ...
Muhammad Ikhwan Perwira's user avatar
0 votes
0 answers
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 ...
aneela's user avatar
  • 223
0 votes
0 answers
19 views

determine degree of boolean polynomial given as black box

I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its ...
Math-fort's user avatar