arXiv:quant-ph/0506081

Quantum optical device accelerating dynamic programming

Dima Yu. Grigoriev, Alexander Ya. Kazakov, S. A. Vakulenko

Published Jun 10, 2005• 0 citations

Abstract

In this paper we discuss analogue computers based on quantum optical systems accelerating dynamic programming for some computational problems. These computers, at least in principle, can be realized by actually existing devices. We estimate an acceleration in resolving of some NP-hard problems that can be obtained in such a way versus deterministic computers

DOI: 10.48550/arxiv.quant-ph/0506081

Related papers

Optical device accelerating dynamic programming

Dima Yu. Grigoriev, Alexander Ya. Kazakov, S. Vakulenko

The subject of this report is the comparison of the conventional deterministic computers versus the analogue computer based on the quantum optical system in resolving some NP-hard computational problems. We describe an optical machine which can be realized physically.

Physics of Particles and Nuclei LettersMar 1, 20071 citation

Vector quantization complexity and quantum computing

Paolo Gastaldo, Sandro Ridella, Rodolfo Zunino

A dichotomy between 'analogue' modeling and 'digital' implementation is often encountered when designing vector quantizers. In the case of digital systems, the requirement of optimality can bring about NP-hard problems. The paper discusses the possibility of using advanced paradigms such as quantum computing for digital optimization processes in order to overcome the limitations of conventional machinery. The presented research provides analytical criteria determining the relative advantages of conventional over quantum-computing approaches.

International Joint Conference on Neural Networks (IJCNN)Feb 28, 20050 citations

Computational Aspects of the Trace Norm Contraction Coefficient

Idris Delsol, Omar Fawzi, Jan Kochanowski +1 more

We show that approximating the trace norm contraction coefficient of a quantum channel within a constant factor is NP-hard. Equivalently, this shows that determining the optimal success probability for encoding a bit in a quantum system undergoing noise is NP-hard. This contrasts with the classical analogue of this problem that can clearly be solved efficiently. We also establish the NP-hardness of deciding if the contraction coefficient is equal to 1, i.e., the channel can perfectly preserve a bit. As a consequence, deciding if a non-commutative graph has an independence number of at least 2 is NP-hard. In addition, we establish a converging hierarchy of semidefinite programming upper bounds on the contraction coefficient.

arXiv:2507.16737IEEE Transactions on Information TheoryJan 1, 20260 citations

Quantum analogue computing

Vivien M. Kendon, Kae Nemoto, William J. Munro

We briefly review what a quantum computer is, what it promises to do for us and why it is so hard to build one. Among the first applications anticipated to bear fruit is the quantum simulation of quantum systems. While most quantum computation is an extension of classical digital computation, quantum simulation differs fundamentally in how the data are encoded in the quantum computer. To perform a quantum simulation, the Hilbert space of the system to be simulated is mapped directly onto the Hilbert space of the (logical) qubits in the quantum computer. This type of direct correspondence is how data are encoded in a classical analogue computer. There is no binary encoding, and increasing precision becomes exponentially costly: an extra bit of precision doubles the size of the computer. This has important consequences for both the precision and error-correction requirements of quantum simulation, and significant open questions remain about its practicality. It also means that the quantum version of analogue computers, continuous-variable quantum computers, becomes an equally efficient architecture for quantum simulation. Lessons from past use of classical analogue computers can help us to build better quantum simulators in future.

arXiv:1001.2215Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering SciencesJul 5, 201041 citations

Dynamic Programming on a Quantum Annealer: Solving the RBC Model

Jesús Fernández‐Villaverde, Isaiah Hull

We introduce a novel approach to solving dynamic programming problems, such as those in many economic models, on a quantum annealer, a specialized device that performs combinatorial optimization. Quantum annealers attempt to solve an NP-hard problem by starting in a quantum superposition of all states and generating candidate global solutions in milliseconds, irrespective of problem size. Using existing quantum hardware, we achieve an order-of-magnitude speed-up in solving the real business cycle model over benchmarks in the literature. We also provide a detailed introduction to quantum annealing and discuss its potential use for more challenging economic problems.

arXiv:2306.04285Jun 7, 20233 citations

Quantum analogue computing

Viv M. Kendon, Kae Nemoto, William J. Munro

We briefly review what a quantum computer is, what it promises to do for us and why it is so hard to build one. Among the first applications anticipated to bear fruit is the quantum simulation of quantum systems. While most quantum computation is an extension of classical digital computation, quantum simulation differs fundamentally in how the data are encoded in the quantum computer. To perform a quantum simulation, the Hilbert space of the system to be simulated is mapped directly onto the Hilbert space of the (logical) qubits in the quantum computer. This type of direct correspondence is how data are encoded in a classical analogue computer. There is no binary encoding, and increasing precision becomes exponentially costly: an extra bit of precision doubles the size of the computer. This has important consequences for both the precision and errorcorrection requirements of quantum simulation, and significant open questions remain about its practicality. It also means that the quantum version of analogue computers, continuous-variable quantum computers, becomes an equally efficient architecture for quantum simulation. Lessons from past use of classical analogue computers can help us to build better quantum simulators in future.

Jan 1, 201027 citations