Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function

• URL: http://arxiv.org/abs/2007.05469v1
• Date: Fri, 10 Jul 2020 16:30:58 GMT
• Title: Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function
• Authors: Sergey Bravyi, Theodore J. Yoder, and Dmitri Maslov
• Abstract summary: A common belief is that the Hidden Weighted Bit function is exponentially hard for implementation by reversible ancilla-free circuits. We develop a reversible ancilla-free circuit of size $O(n6.42)$, where $n$ is the number of bits. We also show that the function can be computed by a quantum ancilla-free circuit of size $O(n2)$.
• Score: 7.140119152422295
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Hidden Weighted Bit function plays an important role in the study of classical models of computation. A common belief is that this function is exponentially hard for the implementation by reversible ancilla-free circuits, even though introducing a small number of ancillae allows a very efficient implementation. In this paper, we refute the exponential hardness conjecture by developing a polynomial-size reversible ancilla-free circuit computing the Hidden Weighted Bit function. Our circuit has size $O(n^{6.42})$, where $n$ is the number of input bits. We also show that the Hidden Weighted Bit function can be computed by a quantum ancilla-free circuit of size $O(n^2)$. The technical tools employed come from a combination of Theoretical Computer Science (Barrington's theorem) and Physics (simulation of fermionic Hamiltonians) techniques.

Related papers

• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices. We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• Efficiently learning fermionic unitaries with few non-Gaussian gates [0.0]
  We present a learning algorithm that learns an $n$-mode circuit containing parity-preserving non-Gaussian gates. Our approach relies on learning approximate Gaussian unitaries that transform the circuit into one that acts non-trivially only on a constant number of Majorana operators.
  arXiv  Detail & Related papers  (2025-04-21T18:02:39Z)
• Almost Optimal Synthesis of Reversible Function in Qudit Model [5.9453200974654195]
  We propose a method to synthesize even permutations in $A_dn$ using $Theta(d)$(n - 1)$-qudit sub-circuits. We also introduce a technique for reversible functions employing $Oleft( n dn right)$ gates and only a single ancilla.
  arXiv  Detail & Related papers  (2025-01-09T13:44:14Z)
• Fast quantum integer multiplication with zero ancillas [0.5755004576310334]
  We introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits. The only qubits involved are the input and output registers themselves. Our algorithm has the potential to outperform previous problem sizes relevant in practice.
  arXiv  Detail & Related papers  (2024-03-26T18:00:03Z)
• Polylogarithmic-depth controlled-NOT gates without ancilla qubits [0.0]
  Controlled operations are fundamental building blocks of quantum algorithms. Decomposing $n$-control-NOT gates into arbitrary single-qubit and CNOT gates is a crucial but non-trivial task.
  arXiv  Detail & Related papers  (2023-12-20T17:23:11Z)
• On the Pauli Spectrum of QAC0 [2.3436632098950456]
  We conjecture that the Pauli spectrum of $mathsfQAC0$ satisfies low-degree concentration. We obtain new circuit lower bounds and learning results as applications.
  arXiv  Detail & Related papers  (2023-11-16T07:25:06Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Extracting a function encoded in amplitudes of a quantum state by tensor network and orthogonal function expansion [0.0]
  We present a quantum circuit and its optimization procedure to obtain an approximating function of $f$ that has a number of degrees of freedom with respect to $d$. We also conducted a numerical experiment to approximate a finance-motivated function to demonstrate that our method works.
  arXiv  Detail & Related papers  (2022-08-31T04:10:24Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Variational Adiabatic Gauge Transformation on real quantum hardware for effective low-energy Hamiltonians and accurate diagonalization [68.8204255655161]
  We introduce the Variational Adiabatic Gauge Transformation (VAGT) VAGT is a non-perturbative hybrid quantum algorithm that can use nowadays quantum computers to learn the variational parameters of the unitary circuit. The accuracy of VAGT is tested trough numerical simulations, as well as simulations on Rigetti and IonQ quantum computers.
  arXiv  Detail & Related papers  (2021-11-16T20:50:08Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases [73.53227696624306]
  We present a new family of algorithms for learning Fourier-sparse set functions. In contrast to other work that focused on the Walsh-Hadamard transform, our novel algorithms operate with recently introduced non-orthogonal Fourier transforms. We demonstrate effectiveness on several real-world applications.
  arXiv  Detail & Related papers  (2020-10-01T14:31:59Z)
• Efficient Quantum Circuit Decompositions via Intermediate Qudits [5.377885520874246]
  We show a method to generate ancilla out of idle qubits by placing some in higher-value states, called qudits. Quantum computers will be resource-constrained for years to come so reducing ancilla requirements is crucial.
  arXiv  Detail & Related papers  (2020-02-24T23:37:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.