×

The accessibility of convex bodies and derandomization of the hit and run algorithm. (English) Zbl 1396.52005

In this manuscript, the authors introduce the new concept of accessibility for convex bodies in \(d\)-dimensional Euclidean space. Roughly speaking, a convex set \(C\subset \mathbb R^d\) is said to be accessible if there exist \(k,\ell\in\mathbb N\) and a set \(\{e_1,\dots,e_\ell\}\) of vectors in \(\mathbb R^d\) such that one may get from a point \(x\in C\) to a point \(y\in C\) in \(k\)-steps (’walking’ only in the vector directions) without leaving the set \(C\). The main result of the paper shows that any convex body \(C\) in \(\mathbb R^d\) is accessible in \(d+1\) steps with respect to set \(\{e_1,\dots,e_\ell\}\) of vectors where \(\ell \leq (2d+1)^d +d\). This result yields a new algorithm, which maybe considered as a derandomized Hit & Run algorithm applied to a sequence of random points covering \(C\) uniformly.

MSC:

52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
52A22 Random convex sets and integral geometry (aspects of convex geometry)
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] W. Bruzda, V. Cappellini, H.-J. Sommers, K. ˙Zyczkowski: Random quantumoperations, Phys. Lett., A 373 (2009) 320-324. · Zbl 1227.81019
[2] S. L. Braunstein: Geometry of quantum inference, Phys. Lett., A 219 (1996)169-174. · Zbl 0972.81521
[3] V. Cappellini H.-J. Sommers, K. ˙Zyczkowski: Subnormalized states and trace-non-increasing maps, J. Math. Phys. 48, 052110 (2007) 19 p. · Zbl 1144.81320
[4] V. Cappellini H.-J. Sommers, W. Bruzda, K. ˙Zyczkowski: Random bistochasticmatrices, J. Phys. A, Math. Theor. 42, 365209 (2009) 23 p. · Zbl 1179.15036
[5] W. Doeblin: Sur les propri´et´es asymptotiques de mouvement r´egis par certainstypes de chaˆınes simples, Bull. Math. Soc. Roum. Sci. 39 (1937) 57-115. · Zbl 0019.17503
[6] M. Dyer, A. Frieze, R. Kannan: A random polynomial-time algorithm for ap-proximating the volume of convex bodies, J. Assoc. Comput. Mach. 38(1) (1991)1-17. · Zbl 0799.68107
[7] F. John: Extremum problems with inequalities as subsidiary conditions, in:Studies and Essays, K. O. Friedrichs et al. (ed.), Interscience, New York (1948)187-204.916B. Collins et al. / Accessibility of Convex Bodies · Zbl 0034.10503
[8] M. J. W. Hall: Random quantum correlations and density operator distributions,Phys. Lett., A 242 (1998) 123-129. · Zbl 0940.82031
[9] G. Kimura: The Bloch vector for n-level systems, Phys. Lett., A 314 (2003)339-349. · Zbl 1052.81117
[10] L. Lov´asz: Random walks on graphs: a survey, in: Combinatorics. Paul Erd¨osis Eighty. Vol. 2, D. Mikl´os et al. (ed.), Bolyai Soc. Math. Stud. 2, J´anos BolyaiMath. Soc., Budapest (1996) 353-397. · Zbl 0854.60071
[11] L. Lov´asz, S. Vempala: Hit-and-run from a corner, SIAM J. Comput. 35(4)(2006) 985-1005. · Zbl 1103.52002
[12] L. Lov´asz, S. Vempala: The geometry of logconcave functions and samplingalgorithms, Random Struct. Algorithms 30(3) (2007) 307-358. · Zbl 1122.65012
[13] S. P. Meyn, R. L. Tweedie: Markov Chains and Stochastic Stability, Springer,London (1993). · Zbl 0925.60001
[14] G. Pisier: The Volume of Convex Bodies and Banach Space Geometry, CambrigeUniversity Press, Cambridge (1999). · Zbl 0933.46013
[15] L. I. Schiff: Quantum Mechanics, McGraw-Hill, New York (1968).
[16] K. Szyma´nski, B. Collins, T. Szarek, K. ˙Zyczkowski: Convex set of quantumstates with positive partial transpose analysed by hit and run algorithm, J.Phys. A (2017), in print, arXiv:1611.01194 [quant-ph].
[17] S. Vempala: Geometric random walks: a survey, in: Combinatorial and Compu-tational Geometry, J. E. Goodman et al. (ed.), MSRI Publications 52, CambridgeUniversity Press, Cambridge (2005) 573-612. · Zbl 1106.52002
[18] K. ˙Zyczkowski, H.-J. Sommers: Induced measures in the space of mixed quantumstates, J. Phys. A, Math. Gen. 34 (2001) 7111-7125. · Zbl 1031.81011
[19] K. ˙Zyczkowski, P. Horodecki, A. Sanpera, M. Lewenstein: Volume of the set ofseparable states, Phys. Rev. A 58 (1998) 883-892.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.